8 citations · 18 across the 17 of their papers we have counts for
6 papers · 1 filter
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…
A Distributional-Lifting Theorem for PAC Learning
Guy Blanc, Jane Lange, Carmen Strassle +1
The apparent difficulty of efficient distribution-free PAC learning has led to a large body of work on distribution-specific learning. Distributional assumptions facilitate the des…