1 citations · 1 across the 9 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.CC2023
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;…
cs.CC2023
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…