# Lower Bounds in Theoretical Computer Science

Besides the classical: you can't do comparison sort with faster than (n logn); what are other lower bounds we know of for algorithms? I can't seem to dig them up via google scholar, yet they must exist.

I'm especially interested in polynomial time algorithms (i.e. and not proofs of: you can't solve this in polynomial time unless P = NP).

Thanks!

Note: marked as community wiki now

-
I am not sure that there is any example of this kind beside sorting, and the obvious bounds in terms of the size of the data or output. –  Benoît Kloeckner Jul 11 '10 at 18:41
If you're asking for a list of examples, this question should be community wiki. You can edit it and check the CW box in the lower right. –  Qiaochu Yuan Jul 11 '10 at 19:14
I added the “complexity-theory” tag, which is the most relevant here. –  Antonio E. Porreca Jul 11 '10 at 21:15
@Antonio, please use cs.cc.complexity-theory instead. See this meta thread: tea.mathoverflow.net/discussion/505/… –  Suresh Venkat Jul 23 '10 at 22:08

Any nonregular language cannot be decided in $o(\log \log n)$ space. This is an exercise in Papadimitriou's Computational Complexity, but I don't have it on hand.

-
I’ve always found this result fascinating: less than log log n tape is no better than no tape at all. –  Antonio E. Porreca Jul 11 '10 at 21:27
You can find the proof in the second volume of "Classical Recursion Theory". –  Kaveh Jul 23 '10 at 20:26

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.

-
Is Mihai Patrascu's PhD thesis pretty much state of the art? There seems to be little work in this field. –  LowerBounds Jul 11 '10 at 22:51
I think so. Even $\Omega(log n)$-lower-bound for any dynamic data structure was proved only in 2004 (also by Patrascu). –  ilyaraz Jul 12 '10 at 5:34
Related to Ryan's result: L. Fortnow, R. Lipton, D. van Melkebeek, and A. Viglas, "Time-space lower bounds for satisfiability", Journal of the ACM, 52(6):835-865, November 2005 –  Kaveh Jul 23 '10 at 20:35

Raz (2002) proves a lower bound of $\Omega(m^2\log m)$ for bounded coefficient arithmetic circuits over the real or complex numbers.

-

No EXPTIME-complete problem can be solved in polynomial time as a consequence of the time hierarchy theorem. Of course, the same holds for harder problems, such as problems complete for exponential space, doubly exponential time, etc. These results are unconditional (i.e., they do not depend on PNP or other conjectures).

There are some interesting problems which provably lie outside P; one of them concerns the equivalence of regular expressions (see these slides for an introduction), and some kinds of game are also very hard to solve.

-

Because of the paucity of lower bounds, there has been some work connecting one lower bound to another, as-yet unknown one. I am thinking here of the 3SUM problem: Given $n$ integers, do three sum to zero? The only upper bound (in the most general model) is $O(n^2)$. Jeff Erickson proved a matching lower bound in a restricted linear decision tree model: "Bounds for Linear Satisfiability Problem." Many problems in computational geometry can be reduced to 3SUM, and so are 3SUM-hard. For example: Given a set of $n$ points in the plane (with integer coordinates), find the minimum area triangle with corners in the set.

-

There are a number of lower bounds for problems related to sorting, for example element-distinctness: are there two identical elements in a set ? These lower bounds are actually interesting because they generalize the comparison-lower bound to more algebraic formulations: for example, you can show that solving element distinctness in a model that allows algebraic operations has a lower bound via analyzing the betti numbers of the space induced by different answers to the problem.

A very interesting example of an unconditional exponential deterministic lower bound (i.e not related to P vs NP) is for estimating the volume of a polytope. There is a construction due to Furedi and Barany that shows that the volume of a convex polytope cannot be approximated to within an even exponential factor in polynomial time unconditionally. This is striking because there are randomized poly-time algorithms that yield arbitrarily good approximations.

-
What is "an even exponential factor"? (Just a typo?) –  JBL Jul 12 '10 at 12:04
bad grammer. should have read "to within even an exponential factor" i.e for emphasis –  Suresh Venkat Jul 12 '10 at 16:06

There are a number of lowerbounds in circuit complexity.

Some well-known examples:

1. Parity is not in $AC^0$:

2. $mod_p$ is not in $AC^0[q]$.

3. k-Clique is not in $AC^0$.

There are also results for monotone circuits and for a few nesting of majority/threshold gates.

You can find references and more result in the second part of

S. Arora and B. Barak, "Computational Complexity: A Modern Approach", http://www.cs.princeton.edu/theory/complexity/

-

Many O(n) algorithms (sorting array with values in fixed range; searching in unsorted array; MST; finding largest binary-search subtree of a tree) are asymptotically optimal simply by virtue of the fact that every element must be looked at at least once.

Also, comparison-search (of a sorted array) is bounded by $\Omega(\log{n})$ for the same reason that comparison-sort is bounded by $\Omega(\log{n!})$

For completeness, O(1) algorithms are also trivially asymptotically-optimal.

-

Yiannis Moschovakis has been working on giving explicit lower bounds for algorithms deciding basic number theoretic questions. For example, together he and Lou van den Dries have shown that any algorithm deciding whether integers a,b are coprime must have infinitely many inputs on which the algorithm runs for more than log(log(a)) steps. See their paper "Is the Euclidean algorithm optimal among its peers?" at http://www.math.ucla.edu/~ynm/papers/acnote.ps The Euclidean algorithm requires logarithmic time, so their lower bound does not establish its optimality; this is discussed in the paper.

Here rather than using the number of steps a Turing machine runs as a gauge for the runtime of an algorithm they use the number of times certain primitives are called (like +,*,<,rem, and so forth). The proofs are done in a logical framework (using the language of model theory).

-
most of the lower bounds that aren't circuit-based also use #primitive operations invoked as a measure of complexity as well - specially the algebraic decision tree lower bounds –  Suresh Venkat Jul 12 '10 at 2:24

There are numerous lower-bound results that are related to distributed (and parallel) algorithms. For a partial list, see the surveys from 1989 and 2003.

Here are some further examples: Linial (1992) shows that 3-colouring a cycle requires $\Omega(\log^* n)$ communication rounds (and this is tight). Similar but more general results include, e.g., Czygrinow et al. (2008), which is a neat application of Ramsey's theorem. For something different, see, e.g., Kuhn et al. (2004).

-

Union-find data structures have an inverse-Ackermann lower bound Ω(n α(n)), see Wikipedia.

-

There are many results for Evolutionary Algorithms, e.g. (1+1)EA solving OneMax (counting ones) in $\Omega(n \log n)$ or LeadingOnes in $\Omega (n^2)$ w.p. $1-e^{-1}$. Have a look at,. e.g. Droste, et. al (2002). In general, lower bounds are harder to determine than upper bounds.

-