# Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments

One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine.

Is there a similarly simple example that

• proves a lower bound of $\Omega(n^3)$ for another problem
• that can be decided in time $O(n^3)$
• on a single tape Turing machine
• using arguments from communication complexity?
• IIRC, the result cannot be extended to $\omega(n^2)$. The reason is that the communication complexity of a function cannot be more than $n$. But I am not an expert. If you don't get an answer here you can move it to Theoretical Computer Science and hopefully someone will answer it there. – Kaveh Sep 4 '14 at 19:46
• afaik nontrivial lower bounds (superlinear) are not proven for nearly any algorithms for TMs via any methods except "contrived" functions via diagonalization eg the time hierarchy theorem. – vzn Sep 4 '14 at 20:12