INTRODUCTION AND SUMMARY
As computer science enters an era of new challenges and multidisciplinary opportunities, there is a pressing need for new approaches, new conceptual models, and unconventional ideas. Theoretical computer science (TCS) has a proven track record in providing all of these. TCS innovations such as analysis of algorithms, NP-completeness, complexity-based cryptography, use of probabilistic choices in algorithms, etc., are mainstays of CS research and education and one result is the growing popularity of quantitative reasoning and formal models in all of CS. In the past decade, TCS has invented new sub-disciplines (quantum computing), contributed new paradigms for emerging areas (web-search, internet content distribution, data-mining, computational biology etc.), and made important breakthroughs in a continuing study of intrinsic complexity, NP-completeness, randomness, efficient algorithms, networks, etc. Its long-term focus is at the root of its high impact –scientific, conceptual— and this has benefited the strategic national interest. Finally, TCS has also had considerable commercial impact: several IT and Biotech companies –Google, Amazon, Celera Genomics, Akamai, Verity, Digital Fountain, etc.—rely crucially on good algorithms originating from TCS. In many cases their chief scientists were also TCS researchers (at Amazon, the title is “Chief Algorithms Officer”).
Theory Matters 