Quantum Query Complexity of Almost All Functions with Fixed On-set Size
- Andris Ambainis
- Kazuo Iwama
- et al.
- 2016
- Computational Complexity
Paper
Publications
10 results at Computational Complexity
Arthur and Merlin as Oracles
- Venkatesan T. Chakaravarthy
- Sambuddha Roy
- 2011
- Computational Complexity
PaperDerandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds
- B. Aydinliog̃lu
- Dan Gutfreund
- et al.
- 2011
- Computational Complexity
PaperOn the hardness of approximating multicut and sparsest-cut
- Shuchi Chawla
- Robert Krauthgamer
- et al.
- 2006
- Computational Complexity
PaperQuantifying knowledge complexity
- Oded Goldreich
- Erez Petrank
- 1999
- Computational Complexity
PaperLower bounds for polynomial evaluation and interpolation problems
- Victor Shoup
- Roman Smolensky
- 1996
- Computational Complexity
PaperThe electrical resistance of a graph captures its commute and cover times
- Ashok K. Chandra
- Prabhakar Raghavan
- et al.
- 1996
- Computational Complexity
PaperRandomness in interactive proofs
- Mihir Bellare
- Oded Goldreich
- et al.
- 1993
- Computational Complexity
PaperFast exponentiation using the truncation operation
- Nader H. Bshouty
- Yishay Mansour
- et al.
- 1992
- Computational Complexity
PaperOn the decidability of sparse univariate polynomial interpolation
- Allan Borodin
- Prasoon Tiwari
- 1991
- Computational Complexity
Paper