37 citations · 101 across the 43 of their papers we have counts for
31 papers · 1 filter
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…
The composition complexity of majority
Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan
We study the complexity of computing majority as a composition of local functions: \[ \text{Maj}_n = h(g_1,\ldots,g_m), \] where each is an arbitrary…
Tradeoffs for small-depth Frege proofs
Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan
We study the complexity of small-depth Frege proofs and give the first tradeoffs between the size of each line and the number of lines. Existing lower bounds apply to the overall p…