37 citations · 101 across the 43 of their papers we have counts for
53 papers
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…
Lifting uniform learners via distributional decomposition
Guy Blanc, Jane Lange, Ali Malik +1
We show how any PAC learning algorithm that works under the uniform distribution can be transformed, in a blackbox fashion, into one that works under an arbitrary and unknown distr…
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…
Multitask Learning via Shared Features: Algorithms and Hardness
Konstantina Bairaktari, Guy Blanc, Li-Yang Tan +2
We investigate the computational efficiency of multitask learning of Boolean functions over the -dimensional hypercube, that are related by means of a feature representation of…