Cover Image

A Hypergraph Container Method on Spread SAT: Approximation and Speedup

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Han, Zicheng, Lin, Yupeng, Ma, Jie, Zhang, Xiande
Format:	Preprint
Published:	2026
Subjects:	Combinatorics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximately counting maximal independent set is equivalent to #SAT
by: Zhang, Hao, et al.
Published: (2024)

Bisection Width, Discrepancy, and Eigenvalues of Hypergraphs
by: Räty, Eero, et al.
Published: (2024)

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, et al.
Published: (2025)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
by: Gan, Luyining, et al.
Published: (2023)

On the Keevash-Knox-Mycroft Conjecture
by: Gan, Luyining, et al.
Published: (2022)

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
by: Li, Zhengyu, et al.
Published: (2023)

On the satisfiability of random $3$-SAT formulas with $k$-wise independent clauses
by: Caragiannis, Ioannis, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VI
by: Bhangale, Amey, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
by: Bhangale, Amey, et al.
Published: (2024)

On Approximability of Satisfiable k-CSPs: IV
by: Bhangale, Amey, et al.
Published: (2023)

A Fast Coloring Oracle for Average Case Hypergraphs
by: Marcussen, Cassandra, et al.
Published: (2025)

Hypergraph Samplers: Typical and Worst Case Behavior
by: Alev, Vedat Levi, et al.
Published: (2026)

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
by: Gribanov, Dmitry, et al.
Published: (2022)

Approximate cycle double cover
by: Ghanbari, Babak, et al.
Published: (2025)

The Chromatic Number of Kneser Hypergraphs via Consensus Division
by: Haviv, Ishay
Published: (2023)

Variants of VC dimension and their applications to dynamics
by: Gao, Guorong, et al.
Published: (2023)

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

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

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

Quantum k-SAT Related Hypergraph Problems
by: Kremer, Simon-Luca, et al.
Published: (2025)

Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
by: Minevich, Igor, et al.
Published: (2024)

A Note on the Complexity of Directed Clique
by: Gutowski, Grzegorz, et al.
Published: (2026)

A near-optimal Quadratic Goldreich-Levin algorithm
by: Briët, Jop, et al.
Published: (2025)

A combinatorial view of Holant problems on higher domains
by: Liu, Yin
Published: (2024)

A Subexponential Reduction from Product Partition to Subset Sum
by: Costandin, Marius
Published: (2024)

A criterion for Andrásfai--Erdős--Sós type theorems and applications
by: Hou, Jianfeng, et al.
Published: (2024)

Finding hardness reductions automatically using SAT solvers
by: Bergold, Helena, et al.
Published: (2024)

Lions and Contamination: Trees and General Graphs
by: Kim, Dohoon, et al.
Published: (2026)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
by: Grüne, Christoph, et al.
Published: (2026)

Classification of Non-redundancy of Boolean Predicates of Arity 4
by: Brakensiek, Joshua, et al.
Published: (2026)

Between proper and square coloring of planar graphs, hardness and extremal graphs
by: Delépine, Thomas
Published: (2026)

The Lens of Abelian Embeddings
by: Minzer, Dor
Published: (2026)

Communication Complexity of Disjointness under Product Distributions
by: Hunter, Zach, et al.
Published: (2026)

Low-Degree Polynomials Are Good Extractors
by: Alrabiah, Omar, et al.
Published: (2024)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

Refuting Perfect Matchings in Spectral Expanders is Hard
by: Biswas, Ari, et al.
Published: (2025)

Direct Product Primality Testing of Graphs is GI-hard
by: Calderoni, Luca, et al.
Published: (2020)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Hunting a rabbit: complexity, approximability and some characterizations
by: Ben-Ameur, Walid, et al.
Published: (2025)