3 papers
cs.CC2025
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…
quant-ph2025
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…
cs.CC2025
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…