Report Number: CS-TR-77-647
Institution: Stanford University, Department of Computer Science
Title: A lower bound to palindrome recognition by probabilistic Turing machines
Author: Yao, Andrew Chi-Chih
Date: December 1977
Abstract: We call attention to the problem of proving lower bounds on probabilistic Turing machine computations. It is shown that any probabilisitc Turing machine recognizing the language L = {w $\phi$ w | w $\epsilon$ ${{0,1}}^*$} with error $\lambda$ < 1/2 must take $\Omega$(n log n) time.
http://i.stanford.edu/pub/cstr/reports/cs/tr/77/647/CS-TR-77-647.pdf