1 citations · 1 across the 5 of their papers we have counts for
7 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…
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…
A Query-Optimal Algorithm for Finding Counterfactuals
Guy Blanc, Caleb Koch, Jane Lange +1
We design an algorithm for finding counterfactuals with strong theoretical guarantees on its performance. For any monotone model and instance , our a…
The Query Complexity of Certification
Guy Blanc, Caleb Koch, Jane Lange +1
We study the problem of {\sl certification}: given queries to a function with certificate complexity and an input , output a size- c…
Hyperprofile-based Computation Offloading for Mobile Edge Networks
Andrew Crutcher, Caleb Koch, Kyle Coleman +3
In recent studies, researchers have developed various computation offloading frameworks for bringing cloud services closer to the user via edge networks. Specifically, an edge devi…