Nullstellensatz size-degree trade-offs from reversible pebbling (Q2040600): Difference between revisions

@@ Property / cites work @@
+Space Complexity in Propositional Calculus
@@ Property / cites work: Space Complexity in Propositional Calculus / rank @@
+Normal rank
@@ Property / cites work @@
+High Parallel Complexity Graphs and Memory-Hard Functions
+Normal rank
@@ Property / cites work @@
+Cumulative Space in Black-White Pebbling and Resolution
+Normal rank
@@ Property / cites work @@
+Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
+Normal rank
@@ Property / cites work @@
+Narrow Proofs May Be Maximally Long
@@ Property / cites work: Narrow Proofs May Be Maximally Long / rank @@
+Normal rank
@@ Property / cites work @@
+Proof Complexity Meets Algebra
@@ Property / cites work: Proof Complexity Meets Algebra / rank @@
+Normal rank
@@ Property / cites work @@
+The relative complexity of NP search problems
@@ Property / cites work: The relative complexity of NP search problems / rank @@
+Normal rank
@@ Property / cites work @@
+Some trade-off results for polynomial calculus
@@ Property / cites work: Some trade-off results for polynomial calculus / rank @@
+Normal rank
@@ Property / cites work @@
+Size-Space Tradeoffs for Resolution
@@ Property / cites work: Size-Space Tradeoffs for Resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Short proofs are narrow—resolution made simple
@@ Property / cites work: Short proofs are narrow—resolution made simple / rank @@
+Normal rank
@@ Property / cites work @@
+Logical Reversibility of Computation
@@ Property / cites work: Logical Reversibility of Computation / rank @@
+Normal rank
@@ Property / cites work @@
+Time/Space Trade-Offs for Reversible Computation
@@ Property / cites work: Time/Space Trade-Offs for Reversible Computation / rank @@
+Normal rank
@@ Property / cites work @@
+Q3304105
@@ Property / cites work: Q3304105 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5769706
@@ Property / cites work: Q5769706 / rank @@
+Normal rank
@@ Property / cites work @@
+Time and space bounds for reversible simulation
@@ Property / cites work: Time and space bounds for reversible simulation / rank @@
+Normal rank
@@ Property / cites work @@
+Homogenization and the polynomial calculus
@@ Property / cites work: Homogenization and the polynomial calculus / rank @@
+Normal rank
@@ Property / cites work @@
+Q4375786
@@ Property / cites work: Q4375786 / rank @@
+Normal rank
@@ Property / cites work @@
+Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
+Normal rank
@@ Property / cites work @@
+Good degree bounds on Nullstellensatz refutations of the induction principle
+Normal rank
@@ Property / cites work @@
+Extreme time-space tradeoffs for graphs with small space requirements
+Normal rank
@@ Property / cites work @@
+Q5497120
@@ Property / cites work: Q5497120 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228469
@@ Property / cites work: Q4228469 / rank @@
+Normal rank
@@ Property / cites work @@
+An observation on time-storage trade off
@@ Property / cites work: An observation on time-storage trade off / rank @@
+Normal rank
@@ Property / cites work @@
+Tight rank lower bounds for the Sherali-Adams proof system
+Normal rank
@@ Property / cites work @@
+Nullstellensatz size-degree trade-offs from reversible pebbling
+Normal rank
@@ Property / cites work @@
+Pebbling and Proofs of Work
@@ Property / cites work: Pebbling and Proofs of Work / rank @@
+Normal rank
@@ Property / cites work @@
+Explicit constructions of linear-sized superconcentrators
+Normal rank
@@ Property / cites work @@
+The Pebbling Problem is Complete in Polynomial Space
+Normal rank
@@ Property / cites work @@
+Q4737162
@@ Property / cites work: Q4737162 / rank @@
+Normal rank
@@ Property / cites work @@
+Adventures in monotone complexity and TFNP
@@ Property / cites work: Adventures in monotone complexity and TFNP / rank @@
+Normal rank
@@ Property / cites work @@
+Q3236253
@@ Property / cites work: Q3236253 / rank @@
+Normal rank
@@ Property / cites work @@
+On Time Versus Space
@@ Property / cites work: On Time Versus Space / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for the polynomial calculus and the Gröbner basis algorithm
+Normal rank
@@ Property / cites work @@
+Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies
+Normal rank
@@ Property / cites work @@
+Pebbling meets coloring: reversible pebble game on trees
+Normal rank
@@ Property / cites work @@
+Time and space complexity of reversible pebbling
@@ Property / cites work: Time and space complexity of reversible pebbling / rank @@
+Normal rank
@@ Property / cites work @@
+Trade-offs between size and degree in polynomial calculus
+Normal rank
@@ Property / cites work @@
+Reversible space equals deterministic space
@@ Property / cites work: Reversible space equals deterministic space / rank @@
+Normal rank
@@ Property / cites work @@
+Asymptotically tight bounds on time-space trade-offs in a pebble game
+Normal rank
@@ Property / cites work @@
+A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
+Normal rank
@@ Property / cites work @@
+Reversibility and adiabatic computation: trading time and space for energy
+Normal rank
@@ Property / cites work @@
+Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
+Normal rank
@@ Property / cites work @@
+A simplified way of proving trade-off results for resolution
+Normal rank
@@ Property / cites work @@
+On the Relative Strength of Pebbling and Resolution
+Normal rank
@@ Property / cites work @@
+Pebble Games, Proof Complexity, and Time-Space Trade-offs
+Normal rank
@@ Property / cites work @@
+Q4185781
@@ Property / cites work: Q4185781 / rank @@
+Normal rank
@@ Property / cites work @@
+Superconcentrators
@@ Property / cites work: Superconcentrators / rank @@
+Normal rank
@@ Property / cites work @@
+Strongly exponential lower bounds for monotone computation
+Normal rank
@@ Property / cites work @@
+Lifting Nullstellensatz to monotone span programs over any field
+Normal rank
@@ Property / cites work @@
+Q4375799
@@ Property / cites work: Q4375799 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4344138
@@ Property / cites work: Q4344138 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4190139
@@ Property / cites work: Q4190139 / rank @@
+Normal rank
@@ Property / cites work @@
+Complete Register Allocation Problems
@@ Property / cites work: Complete Register Allocation Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Space-time trade-offs on the FFT algorithm
@@ Property / cites work: Space-time trade-offs on the FFT algorithm / rank @@
+Normal rank
@@ Property / cites work @@
+Space-time tradeoffs for linear recursion
@@ Property / cites work: Space-time tradeoffs for linear recursion / rank @@
+Normal rank
@@ Property / cites work @@
+Q2816413
@@ Property / cites work: Q2816413 / rank @@
+Normal rank
@@ Property / cites work @@
+Time-space tradeoffs for computing functions, using connectivity properties of their circuits
+Normal rank
@@ Property / cites work @@
+Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space
+Normal rank