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

Ruiwen Chen, Rahul Santhanam

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We give improved deterministic algorithms solving sparse instances of MAX-SAT and MAX-k-CSP. For instances with n variables and cn clauses (constraints), we give algorithms running in time poly(n)⋅2n(1−μ) for
μ=Ω(1/c) and polynomial space solving MAX-SAT and MAX-k-SAT,
μ=Ω(1√c) and exponential space solving MAX-SAT and MAX-k-SAT,
μ=Ω(1/ck2) and polynomial space solving MAX-k-CSP,
μ=Ω(1/√ck3) and exponential space solving MAX-k-CSP.
The previous MAX-SAT algorithms have savings μ=Ω(1/c2log2c) for running in polynomial space [15] and μ=Ω(1/clogc) for exponential space [5]. We also give an algorithm with improved savings for satisfiability of depth-2 threshold circuits with cn wires.
Original languageEnglish
Title of host publicationTheory and Applications of Satisfiability Testing -- SAT 2015
EditorsMarijn Heule, Sean Weaver
Place of PublicationCham
PublisherSpringer International Publishing
Pages33-45
Number of pages13
ISBN (Electronic)978-3-319-24318-4
ISBN (Print)978-3-319-24317-7
DOIs
Publication statusPublished - 27 Oct 2015
Event18th International Conference on Theory and Applications of Satisfiability Testing - Austin, United States
Duration: 24 Sep 201527 Sep 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
Volume9340
ISSN (Print)1611-3349
ISSN (Electronic)0302-9743

Conference

Conference18th International Conference on Theory and Applications of Satisfiability Testing
Abbreviated titleSAT 2015
CountryUnited States
CityAustin
Period24/09/1527/09/15

Fingerprint Dive into the research topics of 'Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP'. Together they form a unique fingerprint.

Cite this