Caleb Koch

Fast decision tree learning solves hard coding-theoretic problems

2024 · arXiv (Cornell University)

We connect the problem of properly PAC learning decision trees to the parameterized Nearest Codeword Problem ($k$-NCP). Despite significant effort by the respective communities, algorithmic progress on both problems has been stuck: the fastest known …