Cover Image

Explaining the Ubiquity of Phase Transitions in Decision Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Jackson, Andrew
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
by: Jackson, Andrew
Published: (2025)

Explaining Decisions in ML Models: a Parameterized Complexity Analysis
by: Ordyniak, Sebastian, et al.
Published: (2024)

Nonogram: Complexity of Inference and Phase Transition Behavior
by: Foote, Aaron, et al.
Published: (2025)

Extensively Not P-Bi-Immune promiseBQP-Complete Languages
by: Jackson, Andrew
Published: (2024)

Tight Bounds for Quantum Phase Estimation and Related Problems
by: Mande, Nikhil S., et al.
Published: (2023)

Geometric Interpretation of 3-SAT and Phase Transition
by: Gillet, Frederic
Published: (2025)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2023)

Hazard-free Decision Trees
by: Benson, Deepu, et al.
Published: (2025)

On complexity of restricted fragments of Decision DNNF
by: Calí, Andrea, et al.
Published: (2025)

From FPT Decision to FPT Enumeration
by: Creignou, Nadia, et al.
Published: (2025)

Additive Models Explained: A Computational Complexity Approach
by: Bassan, Shahaf, et al.
Published: (2025)

On Computability of Computable Problems
by: Khaliq, Asad
Published: (2023)

The Stochastic Arrival Problem
by: Webster, Thomas
Published: (2022)

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

Separations between Combinatorial Measures for Transitive Functions
by: Chakraborty, Sourav, et al.
Published: (2021)

On the Hardness of the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2025)

The Greedy Coin Change Problem
by: Gupta, Shreya, et al.
Published: (2024)

Continuous Defensive Domination Problems
by: Grüne, Christoph, et al.
Published: (2026)

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

Reductions Between Code Equivalence Problems
by: Cheraghchi, Mahdi, et al.
Published: (2025)

Total Search Problems in $\mathsf{ZPP}$
by: Fleming, Noah, et al.
Published: (2025)

Inverse Intersections for Boolean Satisfiability Problems
by: Homer, Paul W.
Published: (2025)

Parameterized Complexity of the Star Decomposition Problem
by: Hajebi, Sahab, et al.
Published: (2024)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)

The 2-Attractor Problem is NP-Complete
by: Fuchs, Janosch, et al.
Published: (2023)

On the Exact Matching Problem in Dense Graphs
by: Maalouly, Nicolas El, et al.
Published: (2024)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2024)

Provably Explaining Neural Additive Models
by: Bassan, Shahaf, et al.
Published: (2026)

On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
by: Devillers, Raymond, et al.
Published: (2022)

Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
by: Casteigts, Arnaud, et al.
Published: (2024)

Hard-to-Sample Distributions from Robust Extractors
by: Byramji, Farzan, et al.
Published: (2026)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)

Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width
by: Razgon, Igor
Published: (2025)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

The Line Traveling Salesman and Repairman Problem with Collaboration
by: Golak, Julian, et al.
Published: (2025)

Geometry Of The Subset Sum Problem -- Part I
by: Bollepalli, Srinivas Balaji
Published: (2025)

Maximum Matching and Related Problems in Catalytic Logspace
by: Chakraborty, Srijan, et al.
Published: (2026)

No Complete Problem for Constant-Cost Randomized Communication
by: Fang, Yuting, et al.
Published: (2024)

P-time Algorithms for Typical #EO Problems
by: Meng, Boning, et al.
Published: (2024)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)