MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Post Made Community Wiki by S. Carnahan
2 added 313 characters in body

Any one-tape Turing machine that decides the language of palyndromes requires $\Omega(n^2)$ time. It can be proved using communication complexity. The proof can be found in "Communication complexity" by Kushilevitz and Nisan.

$\mathbf{SAT}$ can not be decided in time $O(n^{1.801})$ and space $O(n^{o(1)})$. This result is by Ryan Williams.

There is a PhD thesis of Mihai Patrascu, where he proves several lower bounds for data structures, but more or less they are logarithmic.

Another nice lower bound is the following. SUppose you have a first order sentence over reals with operations '+', '*', '>' and integer constants. Celebrated result of Tarski and Seidenberg states that you can decide if sentence is true. But there is an unconditional result that it requires exponential time.

1

Any one-tape Turing machine that decides the language of palyndromes requires $\Omega(n^2)$ time. It can be proved using communication complexity. The proof can be found in "Communication complexity" by Kushilevitz and Nisan.

$\mathbf{SAT}$ can not be decided in time $O(n^{1.801})$ and space $O(n^{o(1)})$. This result is by Ryan Williams.

There is a PhD thesis of Mihai Patrascu, where he proves several lower bounds for data structures, but more or less they are logarithmic.