63 citations · 124 across the 20 of their papers we have counts for
4 papers · 1 filter
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 (…