Asymptotically tight bounds on time-space trade-offs in a pebble game
From MaRDI portal
Publication:3959426
DOI10.1145/322344.322354zbMath0495.68037OpenAlexW2021496873WikidataQ97309578 ScholiaQ97309578MaRDI QIDQ3959426
Thomas Lengauer, Robert Endre Tarjan
Publication date: 1982
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322344.322354
lower boundspebble game on directed acyclic graphspermutations graphsstacks of superconcentratorsstraight line computations
Related Items
Static-memory-hard functions, and modeling the cost of space vs. time, Cumulative Space in Black-White Pebbling and Resolution, Proof of Space from Stacked Expanders, Proofs of Space, Rounds versus time for the two person pebble game, White pebbles help, Eigenvalues and expanders, Complexity theory of parallel time and hardware, Rifflescrambler -- a memory-hard password storing function, Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks, An Application of Generalized Tree Pebbling to Sparse Matrix Factorization, Space characterizations of complexity measures and size-space trade-offs in propositional proof systems, Parallelizing time with polynomial circuits, Superconcentrators of depth 2, On the cost of recomputing: tight bounds on pebbling with faults, On the power of white pebbles, On Reducing the Space Requirements of a Straight-Line Algorithm, Highly symmetric expanders, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Nullstellensatz size-degree trade-offs from reversible pebbling, Efficiently Computing Data-Independent Memory-Hard Functions, On the cost of recomputing: Tight bounds on pebbling with faults, Nullstellensatz size-degree trade-offs from reversible pebbling, Computing transitive closure on systolic arrays of fixed size, Rounds versus time for the two person pebble game, Depth-Robust Graphs and Their Cumulative Memory Complexity, Diameters and Eigenvalues
