Problems that provably require quadratic time

Question

I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$.

The problem needs to have the following properties:

1. $\Omega(n^2)$ runtime proof for any algorithm - first priority is to have as simple as possible lower bound argument.
2. $O(n^2)$ algorithm, if possible, simple one as well.
3. Output size of $O(n)$ (or smaller). Obviously any problem which requires $\Omega(n^2)$ lengthed output required at least similar run time, but that's not what I'm looking for. Notice that any decision problem fits here.
4. (if possible) a "natural" problem. Without a formal definition, a problem any CS graduate would recognize is preferable.

---

I was recently asked about such problem but couldn't come up with a simple one. The first problem that came to mind was $3SUM$, which was conjuctured to be a $\Omega(n^2)$ runtime problem. This was not simple enough and furthermore, the conjucture was recently proven false :o.

Going to an extremely unnatural problem, I believe that the problem that gets as an input a deterministic TM and input $\langle M \rangle,x$, and outputs the position of the tape head after $(|M|+|x|)^2$ steps when it's running on $x$ probably answers the question.

---

If you absolutely need to, lets agree that we're using the single-tape TM model, although I prefer problems whose runtime is independent on the exact model (as long as it's a reasonable one).

---

So, can we find a simple (to prove), natural (well known) problem whose runtime is $\Theta(n^2)$?

Answer 1

Finding an envy-free cake-cutting requires $\Omega(n^2)$ queries. However, this does not directly answer your question as the computational model is different than a Turing machine.

By the way, currently the quickest known algorithm for this problem requires $n^{n^{n^{n^{n^{n}}}}}$ queries, so there is a huge gap from the lower bound - probably one of the largest gaps in computer science.

Answer 2

As in the link provided by Raphael, Peter shows that Input Reversal requires $\Theta(n^2)$ time on vanilla single-tape TMs. For a decision problem, the language $$L = \{x0^{|x|}x \mid x \in \{0,1\}^\ast \}$$ also provably needs $\Theta(n^2)$ time to compute. To see this, use Peter's communication complexity argument , along with a classical result that $EQ_n$ needs $\Theta(n)$ bits of communication, to show the quadratic lower bound of $L$. The similar approach works for a more natural one $L = \{xx \mid x \in \{0,1\}^\ast \}$.

By the way, it is worth mentioning that the "crossing sequence method" mentioned by Yuval is (to my best knowledge) mathematically equivalent (or, maybe, inforior) to the communication complexity one.

---

For another candidate that does not directly answer your question, Ryan Williams proved that $\mathsf{SAT}$ cannot be decided in $O(n^{2 \cos(\pi/7)})$ time and simultaneously $n^{o(1)}$ space on RAMs. While the constant $2 \cos(\pi/7) \approx 1.8$ seems quite magical, the initial idea that comes from Fortnow, is ingenious but not so involved. Refer to page 101 in the textbook of Barak and Arora for an exposition of the idea.