Nullstellensatz size-degree trade-offs from reversible pebbling
From MaRDI portal
Publication:5091769
DOI10.4230/LIPIcs.CCC.2019.18OpenAlexW2965069118MaRDI QIDQ5091769
Or Meir, Robert Robere, Susanna F. de Rezende, Jakob Nordström
Publication date: 27 July 2022
Full work available at URL: http://arxiv.org/pdf/2001.02481.pdf
Related Items (2)
Cites Work
- Tight rank lower bounds for the Sherali-Adams proof system
- Extreme time-space tradeoffs for graphs with small space requirements
- An observation on time-storage trade off
- The relative complexity of NP search problems
- Good degree bounds on Nullstellensatz refutations of the induction principle
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Homogenization and the polynomial calculus
- Reversible space equals deterministic space
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Pebbling meets coloring: reversible pebble game on trees
- Time and space bounds for reversible simulation
- Pebble Games, Proof Complexity, and Time-Space Trade-offs
- High Parallel Complexity Graphs and Memory-Hard Functions
- Reversibility and adiabatic computation: trading time and space for energy
- Space Complexity in Propositional Calculus
- Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
- Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies
- Size-Space Tradeoffs for Resolution
- Time/Space Trade-Offs for Reversible Computation
- The Pebbling Problem is Complete in Polynomial Space
- Asymptotically tight bounds on time-space trade-offs in a pebble game
- Space-time tradeoffs for linear recursion
- Complete Register Allocation Problems
- On Time Versus Space
- Space-time trade-offs on the FFT algorithm
- Short proofs are narrow—resolution made simple
- Proof Complexity Meets Algebra
- Time and space complexity of reversible pebbling
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Strongly exponential lower bounds for monotone computation
- Lifting Nullstellensatz to monotone span programs over any field
- Narrow Proofs May Be Maximally Long
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- Pebbling and Proofs of Work
- Some trade-off results for polynomial calculus
- Logical Reversibility of Computation
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Nullstellensatz size-degree trade-offs from reversible pebbling
