Space-time tradeoff lower bounds

Question

Following the discussion on lower bounds for 3SAT [1], I'm wondering what are the main lower bound results formulated as space-time tradeoffs. I'm excluding results such as, say, Savitch's theorem; a good entry would focus on a single problem and its bounds. An example would be :

"Let T and S be the running time and space bound of any SAT algorithm. Then we must have T⋅S≥n2cos(π/7)−o(1) infinitely often." (Given in [1] by Ryan Williams.)

or

"SAT cannot be solved simultaneously in n¹⁺⁰⁽¹⁾ time and n^1-ε space for any ε>0 on general random-access nondeterministic Turing machines." (Lance Fortnow in 10.1109/CCC.1997.612300)

Further, I'm including definitions of natural space-time tradeoff complexity classes (excluding circuit classes).

Answer 1

Here are a few additional references. More can be found by looking at the papers that cite these.

Duris and Galil (1984) give a language in $P$ which requires $T^2 S \geq \Omega(n^3)$ on one-tape Turing machines with any constant number of read-write heads. Karchmer (1986) showed that the same lower bound holds for the element distinctness problem.

Babai, Nisan, and Szegedy (1989) give a very natural language (generalized inner product) that is solvable in $O(n)$ time and $O(1)$ space on a $k+1$-head one-tape Turing machine, that requires $T S \geq \Omega(n^2)$ on any $k$-head one-tape Turing machine.

Ajtai (1999) shows time-space tradeoffs for deterministic random access machines computing element distinctness. In particular if $S \leq o(n)$, then $T \geq \omega(n)$. Subsequent work by Beame, Saks, Sun, and Vee (2000) proves time-space tradeoffs for randomized computations.

Santhanam (2001) showed that $TS \geq \Omega(n^2)$ holds for multitape Turing machines solving SAT, building on Cobham's analogous lower bound for PALINDROMES.