Cover Image

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Austrin, Per, Bercea, Ioana O., Goswami, Mayank, Limaye, Nutan, Srinivasan, Adarsh
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

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

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

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
by: Tate, Elise, et al.
Published: (2025)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
by: Mao, Songtao
Published: (2026)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

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

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)

Analyzing and Leveraging the $k$-Sensitivity of LZ77
by: Bathie, Gabriel, et al.
Published: (2026)

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

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

A Note on Approximability of Densest At-Least-k-Subgraph
by: Laekhanukit, Bundit, et al.
Published: (2026)

An alignment problem
by: McDaniel, Emma L., et al.
Published: (2024)

Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
by: Holtgrefe, Niels, et al.
Published: (2026)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)

Improved Algorithm for Permutation Testing
by: Zhang, Xiaojin
Published: (2020)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Algorithms and Hardness for Estimating Statistical Similarity
by: Bhattacharyya, Arnab, et al.
Published: (2025)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Impossibility of Depth Reduction in Explainable Clustering
by: Deng, Chengyuan, et al.
Published: (2023)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
by: de Berg, Mark, et al.
Published: (2025)

Constructing self-referential instances for the clique problem
by: Li, Jiaqi, et al.
Published: (2026)

Parameterized Algorithms for Editing to Uniform Cluster Graph
by: Gaikwad, Ajinkya, et al.
Published: (2024)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

Exact Algorithms for Distance to Unique Vertex Cover
by: Fioravantes, Foivos, et al.
Published: (2025)

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

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)

From Amortized to Worst Case Delay in Enumeration Algorithms
by: Capelli, Florent, et al.
Published: (2021)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
by: Clinch, Katie, et al.
Published: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
by: Chmel, Petr, et al.
Published: (2026)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
by: Ducoffe, Guillaume
Published: (2026)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
by: Yang, Yang
Published: (2025)

On connections between k-coloring and Euclidean k-means
by: Aman, Enver, et al.
Published: (2024)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
by: Kumar, Mrinal, et al.
Published: (2024)