53 citations · 247 across the 33 of their papers we have counts for
40 papers
Order-Invariant Cardinality Estimators Are Differentially Private
Charlie Dickens, Justin Thaler, Daniel Ting
We consider privacy in the context of streaming algorithms for cardinality estimation. We show that a large class of algorithms all satisfy -differential privacy, so long as (a)…
Quantum Proofs of Proximity
Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik +1
We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that…
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches
Amit Chakrabarti, Prantar Ghosh, Justin Thaler
We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud…
Relative Error Streaming Quantiles
Graham Cormode, Zohar Karnin, Edo Liberty +2
Estimating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream of items from a data universe equipped with…
Improved Approximate Degree Bounds For k-distinctness
Nikhil S. Mande, Justin Thaler, Shuchen Zhu
An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs…
Vanishing-Error Approximate Degree and QMA Complexity
Alexander A. Sherstov, Justin Thaler
The -approximate degree of a function is the least degree of a multivariate real polynomial such that for all . We det…