Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CUMULATIVE COMPLEXITY:
Reports tagged with cumulative complexity:
TR23-005 | 13th January 2023
Paul Beame, Niels Kornerup

Cumulative Memory Lower Bounds for Randomized and Quantum Computation

Revisions: 2

Cumulative memory---the sum of space used over the steps of a computation---is a fine-grained measure of time-space complexity that is a more accurate measure of cost for algorithms with infrequent spikes in memory usage in the context of technologies such as cloud computing that allow dynamic allocation and de-allocation of ... more >>>


TR24-011 | 24th January 2024
Paul Beame, Niels Kornerup

Quantum Time-Space Tradeoffs for Matrix Problems

Revisions: 1

We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems---including matrix-vector product, matrix inversion, matrix multiplication and powering---existing ... more >>>




ISSN 1433-8092 | Imprint