Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LOWER BOUNDS:
Reports tagged with lower bounds:
TR15-036 | 17th February 2015
David Gajser

#### Verifying whether One-Tape Turing Machines Run in Linear Time

We discuss the following family of problems, parameterized by integers $C\geq 2$ and $D\geq 1$: Does a given one-tape non-deterministic $q$-state Turing machine make at most $Cn+D$ steps on all computations on all inputs of length $n$, for all $n$?

Assuming a fixed tape and input alphabet, we show that ... 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 >>>

ISSN 1433-8092 | Imprint