Imagen de Portada

Superconstant Inapproximability of Decision Tree Learning

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Koch, Caleb, Strassle, Carmen, Tan, Li-Yang
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity Data Structures and Algorithms Machine Learning
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Fast decision tree learning solves hard coding-theoretic problems
por: Koch, Caleb, et al.
Publicado: (2024)

Computational-Statistical Tradeoffs from NP-hardness
por: Blanc, Guy, et al.
Publicado: (2025)

Samplability makes learning easier
por: Blanc, Guy, et al.
Publicado: (2025)

A Distributional-Lifting Theorem for PAC Learning
por: Blanc, Guy, et al.
Publicado: (2025)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
por: Blanc, Guy, et al.
Publicado: (2024)

Feature Selection and Junta Testing are Statistically Equivalent
por: Beretta, Lorenzo, et al.
Publicado: (2025)

Active Learning for Decision Trees with Provable Guarantees
por: Moakhar, Arshia Soltani, et al.
Publicado: (2026)

Treedepth Inapproximability and Exponential ETH Lower Bound
por: Bonnet, Édouard, et al.
Publicado: (2025)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
por: Bilò, Davide, et al.
Publicado: (2024)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
por: Frei, Fabian, et al.
Publicado: (2025)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
por: S., Karthik C., et al.
Publicado: (2024)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
por: Guruswami, Venkatesan, et al.
Publicado: (2023)

Inapproximability of Maximum Diameter Clustering for Few Clusters
por: Fleischmann, Henry, et al.
Publicado: (2023)

Tight Inapproximability of Target Set Reconfiguration
por: Ohsaka, Naoto
Publicado: (2024)

On the Power of Interactive Proofs for Learning
por: Gur, Tom, et al.
Publicado: (2024)

Exact and Approximate Algorithms for Polytree Learning
por: Harviainen, Juha, et al.
Publicado: (2026)

Learning-Augmented Algorithms for Boolean Satisfiability
por: Attias, Idan, et al.
Publicado: (2025)

Hardness of Maximum Likelihood Learning of DPPs
por: Grigorescu, Elena, et al.
Publicado: (2022)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
por: Hirahara, Shuichi, et al.
Publicado: (2024)

The Sample Complexity of Replicable Realizable PAC Learning
por: Larsen, Kasper Green, et al.
Publicado: (2026)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
por: Hirahara, Shuichi, et al.
Publicado: (2023)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
por: Hirahara, Shuichi, et al.
Publicado: (2025)

Hardness of Learning Boolean Functions from Label Proportions
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
por: Sato, Atsuki, et al.
Publicado: (2025)

Efficient Turing Machine Simulation with Transformers
por: Li, Qian, et al.
Publicado: (2025)

Adaptive and oblivious statistical adversaries are equivalent
por: Blanc, Guy, et al.
Publicado: (2024)

Private graphon estimation via sum-of-squares
por: Chen, Hongjie, et al.
Publicado: (2024)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
por: Gopalan, Parikshit, et al.
Publicado: (2024)

Low-degree phase transitions for detecting a planted clique in sublinear time
por: Mardia, Jay, et al.
Publicado: (2024)

Differentially Private Verification of Distribution Properties
por: Du, Elbert, et al.
Publicado: (2026)

Efficient and Private Property Testing via Indistinguishability
por: Dwork, Cynthia, et al.
Publicado: (2025)

Low-Degree Method Fails to Predict Robust Subspace Recovery
por: Jia, He, et al.
Publicado: (2026)

Is nasty noise actually harder than malicious noise?
por: Blanc, Guy, et al.
Publicado: (2025)

Rate-optimal community detection near the KS threshold via node-robust algorithms
por: Ding, Jingqiu, et al.
Publicado: (2025)

On the Hardness of Approximation of the Fair k-Center Problem
por: Thejaswi, Suhas
Publicado: (2026)

The Computational Complexity of Almost Stable Clustering with Penalties
por: Khodamoradi, Kamyar, et al.
Publicado: (2025)

AdaBoost is not an Optimal Weak to Strong Learner
por: Høgsgaard, Mikael Møller, et al.
Publicado: (2023)

Supersimulators
por: Dwork, Cynthia, et al.
Publicado: (2025)

Self-referential instances of the dominating set problem are irreducible
por: Zhou, Guangyan
Publicado: (2026)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
por: Golowich, Noah, et al.
Publicado: (2024)