Showing cs.CCShow all
2 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
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
Guy Blanc, Alexandre Hayderi, Caleb Koch +1
Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also fo…