Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with time space tradeoff:
TR11-031 | 8th March 2011
Sam Buss, Ryan Williams

Limits on Alternation-Trading Proofs for Time-Space Lower Bounds

This paper characterizes alternation trading based proofs that satisfiability is not in the time and space bounded class $\DTISP(n^c, n^\epsilon)$, for various values $c<2$ and $\epsilon<1$. We characterize exactly what can be proved in the $\epsilon=0$ case with currently known methods, and prove the conjecture of Williams that $c=2\cos(\pi/7)$ is ... 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