DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2022.100

Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems

Authors: Theodoros Papamakarios and Alexander Razborov

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract

We identify two new big clusters of proof complexity measures equivalent up to polynomial and log n factors. The first cluster contains, among others, the logarithm of tree-like resolution size, regularized (that is, multiplied by the logarithm of proof length) clause and monomial space, and clause space, both ordinary and regularized, in regular and tree-like resolution. As a consequence, separating clause or monomial space from the (logarithm of) tree-like resolution size is the same as showing a strong trade-off between clause or monomial space and proof length, and is the same as showing a super-critical trade-off between clause space and depth. The second cluster contains width, Σ₂ space (a generalization of clause space to depth 2 Frege systems), both ordinary and regularized, as well as the logarithm of tree-like size in the system R(log). As an application of some of these simulations, we improve a known size-space trade-off for polynomial calculus with resolution. In terms of lower bounds, we show a quadratic lower bound on tree-like resolution size for formulas refutable in clause space 4. We introduce on our way yet another proof complexity measure intermediate between depth and the logarithm of tree-like size that might be of independent interest.

Cite as

Theodoros Papamakarios and Alexander Razborov. Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 100:1-100:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{papamakarios_et_al:LIPIcs.ICALP.2022.100,
  author =	{Papamakarios, Theodoros and Razborov, Alexander},
  title =	{{Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{100:1--100:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.100},
  URN =		{urn:nbn:de:0030-drops-164419},
  doi =		{10.4230/LIPIcs.ICALP.2022.100},
  annote =	{Keywords: Proof Complexity, Resolution, Size-Space Trade-offs}
}

Document

DOI: 10.4230/DagSemProc.10211.2

Diameter of Polyhedra: Limits of Abstraction

Authors: Friedrich Eisenbrand, Nicolai Hähnle, Alexander Razborov, and Thomas Rothvoß

Published in: Dagstuhl Seminar Proceedings, Volume 10211, Flexible Network Design (2010)

Abstract

We investigate the diameter of a natural abstraction of the $1$-skeleton of polyhedra. Even if this abstraction is more general than other abstractions previously studied in the literature, known upper bounds on the diameter of polyhedra continue to hold here. On the other hand, we show that this abstraction has its limits by providing an almost quadratic lower bound.

Cite as

Friedrich Eisenbrand, Nicolai Hähnle, Alexander Razborov, and Thomas Rothvoß. Diameter of Polyhedra: Limits of Abstraction. In Flexible Network Design. Dagstuhl Seminar Proceedings, Volume 10211, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{eisenbrand_et_al:DagSemProc.10211.2,
  author =	{Eisenbrand, Friedrich and H\"{a}hnle, Nicolai and Razborov, Alexander and Rothvo{\ss}, Thomas},
  title =	{{Diameter of Polyhedra: Limits of Abstraction}},
  booktitle =	{Flexible Network Design},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10211},
  editor =	{Anupam Gupta and Stefano Leonardi and Berthold V\"{o}cking and Roger Wattenhofer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10211.2},
  URN =		{urn:nbn:de:0030-drops-27247},
  doi =		{10.4230/DagSemProc.10211.2},
  annote =	{Keywords: Polyhedra, Graphs}
}

Search Results

Documents authored by Razborov, Alexander

Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems

Abstract

Cite as

Diameter of Polyhedra: Limits of Abstraction

Abstract

Cite as

Thanks for your feedback!

Could not send message