Cumulative memory lower bounds for randomized and quantum computation

DOI10.1145/3728715MaRDI QIDQ6907151zbMATH OpenFDO

Authors Paul Beame, Niels Kornerup

Publication date 4 November 2025

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3728715

zbMATH Keywords

branching programscumulative memory complexityquantum lower boundssortingtime-space tradeoffs

Mathematics Subject Classification ID

Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• A nondeterministic space-time tradeoff for linear codes
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• A time-space tradeoff for sorting on non-oblivious machines
• Balloon hashing: a memory-hard function providing provable protection against sequential attacks
• Cumulative memory lower bounds for randomized and quantum computation
• Cumulative space in black-white pebbling and resolution
• Depth-robust graphs and their cumulative memory complexity
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• Efficient Proofs of Secure Erasure
• Efficiently computing data-independent memory-hard functions
• Generalized String Matching
• High Parallel Complexity Graphs and Memory-Hard Functions
• How to record quantum queries, and applications to quantum indifferentiability
• scientific article; zbMATH DE number 5899238 (Why is no real title available?)
• scientific article; zbMATH DE number 3478425 (Why is no real title available?)
• Limitations of Quantum Advice and One-Way Communication
• Memory-hard functions from cryptographic primitives
• Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
• On lower bounds for read-\(k\)-times branching programs
• On the complexity of \textsf{scrypt} and proofs of space in the parallel random oracle model
• On the depth-robustness and cumulative pebbling cost of Argon2i
• One-time computable self-erasing functions
• Pebbling and Proofs of Work
• Proof of space from stacked expanders
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Quantum time-space tradeoff for finding multiple collision pairs
• Scrypt is maximally memory-hard
• The computational complexity of universal hashing
• Time-space trade-off lower bounds for randomized computation of decision problems
• Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
• Time-space tradeoffs for algebraic problems on general sequential machines
• Time-space tradeoffs for branching programs
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer

Cited in

(1)

• Quantum time-space tradeoffs for matrix problems

This page was built for publication: Cumulative memory lower bounds for randomized and quantum computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6907151)