Paper Info
Title
Lower Bounds For Query Complexity Of Some Graph Problems
Abstract
The paper [BuhdW02] by H.Buhrman and P, de Wolf contains an impressive survey of solved and open problem in quantum query complexity, including many graph problems. We use recent results by A.Ambainis [Amb02] to prove higher lower bounds for some of these problems. Some of our new lower bounds do not close the gap between the best upper and lower bounds. We prove in these cases that it is impossible to provide a better application of Ambainis' technique for these problems.
Year
Venue
Keywords
2003
VLSI'03: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON VLSI
quantum computation, query algorithms, lower bounds
Field
DocType
Citations 
Query optimization,Discrete mathematics,Graph,Computer science,Real-time computing,Theoretical computer science,Worst-case complexity
Conference
0
PageRank 
References 
Authors
0.34
1
2
Name
Order
Citations
PageRank
Lelde Lace13511.36
Rusins Freivalds278190.68