### A Framework for Space Complexity in Algebraic Proof SystemsA Framework for Space Complexity in Algebraic Proof Systems

Access Restriction
Subscribed

 Author Bonacina, Ilario ♦ Galesi, Nicola Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Proof complexity ♦ Algebraic proof systems ♦ Polynomial calculus ♦ Random formulae ♦ Resolution ♦ Space complexity Abstract Algebraic proof systems, such as Polynomial Calculus (PC) and Polynomial Calculus with Resolution (PCR), refute contradictions using polynomials. Space complexity for such systems measures the number of distinct monomials to be kept in memory while verifying a proof. We introduce a new combinatorial framework for proving space lower bounds in algebraic proof systems. As an immediate application, we obtain the space lower bounds previously provided for PC/PCR [Alekhnovich et al. 2002; Filmus et al. 2012]. More importantly, using our approach in its full potential, we prove $Ω(\textit{n})$ space lower bounds in PC/PCR for random $\textit{k}-CNFs$ $(\textit{k}≥$ 4) in $\textit{n}$ variables, thus solving an open problem posed in Alekhnovich et al. [2002] and Filmus et al. [2012]. Our method also applies to the Graph Pigeonhole Principle, which is a variant of the Pigeonhole Principle defined over a constant (left) degree expander graph. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-06-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 3 Page Count 20 Starting Page 1 Ending Page 20

#### Open content in new tab

Source: ACM Digital Library