Problems that provably require quadratic time

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:

• $\Omega(n^2)$ runtime proof for any algorithm - first priority is to have as simple as possible lower bound argument.

• $O(n^2)$ algorithm, if possible, simple one as well.

• 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.

• (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)$?

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.

StackExchange Computer Science Q#30320, answer score: 9