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