Pebble games and algebraic proof systems
From MaRDI portal
Cites work
- A comparison of two variations of a pebble game on graphs
- A finite-model-theoretic view on propositional proof complexity
- Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
- Descriptive complexity of linear equation systems and applications to propositional proof complexity
- Hardness of approximation in PSPACE and separation results for pebble games
- Homogenization and the polynomial calculus
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1033441 (Why is no real title available?)
- Limitations of algebraic approaches to graph isomorphism testing
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Nullstellensatz size-degree trade-offs from reversible pebbling
- Number of quantifiers is better than number of tape cells
- On space and depth in resolution
- On the power of white pebbles
- Pebble games, proof complexity, and time-space trade-offs
- Reversible pebble games and the relation between tree-like and general resolution space
- Sherali-Adams relaxations and indistinguishability in counting logics
- Short proofs are narrow—resolution made simple
- Size space tradeoffs for resolution
- Some trade-off results for polynomial calculus (extended abstract)
- Space bounds for a game on graphs
- Storage requirements for deterministic polynomial time recognizable languages
- Time/Space Trade-Offs for Reversible Computation
- White pebbles help
This page was built for publication: Pebble games and algebraic proof systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241072)
