License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.72
URN: urn:nbn:de:0030-drops-117573
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11757/
Go to the corresponding LIPIcs Volume Portal

Lagarde, Guillaume ; Nordström, Jakob ; Sokolov, Dmitry ; Swernofsky, Joseph

Trade-Offs Between Size and Degree in Polynomial Calculus

pdf-format:
LIPIcs-ITCS-2020-72.pdf (0.5 MB)

Abstract

Building on [Clegg et al. '96], [Impagliazzo et al. '99] established that if an unsatisfiable k-CNF formula over n variables has a refutation of size S in the polynomial calculus resolution proof system, then this formula also has a refutation of degree k + O(√(n log S)). The proof of this works by converting a small-size refutation into a small-degree one, but at the expense of increasing the proof size exponentially. This raises the question of whether it is possible to achieve both small size and small degree in the same refutation, or whether the exponential blow-up is inherent. Using and extending ideas from [Thapen '16], who studied the analogous question for the resolution proof system, we prove that a strong size-degree trade-off is necessary.

BibTeX - Entry

@InProceedings{lagarde_et_al:LIPIcs:2020:11757,
  author =	{Guillaume Lagarde and Jakob Nordstr{\"o}m and Dmitry Sokolov and Joseph Swernofsky},
  title =	{{Trade-Offs Between Size and Degree in Polynomial Calculus}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{72:1--72:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Thomas Vidick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11757},
  URN =		{urn:nbn:de:0030-drops-117573},
  doi =		{10.4230/LIPIcs.ITCS.2020.72},
  annote =	{Keywords: proof complexity, polynomial calculus, polynomial calculus resolution, PCR, size-degree trade-off, resolution, colored polynomial local search}
}

Keywords: proof complexity, polynomial calculus, polynomial calculus resolution, PCR, size-degree trade-off, resolution, colored polynomial local search
Collection: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Issue Date: 2020
Date of publication: 06.01.2020

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