Standard
Trade-offs between size and degree in polynomial calculus. / Lagarde, Guillaume; Nordström, Jakob; Sokolov, Dmitry; Swernofsky, Joseph.
11th Innovations in Theoretical Computer Science Conference, ITCS 2020. red. / Thomas Vidick. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. s. 1-16 72 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 151).
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
Lagarde, G
, Nordström, J, Sokolov, D & Swernofsky, J 2020,
Trade-offs between size and degree in polynomial calculus. i T Vidick (red.),
11th Innovations in Theoretical Computer Science Conference, ITCS 2020., 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, LIPIcs, bind 151, s. 1-16, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, Seattle, USA,
12/01/2020.
https://doi.org/10.4230/LIPIcs.ITCS.2020.72
APA
Lagarde, G.
, Nordström, J., Sokolov, D., & Swernofsky, J. (2020).
Trade-offs between size and degree in polynomial calculus. I T. Vidick (red.),
11th Innovations in Theoretical Computer Science Conference, ITCS 2020 (s. 1-16). [72] Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics, LIPIcs Bind 151
https://doi.org/10.4230/LIPIcs.ITCS.2020.72
Vancouver
Lagarde G
, Nordström J, Sokolov D, Swernofsky J.
Trade-offs between size and degree in polynomial calculus. I Vidick T, red., 11th Innovations in Theoretical Computer Science Conference, ITCS 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2020. s. 1-16. 72. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 151).
https://doi.org/10.4230/LIPIcs.ITCS.2020.72
Author
Lagarde, Guillaume ; Nordström, Jakob ; Sokolov, Dmitry ; Swernofsky, Joseph. / Trade-offs between size and degree in polynomial calculus. 11th Innovations in Theoretical Computer Science Conference, ITCS 2020. red. / Thomas Vidick. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. s. 1-16 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 151).
Bibtex
@inproceedings{de8a428c9bf84054a75489519e9de6d6,
title = "Trade-offs between size and degree in polynomial calculus",
abstract = "Building on [Clegg et al.{\textquoteright}96], [Impagliazzo et al.{\textquoteright}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{\textquoteright}16], who studied the analogous question for the resolution proof system, we prove that a strong size-degree trade-off is necessary.",
keywords = "Colored polynomial local search, PCR, Polynomial calculus, Polynomial calculus resolution, Proof complexity, Resolution, Size-degree trade-off",
author = "Guillaume Lagarde and Jakob Nordstr{\"o}m and Dmitry Sokolov and Joseph Swernofsky",
year = "2020",
month = jan,
doi = "10.4230/LIPIcs.ITCS.2020.72",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "1--16",
editor = "Thomas Vidick",
booktitle = "11th Innovations in Theoretical Computer Science Conference, ITCS 2020",
note = "11th Innovations in Theoretical Computer Science Conference, ITCS 2020 ; Conference date: 12-01-2020 Through 14-01-2020",
}
RIS
TY - GEN
T1 - Trade-offs between size and degree in polynomial calculus
AU - Lagarde, Guillaume
AU - Nordström, Jakob
AU - Sokolov, Dmitry
AU - Swernofsky, Joseph
PY - 2020/1
Y1 - 2020/1
N2 - 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.
AB - 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.
KW - Colored polynomial local search
KW - PCR
KW - Polynomial calculus
KW - Polynomial calculus resolution
KW - Proof complexity
KW - Resolution
KW - Size-degree trade-off
U2 - 10.4230/LIPIcs.ITCS.2020.72
DO - 10.4230/LIPIcs.ITCS.2020.72
M3 - Article in proceedings
AN - SCOPUS:85078035428
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 16
BT - 11th Innovations in Theoretical Computer Science Conference, ITCS 2020
A2 - Vidick, Thomas
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 11th Innovations in Theoretical Computer Science Conference, ITCS 2020
Y2 - 12 January 2020 through 14 January 2020
ER -