Cover Image

Maximum And- vs. Even-SAT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nakajima, Tamio-Vesa, Živný, Stanislav
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An approximation algorithm for Maximum DiCut vs. Cut
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

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

A Dichotomy for Maximum PCSPs on Graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

On the complexity of symmetric vs. functional PCSPs
by: Nakajima, Tamio-Vesa, et al.
Published: (2022)

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

A logarithmic approximation of linearly ordered colourings
by: Håstad, Johan, et al.
Published: (2024)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
by: Ciardo, Lorenzo, et al.
Published: (2023)

Virtual-Memory Powersort
by: Moltmann, Finn, et al.
Published: (2026)

Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs
by: Alaoui, Ziad Ismaili, et al.
Published: (2026)

Additive Sparsification of CSPs
by: Pelleg, Eden, et al.
Published: (2021)

Semidefinite programming and linear equations vs. homomorphism problems
by: Ciardo, Lorenzo, et al.
Published: (2023)

The periodic structure of local consistency
by: Ciardo, Lorenzo, et al.
Published: (2024)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
by: Shao, Shuai, et al.
Published: (2023)

New Algorithms for #2-SAT and #3-SAT
by: Peng, Junqiang, et al.
Published: (2025)

An Improved Algorithm for Sparse Instances of SAT
by: Jain, Sanjay, et al.
Published: (2024)

A Polynomial Decision for 3-SAT
by: Weiss, Angela
Published: (2022)

Computing diverse pair of solutions for tractable SAT
by: Gima, Tatsuya, et al.
Published: (2024)

A Polynomial time Algorithm for 3SAT
by: Du, Lizhi
Published: (2010)

New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
by: Jain, Sanjay, et al.
Published: (2026)

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

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
by: Bringmann, Karl, et al.
Published: (2024)

Odd and Even Harder Problems on Cycle-Factors
by: Hörsch, Florian, et al.
Published: (2025)

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

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
by: Bhattacharya, Sayan, et al.
Published: (2024)

On the Parameterized Complexity of Diverse SAT
by: Misra, Neeldhara, et al.
Published: (2024)

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

Listing Even Cycles Faster than the Submodular-Width Barrier
by: Nakos, Vasileios, et al.
Published: (2026)

FPT Approximations for Connected Maximum Coverage
by: Inamdar, Tanmay, et al.
Published: (2026)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
by: Manurangsi, Pasin
Published: (2024)

Quantum Graph-State Synthesis with SAT
by: Brand, Sebastiaan, et al.
Published: (2023)

Even Faster Algorithm for the Chamfer Distance
by: Feng, Ying, et al.
Published: (2025)

On the Efficient Discovery of Maximum $k$-Defective Biclique
by: Cui, Donghang, et al.
Published: (2025)

Half-Approximating Maximum Dicut in the Streaming Setting
by: Azarmehr, Amir, et al.
Published: (2025)

Improved Approximation Algorithm for Maximum Balanced Biclique
by: Manurangsi, Pasin
Published: (2026)

Semi-Robust Communication Complexity of Maximum Matching
by: Huete, Gabriel Cipriani, et al.
Published: (2025)

Acceleration for Distributed Transshipment and Parallel Maximum Flow
by: Grunau, Christoph, et al.
Published: (2025)

Approximating Maximum Matching Requires Almost Quadratic Time
by: Behnezhad, Soheil, et al.
Published: (2024)

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
by: Ene, Alina, et al.
Published: (2025)

Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries
by: Kothalawala, Buddhi, et al.
Published: (2026)

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