Nullstellensatz size-degree trade-offs from reversible pebbling
From MaRDI portal
Publication:2040600
DOI10.1007/s00037-020-00201-yOpenAlexW3131690564MaRDI QIDQ2040600
Robert Robere, Jakob Nordström, Or Meir, Susanna F. de Rezende
Publication date: 14 July 2021
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2001.02481
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simplified way of proving trade-off results for resolution
- Tight rank lower bounds for the Sherali-Adams proof system
- Explicit constructions of linear-sized superconcentrators
- 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
- On the Relative Strength of Pebbling and Resolution
- Reversibility and adiabatic computation: trading time and space for energy
- Space Complexity in Propositional Calculus
- A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
- 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
- Superconcentrators
- Space-time trade-offs on the FFT algorithm
- Short proofs are narrow—resolution made simple
- Proof Complexity Meets Algebra
- Cumulative Space in Black-White Pebbling and Resolution
- Time and space complexity of reversible pebbling
- Strongly exponential lower bounds for monotone computation
- Adventures in monotone complexity and TFNP
- Nullstellensatz size-degree trade-offs from reversible pebbling
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- 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
- Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space
- Trade-offs between size and degree in polynomial calculus
