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?
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Sep 4 '14 at 19:46
  • $\begingroup$ 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. $\endgroup$ – vzn Sep 4 '14 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.