Name
Abstract | ||
|---|---|---|
The paper [4] by H. Buhrman and R. de Wolf contains an impressive survey of solved and open problems in quantum query complexity, including many graph problems. We use recent results by A.Ambainis [1] 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 | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-24618-3_11 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
lower bound,upper and lower bounds | Discrete mathematics,Quantum,Graph,Combinatorics,Computer science,Upper and lower bounds | Conference |
Volume | ISSN | Citations |
2932 | 0302-9743 | 15 |
PageRank | References | Authors |
0.92 | 6 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aija Berzina | 1 | 15 | 1.25 |
| Andrej Dubrovsky | 2 | 15 | 1.25 |
| Rusins Freivalds | 3 | 781 | 90.68 |
| Lelde Lace | 4 | 35 | 11.36 |
| Oksana Scegulnaja | 5 | 15 | 1.25 |