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:
TR04-045 | 15th April 2004
Hartmut Klauck, Robert Spalek, Ronald de Wolf

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

A strong direct product theorem says that if we want to compute
k independent instances of a function, using less than k times
the resources needed for one instance, then our overall success
probability will be exponentially small in k.
We establish such theorems for the classical as well as ... more >>>

TR05-137 | 21st November 2005
Emanuele Viola

On Probabilistic Time versus Alternating Time

We prove several new results regarding the relationship between probabilistic time, BPTime(t), and alternating time, \Sigma_{O(1)} Time(t). Our main results are the following:

1) We prove that BPTime(t) \subseteq \Sigma_3 Time(t polylog(t)). Previous results show that BPTime(t) \subseteq \Sigma_2 Time(t^2 log t) (Sipser and Gacs, STOC '83; Lautemann, IPL '83) ... more >>>

TR12-027 | 29th March 2012
Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang

Time-space tradeoffs for width-parameterized SAT:Algorithms and lower bounds

Revisions: 2

A decade has passed since Alekhnovich and Razborov presented an algorithm that solves SAT on instances $\phi$ of size $n$ having tree-width $TW(\phi)$, using time (and space) bounded by $2^{O(TW(\phi))}n^{O(1)}$. Although there have been several papers over the ensuing years building on the work of Alekhnovich and Razborov there has ... more >>>

TR14-109 | 14th August 2014
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

Quantum lower bound for inverting a permutation with advice

Revisions: 1

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on ... more >>>

TR16-019 | 5th February 2016
Ran Raz

Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial.

More formally, in the problem of ... more >>>

TR16-113 | 22nd July 2016
Gillat Kol, Ran Raz, Avishay Tal

Time-Space Hardness of Learning Sparse Parities

We define a concept class ${\cal F}$ to be time-space hard (or memory-samples hard) if any learning algorithm for ${\cal F}$ requires either a memory of size super-linear in $n$ or a number of samples super-polynomial in $n$, where $n$ is the length of one sample.

A recent work shows ... more >>>

TR17-017 | 5th February 2017
Michal Moshkovitz, Dana Moshkovitz

Mixing Implies Lower Bounds for Space Bounded Learning

One can learn any hypothesis class $H$ with $O(\log|H|)$ labeled examples. Alas, learning with so few examples requires saving the examples in memory, and this requires $|X|^{O(\log|H|)}$ memory states, where $X$ is the set of all labeled examples. A question that arises is how many labeled examples are needed in ... more >>>

TR17-020 | 12th February 2017
Ran Raz

A Time-Space Lower Bound for a Large Class of Learning Problems

We prove a general time-space lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples.

Our result is stated in terms of the norm ... more >>>

TR17-121 | 31st July 2017
Sumegha Garg, Ran Raz, Avishay Tal

Extractor-Based Time-Space Lower Bounds for Learning

Revisions: 1

A matrix $M: A \times X \rightarrow \{-1,1\}$ corresponds to the following learning problem: An unknown element $x \in X$ is chosen uniformly at random. A learner tries to learn $x$ from a stream of samples, $(a_1, b_1), (a_2, b_2) \ldots$, where for every $i$, $a_i \in A$ is chosen ... more >>>

TR19-071 | 14th May 2019
Sumegha Garg, Ran Raz, Avishay Tal

Time-Space Lower Bounds for Two-Pass Learning

A line of recent works showed that for a large class of learning problems, any learning algorithm requires either super-linear memory size or a super-polynomial number of samples [Raz16,KRT17,Raz17,MM18,BOGY18,GRT18]. For example, any algorithm for learning parities of size $n$ requires either a memory of size $\Omega(n^{2})$ or an exponential number ... more >>>

ISSN 1433-8092 | Imprint