Fast decision tree learning solves hard coding-theoretic problems
<|reference_start|>Fast decision tree learning solves hard coding-theoretic problems: 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 algorithm for the former runs in quasipolynomial time (Ehrenfeucht and Haussler 1989) and the best known approximation ratio for the latter is $O(n/\log n)$ (Berman and Karpinsky 2002; Alon, Panigrahy, and Yekhanin 2009). Research on both problems has thus far proceeded independently with no known connections.   We show that $\textit{any}$ improvement of Ehrenfeucht and Haussler's algorithm will yield $O(\log n)$-approximation algorithms for $k$-NCP, an exponential improvement of the current state of the art. This can be interpreted either as a new avenue for designing algorithms for $k$-NCP, or as one for establishing the optimality of Ehrenfeucht and Haussler's algorithm. Furthermore, our reduction along with existing inapproximability results for $k$-NCP already rule out polynomial-time algorithms for properly learning decision trees. A notable aspect of our hardness results is that they hold even in the setting of $\textit{weak}$ learning whereas prior ones were limited to the setting of strong learning.<|reference_end|>
@article{koch2024fast,
    title={Fast decision tree learning solves hard coding-theoretic problems},
    author={Caleb Koch, Carmen Strassle, Li-Yang Tan},
    journal={arXiv preprint arXiv:2409.13096},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.13096},
    primaryClass={cs.CC cs.DS cs.LG}
}