research
∙
08/17/2023
Distribution-Free Proofs of Proximity
Motivated by the fact that input distributions are often unknown in adva...
share
research
∙
01/05/2023
Streaming Zero-Knowledge Proofs
We initiate the study of zero-knowledge proofs for data streams. Streami...
research
∙
12/06/2022
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
We study the problem of designing worst-case to average-case reductions ...
research
∙
02/18/2022
Worst-Case to Average-Case Reductions via Additive Combinatorics
We present a new framework for designing worst-case to average-case redu...
research
∙
11/22/2021
Sublinear quantum algorithms for estimating von Neumann entropy
Entropy is a fundamental property of both classical and quantum systems,...
research
∙
11/17/2021
Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for ε-Product Spaces
We prove hypercontractive inequalities on high dimensional expanders. As...
research
∙
08/12/2021
Derandomization of Cell Sampling
Since 1989, the best known lower bound on static data structures was Sie...
research
∙
05/08/2021
Quantum Proofs of Proximity
We initiate the systematic study of QMA algorithms in the setting of pro...
research
∙
12/03/2020
Quantum learning algorithms imply circuit lower bounds
We establish the first general connection between the design of quantum ...
research
∙
10/10/2020
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy
We prove a general structural theorem for a wide family of local algorit...
research
∙
04/17/2019
A Lower Bound for Relaxed Locally Decodable Codes
A locally decodable code (LDC) C:0,1^k -> 0,1^n is an error correcting c...
research
∙
03/05/2018
Spatial Isolation Implies Zero Knowledge Even in a Quantum World
Zero knowledge plays a central role in cryptography and complexity. The ...
research
∙
01/10/2018