Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP

DOI10.1007/978-3-319-24318-4_4zbMath1476.68248OpenAlexW2191626561MaRDI QIDQ3453207

Ruiwen Chen, Rahul Santhanam

Publication date: 20 November 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-24318-4_4

zbMATH Keywords

MAX-SATsatisfiability algorithmMAX-\(k\)-CSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (13)

Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ CHAMP: a multipass algorithm for Max Sat based on saver variables ⋮ Go-MOCE: greedy order method of conditional expectations for Max Sat ⋮ Unnamed Item ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Probabilistic characterization of random Max \(r\)-Sat ⋮ The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$ ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates

Cites Work

• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Optimal 2-constraint satisfaction via sum-product algorithms
• Improved exact algorithms for MAX-SAT
• Mining circuit lower bound proofs for meta-algorithms
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• New exact algorithms for the 2-constraint satisfaction problem
• A new algorithm for optimal 2-constraint satisfaction and its implications
• An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
• Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction
• A measure & conquer approach for the analysis of exact algorithms
• New Bounds for MAX-SAT by Clause Learning
• The Complexity of Satisfiability of Small Depth Circuits
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• The effect of random restrictions on formula size
• Shrinkage of de Morgan formulae under restriction
• MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time

This page was built for publication: Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP