Cumulative Space in Black-White Pebbling and Resolution
From MaRDI portal
Publication:4638091
DOI10.4230/LIPIcs.ITCS.2017.38zbMath1402.68079OpenAlexW2773116874MaRDI QIDQ4638091
Susanna F. de Rezende, Joël Alwen, Jakob Nordström, Marc Vinyals
Publication date: 3 May 2018
Full work available at URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.38
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items
Static-memory-hard functions, and modeling the cost of space vs. time, From Expanders to Hitting Distributions and Simulation Theorems, Nullstellensatz size-degree trade-offs from reversible pebbling, Adventures in monotone complexity and TFNP
Cites Work
- The intractability of resolution
- Speedups of deterministic machines by synchronous parallel machines
- On alternation. II. A graph theoretic approach to determinism versus nondeterminism
- On sparse graphs with dense long paths
- Storage requirements for deterministic polynomial time recognizable languages
- Space bounds for resolution
- Separation of the monotone NC hierarchy
- On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
- A Framework for Space Complexity in Algebraic Proof Systems
- Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
- Efficiently Computing Data-Independent Memory-Hard Functions
- Total Space in Resolution
- Pebble Games, Proof Complexity, and Time-Space Trade-offs
- High Parallel Complexity Graphs and Memory-Hard Functions
- Space Complexity in Polynomial Calculus
- On the Relative Strength of Pebbling and Resolution
- Space Complexity in Propositional Calculus
- Many hard examples for resolution
- Hard examples for resolution
- Asymptotically tight bounds on time-space trade-offs in a pebble game
- Complete Register Allocation Problems
- On Time Versus Space
- Space-time trade-offs on the FFT algorithm
- The relative efficiency of propositional proof systems
- Short proofs are narrow—resolution made simple
- Space complexity of random formulae in resolution
- GRASP: a search algorithm for propositional satisfiability
- Total Space in Resolution Is at Least Width Squared
- Narrow Proofs May Be Spacious:Separating Space and Width in Resolution
- Communication lower bounds via critical block sensitivity
- Depth-Robust Graphs and Their Cumulative Memory Complexity
- Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
- On the virtue of succinct proofs
- Pebbling and Proofs of Work
- Some trade-off results for polynomial calculus
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
