Pebble Games and Algebraic Proof Systems
Lisa-Marie Jaser, Jacobo Torán · 2025
Read Pebble Games and Algebraic Proof Systems by Lisa-Marie Jaser, Jacobo Torán (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-21149.txt.
Introduction
Jaser and Toran link pebble games to algebraic proof systems in twenty twenty-five. Pebble games model the cost of computations on directed graphs. Algebraic proof systems refute formulas by polynomial reasoning. The authors study refutations of pebbling formulas, which encode pebble games as formulas.
They show a parallel between three game variants and three proof systems. A refutation with set degree and size yields a pebbling strategy with matching space and time. A pebbling strategy can likewise be turned back into a refutation. The space needed in each game variant matches variable space in its proof system. Using known pebbling bounds, they prove separations between the proof systems. Strong trade offs between degree and size are also shown for one system.
Catalog record
| CREATOR | Lisa-Marie Jaser, Jacobo Torán |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-21149
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pebble Games and Algebraic Proof Systems Lisa-Marie Jaser, Jacobo Torán Abstract Analyzing refutations of the well known pebbling formulas Peb ( G ) \mathrm{Peb}(G) we prove some new strong connections between pebble games and algebraic proof system, showing that there is a parallelism between the reversible, black and black-white pebbling games on one side, and the three algebraic proof systems Nullstellensatz, Monomial Calculus and Polynomial Calculus on the other side. In particular we prove that for any DAG G G with a single sink, if there is a Monomial Calculus refutation for Peb ( G ) \mathrm{Peb}(G) having simultaneously degree s s and size t t then there is a black pebbling strategy on G G with space s s and time t + s t+s . Also if there is a black pebbling strategy for G G with space s s and time t t it is possible to extract from it a MC refutation for Peb ( G ) \mathrm{Peb}(G) having simultaneously degree s s and size t s ts . These results are analogous to those proven in [ dRMNR21 ] for the case of reversible pebbling and Nullstellensatz. Using them we prove degree separations between NS, MC and PC, as well as strong degree-size tradeoffs for MC \mathrm{MC} . We also notice that for any directed acyclic graph G G the space needed in a pebbling strategy on G G , for the three versions of the game, reversible, black and black-white, exactly matches the variable space complexity of a refutation of the corresponding pebbling formula Peb ( G ) \mathrm{Peb}(G) in each of the algebraic proof systems NS , MC \mathrm{NS},\mathrm{MC} and PC \mathrm{PC} . Using known pebbling bounds on graphs, this connection implies separations between the corresponding variable space measures. 1 Introduction The use of pebble games in complexity theory goes back many decades. They offer a very clean tool to analyze certain complexity measures, mainly space and time, in an isolated way on a graph, which can then be translated to specific computational models. Very good overviews of these results can be found in [ Pip80 , Sav98 , Nor15 ] . We consider several versions of the game, defined formally in the preliminaries. Intuitively, the goal of these games is to measure the minimum number of pebbles needed by a single player in order to place a pebble on the sink of a directed acyclic graph (DAG) following certain rules (this is called the pebbling price). A black pebble can only be placed on a vertex if it is a source or if all its direct predecessors already have a pebble on them, but these pebbles can be removed at any time. A white pebble (modelling non-determinism) can be placed on any vertex v at any time but can only be removed if all its direct predecessors contain a pebble, which is considered as a certificate for the fact that the pebble could have been placed on v . In the reversible pebble game (modelling reversible computation), pebbles can only be placed or removed from a vertex if all the direct predecessors of the vertex contain a pebble. These three games define a short hierarchy being reversible pebbling weaker than black pebbling and this in turn weaker than the black-white pebble game. In proof complexity one tries to understand the resources needed for a proof of a mathematical statement in a formalized system. Pebbling games have also become one of the most useful tools for proving results in this area. The reason for this is that one can often translate a certain measure for the pebbling game, mainly number of pebbles or pebbling time, into a suitable complexity measure for a concrete proof system. Very often the bounds for this measure in a graph translate accurately to complexity bounds in the different proof systems for a certain kind of contradictory formulas mimicking the game, called pebbling formulas. These formulas were introduced in [ BW01 ] and have been extremely useful for proving separations, upper and lower bounds as well as tradeoff results in basically all studied proof systems. See e.g. [ Nor13 ] . In the present paper we will concentrate on algebraic proof system. In these systems formulas are encoded as sets of polynomials over a field and the question of whether a formula is unsatisfiable is translated to the question of whether the polynomials have a common root. Powerful algebraic tools like the Gröbner Basis Algorithm can be used for this purpose. Several algebraic proof systems have been introduced in the literature (defined formally bellow). Well known are Nullstellensatz (NS) introduced in [ BIK+94 ] and the more powerful Polynomial Calculus (PC) defined in [ CEI96 ] . The first one is usually considered as a static system in which a “one-shot” proof has to be produced, while in PC there are certain derivation rules like in a more standard proof system. The best studied complexity measures for refutations in these systems are the degree (maximum degree of a polynomial in the refutation) and size (number of monomials in the refutation, counted with repetitions). For studying the connections with the pebble games it is very useful to consider also space measures and the configurational refutations associated with space. We will use the variable space measure (number of variables that are simultaneously active in a refutation). In [ BG15 ] the Monomial Calculus system (MC) was identified. This system is defined by limiting the multiplication rule in PC to monomials and its power lies between \mathrm{NS} and \mathrm{PC} . Building on results from [ AM13 ] for the Sherali-Adams proof system, the authors proved that for any pair of non-isomorphic graphs, the MC degree for the refutation of the corresponding isomorphism formulas exactly corresponds to the Weisfeiler-Leman bound for separating the graphs, a very important tool in graph theory and descriptive complexity. This equivalence (as well as the relations to pebbling shown here) motivates the study of Monomial Calculus as a natural proof system between NC and PC. As mentioned above, connections between pebbling games and algebraic systems have been known since [ BCIP02 ] . It was proved in the mentioned reference that for any directed acyclic graph (DAG) G the corresponding pebbling formula \mathrm{Peb}(G) can be refuted with constant degree in PC but it requires degree \Omega(s) in NS, where s is the black pebbling price of G,\mathsf{Black}(G) . Using pebbling results, this automatically proves a strong degree separation between NS and PC. As a more recent example, the authors in [ dRMNR21 ] proved a very tight connection between NS and the reversible pebbling game. They showed that space and time in the game played on a DAG exactly correspond to the degree and size measures in a NS refutation of the corresponding pebbling formula. From this connection strong degree-size tradeoffs for NS follow. This result also improves the degree separation from [ BCIP02 ] since it is known that there are graphs for which the reversible pebbling price is a logarithmic factor larger than the black pebbling price. We show in this paper that besides these results, there are further parallelisms between