LIPIcs.FSTTCS.2022.2.pdf
- Filesize: 342 kB
- 1 pages
Document
Why MCSP Is a More Important Problem Than SAT (Invited Talk)
Author
Rahul Santhanam 
-
Part of:
Volume:
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-12-14
File
Document Identifiers
Author Details
Cite AsGet BibTex
Rahul Santhanam. Why MCSP Is a More Important Problem Than SAT (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.2
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.2
Abstract
CNF Satisfiability (SAT) and its variants are generally considered the central problems in complexity theory, due to their applications in the theory of NP-completeness, logic, verification, probabilistically checkable proofs and parameterized complexity, among other areas. We challenge this conventional wisdom and argue that analysing the Minimum Circuit Size Problem (MCSP) and its relatives is more important from the perspective of fundamental problems in complexity theory, such as complexity lower bounds, minimal assumptions for cryptography, a robust theory of average-case complexity, and optimal results in hardness of approximation.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational complexity and cryptography
Keywords
- Minimum Circuit Size Problem
- Satisfiability
- Cryptography
- Learning
- Approximation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads