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

Ruiwen Chen; Rahul Santhanam

doi:10.1007/978-3-319-24318-4_4

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

Ruiwen Chen
, Rahul Santhanam

Research output: Chapter in Book/Report/Conference proceeding › Conference 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)⋅2^n(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/ck²) and polynomial space solving MAX-k-CSP,
μ=Ω(1/√ck³) and exponential space solving MAX-k-CSP.
The previous MAX-SAT algorithms have savings μ=Ω(1/c²log²c) 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 language	English
Title of host publication	Theory and Applications of Satisfiability Testing -- SAT 2015
Editors	Marijn Heule, Sean Weaver
Place of Publication	Cham
Publisher	Springer
Pages	33-45
Number of pages	13
ISBN (Electronic)	978-3-319-24318-4
ISBN (Print)	978-3-319-24317-7
DOIs	https://doi.org/10.1007/978-3-319-24318-4_4
Publication status	Published - 27 Oct 2015
Event	18th International Conference on Theory and Applications of Satisfiability Testing - Austin, United States Duration: 24 Sept 2015 → 27 Sept 2015

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer, Cham
Volume	9340
ISSN (Print)	1611-3349
ISSN (Electronic)	0302-9743

Conference

Conference	18th International Conference on Theory and Applications of Satisfiability Testing
Abbreviated title	SAT 2015
Country/Territory	United States
City	Austin
Period	24/09/15 → 27/09/15

Access to Document

10.1007/978-3-319-24318-4_4

TR15-112Accepted author manuscript, 639 KB

ALUnif - Algorithms and Lower Bounds: A Unified Approach
Santhanam, R. (Principal Investigator)
EU government bodies
1/03/14 → 28/02/19
Project: Research

Cite this

@inproceedings{9d90d5ae1aa341ddabe4d70f7f18624e,

title = "Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP",

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.",

author = "Ruiwen Chen and Rahul Santhanam",

year = "2015",

month = oct,

day = "27",

doi = "10.1007/978-3-319-24318-4\_4",

language = "English",

isbn = "978-3-319-24317-7",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "33--45",

editor = "Marijn Heule and Sean Weaver",

booktitle = "Theory and Applications of Satisfiability Testing -- SAT 2015",

address = "United Kingdom",

note = "18th International Conference on Theory and Applications of Satisfiability Testing, SAT 2015 ; Conference date: 24-09-2015 Through 27-09-2015",

}

Chen, R & Santhanam, R 2015, Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP. in M Heule & S Weaver (eds), Theory and Applications of Satisfiability Testing -- SAT 2015. Lecture Notes in Computer Science , vol. 9340, Springer, Cham, pp. 33-45, 18th International Conference on Theory and Applications of Satisfiability Testing, Austin, Texas, United States, 24/09/15. https://doi.org/10.1007/978-3-319-24318-4_4

TY - GEN

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

AU - Chen, Ruiwen

AU - Santhanam, Rahul

PY - 2015/10/27

Y1 - 2015/10/27

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-24318-4_4

DO - 10.1007/978-3-319-24318-4_4

M3 - Conference contribution

SN - 978-3-319-24317-7

T3 - Lecture Notes in Computer Science

SP - 33

EP - 45

BT - Theory and Applications of Satisfiability Testing -- SAT 2015

A2 - Heule, Marijn

A2 - Weaver, Sean

PB - Springer

CY - Cham

T2 - 18th International Conference on Theory and Applications of Satisfiability Testing

Y2 - 24 September 2015 through 27 September 2015

ER -

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

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

ALUnif - Algorithms and Lower Bounds: A Unified Approach

Cite this