Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

Standard

Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases. / Lauria, Massimo; Nordström, Jakob.

32nd Computational Complexity Conference, CCC 2017. red. / Ryan O'Donnell. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. 2 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 79).

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

Harvard

Lauria, M & Nordström, J 2017, Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases. i R O'Donnell (red.), 32nd Computational Complexity Conference, CCC 2017., 2, Leibniz International Proceedings in Informatics, LIPIcs, vol. 79, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 32nd Computational Complexity Conference, CCC 2017, Riga, Lettland, 2017/07/06. https://doi.org/10.4230/LIPIcs.CCC.2017.2

APA

Lauria, M., & Nordström, J. (2017). Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases. I R. O'Donnell (Red.), 32nd Computational Complexity Conference, CCC 2017 [2] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 79). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CCC.2017.2

CBE

Lauria M, Nordström J. 2017. Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases. O'Donnell R, redaktör. I 32nd Computational Complexity Conference, CCC 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Article 2. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.CCC.2017.2

MLA

Lauria, Massimo och Jakob Nordström "Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases". O'Donnell, Ryan (red.). 32nd Computational Complexity Conference, CCC 2017. Leibniz International Proceedings in Informatics, LIPIcs. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2017. https://doi.org/10.4230/LIPIcs.CCC.2017.2

Vancouver

Lauria M, Nordström J. Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases. I O'Donnell R, redaktör, 32nd Computational Complexity Conference, CCC 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2017. 2. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.CCC.2017.2

Author

Lauria, Massimo ; Nordström, Jakob. / Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases. 32nd Computational Complexity Conference, CCC 2017. redaktör / Ryan O'Donnell. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. (Leibniz International Proceedings in Informatics, LIPIcs).

RIS

TY - GEN

T1 - Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases

AU - Lauria, Massimo

AU - Nordström, Jakob

PY - 2017/7/1

Y1 - 2017/7/1

N2 - We consider the graph k-colouring problem encoded as a set of polynomial equations in the standard way. We prove that there are bounded-degree graphs that do not have legal k-colourings but for which the polynomial calculus proof system defined in [Clegg et al. 1996, Alekhnovich et al. 2002] requires linear degree, and hence exponential size, to establish this fact. This implies a linear degree lower bound for any algorithms based on Gröbner bases solving graph k-colouring using this encoding. The same bound applies also for the algorithm studied in a sequence of papers [De Loera et al. 2008, 2009, 2011, 2015] based on Hilbert's Nullstellensatz proofs for a slightly different encoding, thus resolving an open problem mentioned, e.g., in [De Loera et al. 2009] and [Li et al. 2016]. We obtain our results by combining the polynomial calculus degree lower bound for functional pigeonhole principle (FPHP) formulas over bounded-degree bipartite graphs in [Miksa and Nordström 2015] with a reduction from FPHP to k-colouring derivable by polynomial calculus in constant degree.

AB - We consider the graph k-colouring problem encoded as a set of polynomial equations in the standard way. We prove that there are bounded-degree graphs that do not have legal k-colourings but for which the polynomial calculus proof system defined in [Clegg et al. 1996, Alekhnovich et al. 2002] requires linear degree, and hence exponential size, to establish this fact. This implies a linear degree lower bound for any algorithms based on Gröbner bases solving graph k-colouring using this encoding. The same bound applies also for the algorithm studied in a sequence of papers [De Loera et al. 2008, 2009, 2011, 2015] based on Hilbert's Nullstellensatz proofs for a slightly different encoding, thus resolving an open problem mentioned, e.g., in [De Loera et al. 2009] and [Li et al. 2016]. We obtain our results by combining the polynomial calculus degree lower bound for functional pigeonhole principle (FPHP) formulas over bounded-degree bipartite graphs in [Miksa and Nordström 2015] with a reduction from FPHP to k-colouring derivable by polynomial calculus in constant degree.

KW - 3-colouring

KW - Cutting planes

KW - Gröbner basis

KW - Nullstellensatz

KW - Polynomial calculus

KW - Proof complexity

U2 - 10.4230/LIPIcs.CCC.2017.2

DO - 10.4230/LIPIcs.CCC.2017.2

M3 - Paper in conference proceeding

AN - SCOPUS:85028777140

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 32nd Computational Complexity Conference, CCC 2017

A2 - O'Donnell, Ryan

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 32nd Computational Complexity Conference, CCC 2017

Y2 - 6 July 2017 through 9 July 2017

ER -