53 citations · 247 across the 33 of their papers we have counts for
6 papers · 1 filter
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Mark Bun, Justin Thaler
We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit can…
Annotations for Sparse Data Streams
Amit Chakrabarti, Graham Cormode, Navin Goyal +1
Motivated by cloud computing, a number of recent works have studied annotated data streams and variants thereof. In this setting, a computationally weak verifier (cloud user), lack…
Time-Optimal Interactive Proofs for Circuit Evaluation
Justin Thaler
Recently, researchers have been working toward the development of practical general-purpose protocols for verifiable computation. These protocols enable a computationally weak veri…
Faster Private Release of Marginals on Small Databases
Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman +1
We study the problem of answering \emph{-way marginal} queries on a database , while preserving differential privacy. The answer to a -way marginal query…
Parallel Peeling Algorithms
Jiayang Jiang, Michael Mitzenmacher, Justin Thaler
The analysis of several algorithms and data structures can be framed as a peeling process on a random hypergraph: vertices with degree less than k are removed until there are no ve…
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities
Mark Bun, Justin Thaler
The -approximate degree of a Boolean function is the minimum degree of a real polynomial that approximates to within in the …