1 citations · 1 across the 9 of their papers we have counts for
12 papers
Quantum Speedups Require Structure or Depth
Guy Blanc, Jordan Docter, Carmen Strassle +1
One of the most basic conjectures in quantum complexity theory states that every -query quantum algorithm can be simulated on most inputs by a -query classical…
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…
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…
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…
Fast decision tree learning solves hard coding-theoretic problems
Caleb Koch, Carmen Strassle, Li-Yang Tan
We connect the problem of properly PAC learning decision trees to the parameterized Nearest Codeword Problem (-NCP). Despite significant effort by the respective communities, al…
Superconstant Inapproximability of Decision Tree Learning
Caleb Koch, Carmen Strassle, Li-Yang Tan
We consider the task of properly PAC learning decision trees with queries. Recent work of Koch, Strassle, and Tan showed that the strictest version of this task, where the hypothes…
A Strong Direct Sum Theorem for Distributional Query Complexity
Guy Blanc, Caleb Koch, Carmen Strassle +1
Consider the expected query complexity of computing the -fold direct product of a function to error with respect to a distribution . One s…
Properly Learning Decision Trees with Queries Is NP-Hard
Caleb Koch, Carmen Strassle, Li-Yang Tan
We prove that it is NP-hard to properly PAC learn decision trees with queries, resolving a longstanding open problem in learning theory (Bshouty 1993; Guijarro-Lavin-Raghavan 1999;…
A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers
Guy Blanc, Caleb Koch, Carmen Strassle +1
We prove a strong composition theorem for junta complexity and show how such theorems can be used to generically boost the performance of property testers. The -approx…
Certification with an NP Oracle
Guy Blanc, Caleb Koch, Jane Lange +2
In the certification problem, the algorithm is given a function with certificate complexity and an input , and the goal is to find a certificate of size $\le \text…
Superpolynomial Lower Bounds for Decision Tree Learning and Testing
Caleb Koch, Carmen Strassle, Li-Yang Tan
We establish new hardness results for decision tree optimization problems, adding to a line of work that dates back to Hyafil and Rivest in 1976. We prove, under randomized ETH, su…