This is the title of a recent paper by Prof. Eric Allender at Rutgers University. Who better than the author himself to explain what the paper is all about? The full text of the paper is available here. So without further ado, here is a talk that Prof. Allender gave about this paper on April 15, 2010.
Avoiding Simplicity is Complex
I apologize for the crunchy noises from people eating during the presentation; it is after all a tradition at Rutgers that breakfast is served for people who attend the computer science theory seminar. 