63 citations · 124 across the 20 of their papers we have counts for
27 papers
Distributional Variants of the Aaronson-Ambainis Conjecture
Uma Girish, Kunal Mittal, Barak Nehoran +1
A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query…
Quantum Logspace Computations are Verifiable
Uma Girish, Ran Raz, Wei Zhan
In this note, we observe that quantum logspace computations are verifiable by classical logspace algorithms, with unconditional security. More precisely, every language in BQL has…
On the works of Avi Wigderson
Boaz Barak, Yael Kalai, Ran Raz +2
This is an overview of some of the works of Avi Wigderson, 2021 Abel prize laureate. Wigderson's contributions span many fields of computer science and mathematics. In this survey…
Certified Hardness vs. Randomness for Log-Space
Edward Pyne, Ran Raz, Wei Zhan
Let be a language that can be decided in linear space and let be any constant. Let be the exponential hardness assumption that for every , memb…
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
Qipeng Liu, Ran Raz, Wei Zhan
In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on bits requires either bits of classical memory or an exponential number (…
Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs
Uma Girish, Kunal Mittal, Ran Raz +1
We prove that for every 3-player (3-prover) game with value less than one, whose query distribution has the support of ham…