Image de couverture de livre

Hazard-free Decision Trees

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Benson, Deepu, Komarath, Balagopal, Sarma, Jayalal, Soumya, Nalli Sai
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Sensitivity and Query Complexity under Uncertainty
par: Benson, Deepu, et autres
Publié: (2025)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
par: Nalli, Sai Soumya, et autres
Publié: (2026)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
par: Komarath, Balagopal, et autres
Publié: (2026)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
par: Komarath, Balagopal, et autres
Publié: (2025)

Bounds for Hardness Condensation in the Query Model
par: Kayal, Chandrima, et autres
Publié: (2026)

Range Avoidance in Boolean Circuits via Turan-type Bounds
par: Kuntewar, Neha, et autres
Publié: (2025)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
par: Bhattacharjee, Sutanay, et autres
Publié: (2026)

Almost-catalytic Computation
par: Bisoyi, Sagar, et autres
Publié: (2024)

Small Hazard-free Transducers
par: Bund, Johannes, et autres
Publié: (2018)

On the Complexity of Hazard-Free Formulas
par: Arazi, Leah London, et autres
Publié: (2024)

One-Way Functions and Polynomial Time Dimension
par: Nandakumar, Satyadev, et autres
Publié: (2024)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
par: Ostonov, Azimkhon, et autres
Publié: (2023)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
par: Alhamdan, Yousef M.
Publié: (2025)

Decision Tree Learning on Product Spaces
par: Moakahr, Arshia Soltani, et autres
Publié: (2026)

Baby PIH: Parameterized Inapproximability of Min CSP
par: Guruswami, Venkatesan, et autres
Publié: (2023)

On complexity of restricted fragments of Decision DNNF
par: Calí, Andrea, et autres
Publié: (2025)

From FPT Decision to FPT Enumeration
par: Creignou, Nadia, et autres
Publié: (2025)

Explaining the Ubiquity of Phase Transitions in Decision Problems
par: Jackson, Andrew
Publié: (2025)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
par: Fortnow, Lance
Publié: (2025)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
par: Jackson, Andrew
Publié: (2025)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
par: Ostonov, Azimkhon, et autres
Publié: (2024)

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
par: Cornelissen, Arjan, et autres
Publié: (2022)

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
par: Bhattiprolu, Vijay, et autres
Publié: (2025)

Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width
par: Razgon, Igor
Publié: (2025)

A quantum neural network framework for scalable quantum circuit approximation of unitary matrices
par: Sarkar, Rohit Sarma, et autres
Publié: (2024)

Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
par: Hodur, Nadzieja, et autres
Publié: (2025)

Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
par: Grillo, Sebastian Alberto, et autres
Publié: (2026)

Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions
par: Junchi, Ma, et autres
Publié: (2024)

Superconstant Inapproximability of Decision Tree Learning
par: Koch, Caleb, et autres
Publié: (2024)

Orbit-blocking words in free groups
par: Koch-Hyde, Lucy, et autres
Publié: (2025)

Improved Hardness of Approximation for Geometric Bin Packing
par: Ray, Arka, et autres
Publié: (2023)

Active Learning for Decision Trees with Provable Guarantees
par: Moakhar, Arshia Soltani, et autres
Publié: (2026)

Value Iteration with Guessing for Markov Chains and Markov Decision Processes
par: Chatterjee, Krishnendu, et autres
Publié: (2025)

Explaining Decisions in ML Models: a Parameterized Complexity Analysis
par: Ordyniak, Sebastian, et autres
Publié: (2024)

On the complexity of estimating ground state entanglement and free energy
par: Gharibian, Sevag, et autres
Publié: (2025)

Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
par: Khadiev, Kamil, et autres
Publié: (2017)

Direct Sums for Parity Decision Trees
par: Besselman, Tyler, et autres
Publié: (2024)

On the Complexity of Problems on Tree-structured Graphs
par: Bodlaender, Hans L., et autres
Publié: (2022)

Isomorphism Testing of Rooted Trees in Linear Time
par: Lindeberg, Anna
Publié: (2024)

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
par: Delavenne, Hugo, et autres
Publié: (2024)