License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.2
URN: urn:nbn:de:0030-drops-173943
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17394/
Go to the corresponding LIPIcs Volume Portal

Santhanam, Rahul

Why MCSP Is a More Important Problem Than SAT (Invited Talk)

pdf-format:
LIPIcs-FSTTCS-2022-2.pdf (0.3 MB)

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.

BibTeX - Entry

@InProceedings{santhanam:LIPIcs.FSTTCS.2022.2,
  author =	{Santhanam, Rahul},
  title =	{{Why MCSP Is a More Important Problem Than SAT}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17394},
  URN =		{urn:nbn:de:0030-drops-173943},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.2},
  annote =	{Keywords: Minimum Circuit Size Problem, Satisfiability, Cryptography, Learning, Approximation}
}

Keywords: Minimum Circuit Size Problem, Satisfiability, Cryptography, Learning, Approximation
Collection: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI