7 papers
Robust Learning with Optimal Error
Guy Blanc
We construct algorithms with optimal error for learning with adversarial noise. The overarching theme of this work is that the use of \textsl{randomized} hypotheses can substantial…
Samplability makes learning easier
Guy Blanc, Caleb Koch, Jane Lange +2
The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions -- even ones that are intractable to sample from. This stands in contras…
Differential privacy from axioms
Guy Blanc, William Pires, Toniann Pitassi
Differential privacy (DP) is the de facto notion of privacy both in theory and in practice. However, despite its popularity, DP imposes strict requirements which guard against stro…
The power of quantum circuits in sampling
Guy Blanc, Caleb Koch, Jane Lange +2
We give new evidence that quantum circuits are substantially more powerful than classical circuits. We show, relative to a random oracle, that polynomial-size quantum circuits can…
Instance-Optimal Uniformity Testing and Tracking
Guy Blanc, Clément L. Canonne, Erik Waingarten
In the uniformity testing task, an algorithm is provided with samples from an unknown probability distribution over a (known) finite domain, and must decide whether it is the unifo…
Computational-Statistical Tradeoffs from NP-hardness
Guy Blanc, Caleb Koch, Carmen Strassle +1
A central question in computer science and statistics is whether efficient algorithms can achieve the information-theoretic limits of statistical problems. Many computational-stati…