Cover Image

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Kızıldağ, Eren C.
Format:	Preprint
Published:	2023
Subjects:	Probability Computational Complexity Data Structures and Algorithms Mathematical Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sharp Online Hardness for Large Balanced Independent Sets
by: Dhawan, Abhishek, et al.
Published: (2025)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2026)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
by: R., Abhishek Hegade K., et al.
Published: (2025)

Stable algorithms cannot reliably find isolated perceptron solutions
by: Gong, Shuyang, et al.
Published: (2026)

Discrepancy Algorithms for the Binary Perceptron
by: Li, Shuangping, et al.
Published: (2024)

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

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
by: Huang, Neng, et al.
Published: (2024)

Parameter estimation for Gibbs distributions
by: Harris, David G., et al.
Published: (2020)

Microscopic Structure of Random 3-SAT: A Discrete Geometric Approach to Phase Transitions and Algorithmic Complexity
by: Zhan, Yongjian
Published: (2026)

Random tensor isomorphism under orthogonal and unitary actions
by: Chizewer, Jeremy, et al.
Published: (2026)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
by: Gamarnik, David, et al.
Published: (2026)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
by: Sohn, Youngtak, et al.
Published: (2025)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
by: Austrin, Per, et al.
Published: (2024)

A computational phase transition for learning-to-sample from Ising models
by: Risteski, Andrej, et al.
Published: (2026)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
by: Buhrman, Harry, et al.
Published: (2025)

Fast relaxation of the random field Ising dynamics
by: Alaoui, Ahmed El, et al.
Published: (2023)

Log-Sobolev inequality for near critical Ising models
by: Bauerschmidt, Roland, et al.
Published: (2022)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
by: Bedert, Benjamin, et al.
Published: (2025)

$O(n +f(k))$: Truly Linear FPT
by: Bumpus, Benjamin Merlin, et al.
Published: (2026)

Maximum $k$- vs. $\ell$-colourings of graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2023)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
by: Moka, Sarat, et al.
Published: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
by: Li, Tiange, et al.
Published: (2026)

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

The complexity of strong conflict-free vertex-connection $k$-colorability
by: Hsieh, Sun-Yuan, et al.
Published: (2024)

Fast mixing in Ising models with a negative spectral outlier via Gaussian approximation
by: Mikulincer, Dan, et al.
Published: (2025)

Randomized Communication and Implicit Graph Representations
by: Harms, Nathaniel, et al.
Published: (2021)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
by: Scheder, Dominik, et al.
Published: (2025)

SAT Requires Exhaustive Search
by: Xu, Ke, et al.
Published: (2023)

On the Mysteries of MAX NAE-SAT
by: Brakensiek, Joshua, et al.
Published: (2020)

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

Polynomial-time sampling despite disorder chaos
by: Ma, Eric, et al.
Published: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

Some easy optimization problems have the overlap-gap property
by: Li, Shuangping, et al.
Published: (2024)

Certifying and learning quantum Ising Hamiltonians
by: Bluhm, Andreas, et al.
Published: (2025)

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

Further Explanations on "SAT Requires Exhaustive Search"
by: Dong, Qingxiu, et al.
Published: (2024)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
by: Kocurek, Nicholas, et al.
Published: (2026)

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2024)

A note on approximating the average degree of bounded arboricity graphs
by: Eden, Talya, et al.
Published: (2026)