Nullstellensatz size-degree trade-offs from reversible pebbling
From MaRDI portal
Publication:5091769
Recommendations
Cites work
- A tradeoff between length and width in resolution
- An observation on time-storage trade off
- Asymptotically tight bounds on time-space trade-offs in a pebble game
- Complete Register Allocation Problems
- 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 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 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
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Narrow proofs may be maximally long
- 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 space equals deterministic space
- Short proofs are narrow—resolution made simple
- 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
- 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
Cited in
(6)- Nullstellensatz size-degree trade-offs from reversible pebbling
- Time and space complexity of reversible pebbling
- scientific article; zbMATH DE number 7087310 (Why is no real title available?)
- Practical algebraic calculus and Nullstellensatz with the checkers Pacheck and Pastèque and Nuss-Checker
- Bounds on the total coefficient size of nullstellensatz proofs of the pigeonhole principle
- Separations in proof complexity and TFNP
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 Q5091769)
