53 citations · 247 across the 33 of their papers we have counts for
3 papers · 1 filter
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…