Abstract
dc:description.abstractThis 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