research
∙
03/29/2022
(Nearly) All Cardinality Estimators Are Differentially Private
We consider privacy in the context of streaming algorithms for cardinali...
share
research
∙
05/08/2021
Quantum Proofs of Proximity
We initiate the systematic study of QMA algorithms in the setting of pro...
research
∙
07/06/2020
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches
We study graph computations in an enhanced data streaming setting, where...
research
∙
04/03/2020
Relative Error Streaming Quantiles
Approximating ranks, quantiles, and distributions over streaming data is...
research
∙
02/19/2020
Improved Approximate Degree Bounds For k-distinctness
An open problem that is widely regarded as one of the most important in ...
research
∙
09/16/2019
Vanishing-Error Approximate Degree and QMA Complexity
The ϵ-approximate degree of a function f X →{0, 1} is the least degree o...
research
∙
06/02/2019
Approximate degree, secret sharing, and concentration phenomena
The ϵ-approximate degree deg_ϵ(f) of a Boolean function f is the least d...
research
∙
04/18/2019
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
This paper proves new limitations on the power of quantum computers to s...
research
∙
03/01/2019
Sign-Rank Can Increase Under Intersection
The communication class UPP^cc is a communication analog of the Turing M...
research
∙
09/06/2018
Quantum algorithms and approximating polynomials for composed functions with shared inputs
We give new quantum algorithms for evaluating composed functions whose i...
research
∙
10/25/2017