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.ICALP.2021.5
URN: urn:nbn:de:0030-drops-140747
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14074/
Go to the corresponding LIPIcs Volume Portal

Pitassi, Toniann

Algebraic Proof Systems (Invited Talk)

pdf-format:
LIPIcs-ICALP-2021-5.pdf (0.3 MB)

Abstract

Given a set of polynomial equations over a field F, how hard is it to prove that they are simultaneously unsolvable? In the last twenty years, algebraic proof systems for refuting such systems of equations have been extensively studied, revealing close connections to both upper bounds (connections between short refutations and efficient approximation algorithms) and lower bounds (connections to fundamental questions in circuit complexity.)
The Ideal Proof System (IPS) is a simple yet powerful algebraic proof system, with very close connections to circuit lower bounds: [Joshua A. Grochow and Toniann Pitassi, 2018] proved that lower bounds for IPS imply VNP ≠ VP, and very recently connections in the other direction have been made, showing that circuit lower bounds imply IPS lower bounds [Rahul Santhanam and Iddo Tzameret, 2021; Yaroslav Alekseev et al., 2020].
In this talk I will survey the landscape of algebraic proof systems, focusing on their connections to complexity theory, derandomization, and standard proposional proof complexity. I will discuss the state-of-the-art lower bounds, as well as the relationship between algebraic systems and textbook style propositional proof systems. Finally we end with open problems, and some recent progress towards proving superpolynomial lower bounds for bounded-depth Frege systems with modular gates (a major open problem in propositional proof complexity).

BibTeX - Entry

@InProceedings{pitassi:LIPIcs.ICALP.2021.5,
  author =	{Pitassi, Toniann},
  title =	{{Algebraic Proof Systems}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{5:1--5:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14074},
  URN =		{urn:nbn:de:0030-drops-140747},
  doi =		{10.4230/LIPIcs.ICALP.2021.5},
  annote =	{Keywords: complexity theory, proof complexity, algebraic circuits}
}

Keywords: complexity theory, proof complexity, algebraic circuits
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

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