Imagen de Portada

On the Mysteries of MAX NAE-SAT

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Brakensiek, Joshua, Huang, Neng, Potechin, Aaron, Zwick, Uri
Formato:	Preprint
Publicado:	2020
Materias:	Computational Complexity Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

MAX BISECTION might be harder to approximate than MAX CUT
por: Brakensiek, Joshua, et al.
Publicado: (2025)

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
por: Brakensiek, Joshua, et al.
Publicado: (2026)

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

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
por: Brakensiek, Joshua, et al.
Publicado: (2026)

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

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
por: Chen, Xi, et al.
Publicado: (2026)

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

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

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

On Optimal Testing of Linearity
por: Arora, Vipul, et al.
Publicado: (2024)

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

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

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
por: DeHaan, Ian, et al.
Publicado: (2025)

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

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

Optimal Parallel Basis Finding in Graphic and Related Matroids
por: Khanna, Sanjeev, et al.
Publicado: (2025)

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

Bounded Independence Edge Sampling for Combinatorial Graph Properties
por: Putterman, Aaron, et al.
Publicado: (2026)

The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand
por: Caragiannis, Ioannis, et al.
Publicado: (2026)

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

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
por: Anand, Aditya, et al.
Publicado: (2025)

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

Sublinear-query relative-error testing of halfspaces
por: Chen, Xi, et al.
Publicado: (2026)

Halfspaces are hard to test with relative error
por: Chen, Xi, et al.
Publicado: (2025)

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

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

Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing
por: Courtney, Joshua M.
Publicado: (2026)

Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing
por: Courtney, Joshua M.
Publicado: (2026)

SAT Requires Exhaustive Search
por: Xu, Ke, et al.
Publicado: (2023)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
por: Enright, Jessica, et al.
Publicado: (2020)

Improved Algorithm for Permutation Testing
por: Zhang, Xiaojin
Publicado: (2020)

Removable Online Knapsack and Advice
por: Böckenhauer, Hans-Joachim, et al.
Publicado: (2020)

On girth and the parameterized complexity of token sliding and token jumping
por: Bartier, Valentin, et al.
Publicado: (2020)

The Query Complexity of Local Search and Brouwer in Rounds
por: Brânzei, Simina, et al.
Publicado: (2020)

Neighborhood-Aware Graph Labeling Problem
por: Shahverdikondori, Mohammad, et al.
Publicado: (2026)

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

Lazy Kronecker Product
por: Song, Zhao
Publicado: (2026)

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

Complexity of Local Search for Euclidean Clustering Problems
por: Manthey, Bodo, et al.
Publicado: (2023)

Can You Link Up With Treewidth?
por: Curticapean, Radu, et al.
Publicado: (2024)