A generalized method for proving polynomial calculus degree lower bounds
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. '99] also on proof size. [Alekhnovich and Razborov'03] established that if the clause-variable incidence graph of a CNF formula F is a good enough expander, then proving that F is unsatisfiable requires high PC/PCR degree. We further develop the techniques in [AR03] to show that if one can "cluster" clauses and variables in a way that "respects the structure" of the formula in a certain sense, then it is sufficient that the incidence graph of this clustered version is an expander. As a corollary of this, we prove that the functional pigeonhole principle (FPHP) formulas require high PC/PCR degree when restricted to constant-degree expander graphs. This answers an open question in [Razborov'02], and also implies that the standard CNF encoding of the FPHP formulas require exponential proof size in polynomial calculus resolution. Thus, while Onto-FPHP formulas are easy for polynomial calculus, as shown in [Riis'93], both FPHP and Onto-PHP formulas are hard even when restricted to bounded-degree expanders.
Originalsprog | Engelsk |
---|---|
Titel | 30th Conference on Computational Complexity, CCC 2015 |
Redaktører | David Zuckerman |
Antal sider | 21 |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 1 jun. 2015 |
Sider | 467-487 |
ISBN (Elektronisk) | 9783939897811 |
DOI | |
Status | Udgivet - 1 jun. 2015 |
Eksternt udgivet | Ja |
Begivenhed | 30th Conference on Computational Complexity, CCC 2015 - Portland, USA Varighed: 17 jun. 2015 → 19 jun. 2015 |
Konference
Konference | 30th Conference on Computational Complexity, CCC 2015 |
---|---|
Land | USA |
By | Portland |
Periode | 17/06/2015 → 19/06/2015 |
Sponsor | Microsoft Research |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 33 |
ISSN | 1868-8969 |
ID: 251869007