Nullstellensatz size-degree trade-offs from reversible pebbling
From MaRDI portal
Publication:2040600
Recommendations
Cites work
- A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
- A simplified way of proving trade-off results for resolution
- A tradeoff between length and width in resolution
- Adventures in monotone complexity and TFNP
- An observation on time-storage trade off
- Asymptotically tight bounds on time-space trade-offs in a pebble game
- Complete Register Allocation Problems
- Cumulative space in black-white pebbling and resolution
- Explicit constructions of linear-sized superconcentrators
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- Extreme time-space tradeoffs for graphs with small space requirements
- Good degree bounds on Nullstellensatz refutations of the induction principle
- High Parallel Complexity Graphs and Memory-Hard Functions
- Homogenization and the polynomial calculus
- scientific article; zbMATH DE number 3121294 (Why is no real title available?)
- scientific article; zbMATH DE number 3622921 (Why is no real title available?)
- scientific article; zbMATH DE number 3628386 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1033441 (Why is no real title available?)
- scientific article; zbMATH DE number 1114017 (Why is no real title available?)
- scientific article; zbMATH DE number 1114028 (Why is no real title available?)
- scientific article; zbMATH DE number 2086627 (Why is no real title available?)
- scientific article; zbMATH DE number 3029852 (Why is no real title available?)
- Lifting Nullstellensatz to monotone span programs over any field
- Logical Reversibility of Computation
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies
- Narrow proofs may be maximally long
- Nullstellensatz size-degree trade-offs from reversible pebbling
- On the Relative Strength of Pebbling and Resolution
- On Time Versus Space
- Pebble games, proof complexity, and time-space trade-offs
- Pebbling and Proofs of Work
- Pebbling meets coloring: reversible pebble game on trees
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Proof Complexity Meets Algebra
- Reversibility and adiabatic computation: trading time and space for energy
- Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space
- Reversible space equals deterministic space
- Short proofs are narrow—resolution made simple
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- Size-space tradeoffs for resolution
- Some trade-off results for polynomial calculus (extended abstract)
- Space Complexity in Propositional Calculus
- Space-time trade-offs on the FFT algorithm
- Space-time tradeoffs for linear recursion
- Strongly exponential lower bounds for monotone computation
- Superconcentrators
- The Pebbling Problem is Complete in Polynomial Space
- The relation between polynomial calculus, Sherali-Adams, and sum-of-squares proofs
- The relative complexity of NP search problems
- Tight bounds for monotone switching networks via Fourier analysis
- Tight rank lower bounds for the Sherali-Adams proof system
- Time and space bounds for reversible simulation
- Time and space complexity of reversible pebbling
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- Time/Space Trade-Offs for Reversible Computation
- Trade-offs between size and degree in polynomial calculus
Cited in
(6)- Reversible pebble games and the relation between tree-like and general resolution space
- Time and space complexity of reversible pebbling
- Nullstellensatz size-degree trade-offs from reversible pebbling
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Pebble games and algebraic proof systems
- Pebble games and algebraic proof systems
This page was built for publication: Nullstellensatz size-degree trade-offs from reversible pebbling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2040600)
