Buchumschlag

Phase Transitions in Decision Problems Over Odd-Sized Alphabets

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Jackson, Andrew
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Explaining the Ubiquity of Phase Transitions in Decision Problems
von: Jackson, Andrew
Veröffentlicht: (2025)

Good Locally Testable Codes with Small Alphabet and Small Query Size
von: First, Uriya, et al.
Veröffentlicht: (2025)

Alphabet Reduction for Reconfiguration Problems
von: Ohsaka, Naoto
Veröffentlicht: (2024)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2025)

Explicit Constant-Alphabet Subspace Design Codes
von: Goyal, Rohan, et al.
Veröffentlicht: (2026)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
von: Basu, Arpon, et al.
Veröffentlicht: (2024)

Higher Hardness Results for the Reconfiguration of Odd Matchings
von: Dorfer, Joseph
Veröffentlicht: (2026)

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
von: Gryaznov, Svyatoslav, et al.
Veröffentlicht: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
von: Minzer, Dor, et al.
Veröffentlicht: (2024)

Partial Minimum Branching Program Size Problem is ETH-hard
von: Glinskih, Ludmila, et al.
Veröffentlicht: (2024)

Nonogram: Complexity of Inference and Phase Transition Behavior
von: Foote, Aaron, et al.
Veröffentlicht: (2025)

Extensively Not P-Bi-Immune promiseBQP-Complete Languages
von: Jackson, Andrew
Veröffentlicht: (2024)

On the Parameterized Complexity of Odd Coloring
von: Bhyravarapu, Sriram, et al.
Veröffentlicht: (2025)

The Constraint Satisfaction Problem Over Multisorted Cores
von: Delic, Dejan, et al.
Veröffentlicht: (2025)

Low-Degree Testing Over Grids
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2023)

Tight Bounds for Quantum Phase Estimation and Related Problems
von: Mande, Nikhil S., et al.
Veröffentlicht: (2023)

Geometric Interpretation of 3-SAT and Phase Transition
von: Gillet, Frederic
Veröffentlicht: (2025)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
von: Ostonov, Azimkhon, et al.
Veröffentlicht: (2023)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
von: Mukhopadhyay, Partha, et al.
Veröffentlicht: (2025)

Low Degree Local Correction Over the Boolean Cube
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2024)

Hazard-free Decision Trees
von: Benson, Deepu, et al.
Veröffentlicht: (2025)

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
von: Bortolotti, Alex, et al.
Veröffentlicht: (2025)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
von: Casteigts, Arnaud, et al.
Veröffentlicht: (2026)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2025)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
von: Bhattacharya, Sreejata Kishor, et al.
Veröffentlicht: (2024)

On complexity of restricted fragments of Decision DNNF
von: Calí, Andrea, et al.
Veröffentlicht: (2025)

From FPT Decision to FPT Enumeration
von: Creignou, Nadia, et al.
Veröffentlicht: (2025)

Holant* Dichotomy on Domain Size 3: A Geometric Perspective
von: Cai, Jin-Yi, et al.
Veröffentlicht: (2025)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
von: Hitchcock, John M.
Veröffentlicht: (2026)

Quasi-Linear Size PCPs with Small Soundness from HDX
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

On Computability of Computable Problems
von: Khaliq, Asad
Veröffentlicht: (2023)

The Stochastic Arrival Problem
von: Webster, Thomas
Veröffentlicht: (2022)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
von: Fortnow, Lance
Veröffentlicht: (2025)

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
von: Bhattacharya, Sreejata Kishor, et al.
Veröffentlicht: (2025)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
von: Chukhin, Nikolai, et al.
Veröffentlicht: (2024)

Separations between Combinatorial Measures for Transitive Functions
von: Chakraborty, Sourav, et al.
Veröffentlicht: (2021)

On the Hardness of the Drone Delivery Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2025)

The Greedy Coin Change Problem
von: Gupta, Shreya, et al.
Veröffentlicht: (2024)

Continuous Defensive Domination Problems
von: Grüne, Christoph, et al.
Veröffentlicht: (2026)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
von: Alhamdan, Yousef M.
Veröffentlicht: (2025)