Showing 2023Show all
3 papers · 1 filter
quant-ph2023
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…
cs.CC2023
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions
Huacheng Yu, Wei Zhan
We prove the first polynomial separation between randomized and deterministic time-space tradeoffs of multi-output functions. In particular, we present a total function that on the…
cs.CC2023
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…