Publications

10 results at Computational Complexity

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