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 Tradeoffs:
TR11-149 | 4th November 2011
Paul Beame, Chris Beck, Russell Impagliazzo

Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space

We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size $N$ that have Resolution refutations of space and size each roughly $N^{\log_2 N}$ (and like all formulas have Resolution refutations of space $N$) for ... more >>>

TR18-182 | 31st October 2018
Henry Corrigan-Gibbs, Dmitry Kogan

The Function-Inversion Problem: Barriers and Opportunities

Revisions: 1

We study preprocessing algorithms for the function-inversion problem. In this problem, an algorithm gets oracle access to a function $f\colon[N] \to [N]$ and takes as input $S$ bits of auxiliary information about $f$, along with a point $y \in [N]$. After running for time $T$, the algorithm must output an ... more >>>

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-054 | 13th March 2024
Karthik Gajulapalli, Alexander Golovnev, Samuel King

On the Power of Adaptivity for Function Inversion

We study the problem of function inversion with preprocessing where, given a function $f : [N] \to [N]$ and a point $y$ in its image, the goal is to find an $x$ such that $f(x) = y$ using at most $T$ oracle queries to $f$ and $S$ bits of preprocessed ... more >>>

ISSN 1433-8092 | Imprint