The hardness of decision tree complexity

DOI10.4230/LIPICS.STACS.2025.66MaRDI QIDQ7287805zbMATH OpenFDO

Authors Bruno Loff, Alexey Milovanov

Publication date 24 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2025.66

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Algorithms for Boolean Function Query Properties
• Deterministic communication vs. partition number
• Exact learning when irrelevant variables abound
• scientific article; zbMATH DE number 3860199 (Why is no real title available?)
• Lifting Theorems for Equality
• Lower bounds for clique vs. independent set
• Minimization of decision trees is hard to approximate
• On uniformity within \(NC^ 1\)
• Properly learning decision trees with queries is NP-hard
• Separation of the monotone NC hierarchy
• Simulation theorems via pseudo-random properties
• Theory of Cryptography

This page was built for publication: The hardness of decision tree complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7287805)