Back to search

Georgia Institute of Technology

Proofdoors and efficiency of CDCL solvers

Abstract

dc:description.abstract

This thesis studies the gap between the worst-case complexity of SAT and the strong practical performance of CDCL solvers. It builds on the notion of proofdoors, a structural decomposition of CNF formulas into sequential components connected by interpolants. We show that formulas admitting small proofdoors have short resolution refutations, and that suitably configured CDCL solvers can construct such proofs efficiently. We also establish a connection between proofdoors and the CacheSAT algorithm via clause-variable incidence pathwidth, and show how CDCL can simulate such executions. As an application, we prove that SAT encodings of floating-point addition commutativity admit small proofdoors, explaining their tractability.

Degree

thesis:*
Name thesis:degree_name
Computer Science, MS
Department thesis:degree_department
Computer Science
Grantor
Georgia Institute of Technology
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Singh, Sunidhi
Advisor dc:contributor.advisor
  • Ganesh, Vijay
Committee members dc:contributor.committeemember
  • Marc Vinyals
  • Bansal, Suguman

Rights

Language dc:language.iso
English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/81592

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Singh, Sunidhi. Proofdoors and efficiency of CDCL solvers. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/81592