Copertina

Geometric Interpretation of 3-SAT and Phase Transition

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Gillet, Frederic
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

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

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

Improved Hardness of Approximation for Geometric Bin Packing
di: Ray, Arka, et al.
Pubblicazione: (2023)

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

An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication
di: Sun, Yinqi
Pubblicazione: (2026)

Hardness and Algorithmic Results for Roman \{3\}-Domination
di: Reddy, Sangam Balchandar
Pubblicazione: (2025)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
di: Michel, Lukas, et al.
Pubblicazione: (2023)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
di: Khanna, Sanjeev, et al.
Pubblicazione: (2026)

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT
di: Kızıldağ, Eren C.
Pubblicazione: (2023)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
di: Sarriguren, Alfredo Goñi
Pubblicazione: (2024)

The Complexity of Transitively Orienting Temporal Graphs
di: Mertzios, George B., et al.
Pubblicazione: (2021)

SAT Requires Exhaustive Search
di: Xu, Ke, et al.
Pubblicazione: (2023)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
di: Greilhuber, Jakob, et al.
Pubblicazione: (2025)

The Trichotomy of Regular Property Testing
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

Downward self-reducibility in the total function polynomial hierarchy
di: Gajulapalli, Karthik, et al.
Pubblicazione: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
di: Fujie, Yuto, et al.
Pubblicazione: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
di: Moroie, Gregory
Pubblicazione: (2025)

Precoloring extension with demands on paths
di: Das, Arun Kumar, et al.
Pubblicazione: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
di: Gholizadeh, Hossein, et al.
Pubblicazione: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
di: Herrmann, Anton, et al.
Pubblicazione: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
di: Maalouly, Nicolas El, et al.
Pubblicazione: (2025)

k-SUM Hardness Implies Treewidth-SETH
di: Lampis, Michael
Pubblicazione: (2025)

Efficient Catalytic Graph Algorithms
di: Cook, James, et al.
Pubblicazione: (2025)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
di: Dhar, Anubhav, et al.
Pubblicazione: (2025)

Scheduling Problems with Constrained Rejections
di: Davies, Sami, et al.
Pubblicazione: (2025)

Graded Projection Recursion (GPR): Corrections, Obstructions, and Conservative Approximate Matrix Multiplication
di: Uhlmann, Jeffrey
Pubblicazione: (2025)

Parameterized Complexity of Vehicle Routing
di: Döring, Michelle, et al.
Pubblicazione: (2025)

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
di: Curticapean, Radu, et al.
Pubblicazione: (2025)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2025)

Most Juntas Saturate the Hardcore Lemma
di: Kumar, Vinayak M.
Pubblicazione: (2025)

FPT Parameterisations of Fractional and Generalised Hypertree Width
di: Lanzinger, Matthias, et al.
Pubblicazione: (2025)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
di: Kluk, Kacper, et al.
Pubblicazione: (2025)