Nullstellensatz size-degree trade-offs from reversible pebbling
type: Item
instance of: scholarly article
title: Nullstellensatz size-degree trade-offs from reversible pebbling
author: Or Meir
author: Jakob Nordstrom
author: Robert Robere
author: Susanna F. de Rezende
published in: Computational Complexity
publication date: 2021-07-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/2001.02481
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10840/
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7371505
zbMATH Keywords: proof complexity
zbMATH Keywords: nullstellensatz
zbMATH Keywords: trade-offs
zbMATH Keywords: pebbling
MaRDI profile type: Publication
OpenAlex ID: W3131690564
cites work: Space Complexity in Propositional Calculus
cites work: High Parallel Complexity Graphs and Memory-Hard Functions
cites work: Cumulative Space in Black-White Pebbling and Resolution
cites work: Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
cites work: Narrow Proofs May Be Maximally Long
cites work: Proof Complexity Meets Algebra
cites work: The relative complexity of NP search problems
cites work: Some trade-off results for polynomial calculus
cites work: Size-Space Tradeoffs for Resolution
cites work: Short proofs are narrow—resolution made simple
cites work: Logical Reversibility of Computation
cites work: Time/Space Trade-Offs for Reversible Computation
cites work: Q3304105
cites work: Q5769706
cites work: Time and space bounds for reversible simulation
cites work: Homogenization and the polynomial calculus
cites work: Q4375786
cites work: Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
cites work: Good degree bounds on Nullstellensatz refutations of the induction principle
cites work: Extreme time-space tradeoffs for graphs with small space requirements
cites work: Q5497120
cites work: Q4228469
cites work: An observation on time-storage trade off
cites work: Tight rank lower bounds for the Sherali-Adams proof system
cites work: Nullstellensatz size-degree trade-offs from reversible pebbling
cites work: Pebbling and Proofs of Work
cites work: Explicit constructions of linear-sized superconcentrators
cites work: The Pebbling Problem is Complete in Polynomial Space
cites work: Q4737162
cites work: Adventures in monotone complexity and TFNP
cites work: Q3236253
cites work: On Time Versus Space
cites work: Lower bounds for the polynomial calculus and the Gröbner basis algorithm
cites work: Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies
cites work: Pebbling meets coloring: reversible pebble game on trees
cites work: Time and space complexity of reversible pebbling
cites work: Trade-offs between size and degree in polynomial calculus
cites work: Reversible space equals deterministic space
cites work: Asymptotically tight bounds on time-space trade-offs in a pebble game
cites work: A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
cites work: Reversibility and adiabatic computation: trading time and space for energy
cites work: Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
cites work: A simplified way of proving trade-off results for resolution
cites work: On the Relative Strength of Pebbling and Resolution
cites work: Pebble games, proof complexity, and time-space trade-offs
cites work: Q4185781
cites work: Superconcentrators
cites work: Strongly exponential lower bounds for monotone computation
cites work: Lifting Nullstellensatz to monotone span programs over any field
cites work: Q4375799
cites work: Q4344138
cites work: Q4190139
cites work: Complete Register Allocation Problems
cites work: Space-time trade-offs on the FFT algorithm
cites work: Space-time tradeoffs for linear recursion
cites work: A tradeoff between length and width in resolution
cites work: Time-space tradeoffs for computing functions, using connectivity properties of their circuits
cites work: Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space
DOI: 10.1007/S00037-020-00201-Y
description: scientific article; zbMATH DE number 7371505