3 citations · 10 across the 11 of their papers we have counts for
13 papers
More is Less:Optimal Security for Haar Quantum Money and More
Zihan Hao, Xingjian Li, Qipeng Liu +1
Quantum cryptography leverages unclonability to enable a wide range of cryptographic applications that are impossible classically, such as digital currency protected against counte…
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…
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…
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…
Parallel Repetition For All 3-Player Games Over Binary Alphabet
Uma Girish, Justin Holmgren, Kunal Mittal +2
We prove that for every 3-player game with binary questions and answers and value , the value of the -fold parallel repetition of the game decays polynomially fast to 0. Tha…
Parallel Repetition for the GHZ Game: A Simpler Proof
Uma Girish, Justin Holmgren, Kunal Mittal +2
We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value…
Lower Bounds for XOR of Forrelations
Uma Girish, Ran Raz, Wei Zhan
The Forrelation problem, introduced by Aaronson [A10] and Aaronson and Ambainis [AA15], is a well studied problem in the context of separating quantum and classical models. Variant…
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm
Uma Girish, Ran Raz, Wei Zhan
We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most~1. The algorithm gets as an input an arbitrary cont…
Odd Yao-Yao Graphs are Not Spanners
Yifei Jin, Jian Li, Wei Zhan
It is a long standing open problem whether Yao-Yao graphs are all spanners [li2002sparse]. Bauer and Damian [bauer2013infinite] showed that all …
Exponential Separations in the Energy Complexity of Leader Election
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie +2
Energy is often the most constrained resource for battery-powered wireless devices and the lion's share of energy is often spent on transceiver usage (sending/receiving packets), n…
Almost All Even Yao-Yao Graphs Are Spanners
Jian Li, Wei Zhan
It is an open problem whether Yao-Yao graphs (also known as sparse-Yao graphs) are all spanners when the integer parameter is large enough. In this paper we sho…