Appendix A: Brief history of recent TCS breakthroughs

To illustrate our point about TCS making unexpected connections, we sketch the history of a few representative breakthroughs from the 1990s. Such connections are difficult to fund in the application-driven model.

• Boosting. Work in early 1980s (Yao’s work on hardness amplification for cryptography, Valiant’s PAC learning model) --> First “boosting” algorithm (Schapire, 1989) which was clearly impractical --> AdaBoost (Freund and Schapire, 1995); a practical algorithm that quickly became a pillar of AI, Data Mining, etc. (a recent textbook in the field calls it the ``best off-the-shelf classifier in the world''). It won the ACM Kanellakis 2004 award for theory & practice.
• Random graph models. Invented in 1959 (Erdos and Renyi) --> Studied in discrete mathematics and TCS for three decades which greatly refined our knowledge --> in late 1990s, became a popular and influential tool in reasoning about many large networks, including word nets, the internet, and the human brain, with connections to physics and biology (scale-free networks).
• Quantum computation. Suggested as a possibility by physicists (Feynman, Deutsch) in early 1980s --> early 1990s; STOC/FOCS papers (Bernstein-Vazirani, Yao, Simon) formalized quantum turing machines and quantum circuits, and suggested that they may be more powerful than classical computers because they can implement the Quantum Fourier Transform-->Shor’s factoring algorithm (1994) --> mid to late 1990s; TCS papers described how to introduce robustness in the quantum model and allow it to tolerate errors/decoherence --> today QC is a thriving sub area at the intersection of physics, chemistry, and CS.
• Hashing. Rudimentary forms discovered in 1950s -->First STOC/FOCS paper in 1979; universal hashing (Carter-Wegman)--> hashing theory developed over many years in TCS papers; few immediate applications --> Late 1990s, Akamai is formed thanks to the TCS idea of consistent hashing. Hashing-like ideas also heavily used by Google and other companies that work with large data-sets.
• Interactive and probabilistic proofs and an application to coding theory. Interactive proofs invented for cryptographic purposes (GMR, mid 1980s) --> in early 1990s, connection is made to probabilistically checkable proofs and leads to important extension of the classical theory of NP-completeness (namely, for many NP-hard problems, computing approximate solutions is NP-hard too) --> in late 1990s one of the offshoots is an algorithm for decoding error-correcting codes (Sudan, Guruswami-Sudan work on list-decoding) that is considered one of the major theoretical and practical advances in information and coding theory of the past decade (featured as a “discovery” on nsf.gov).
• PCPs and  loss-resilient codes:  PCP Theorem proved (1992, AS, ALMSS) -->1993 Sipser and Spielman rediscover expander codes in an effort to simplify proof of PCP Theorem--> late 1990s; new constructions of low density parity check codes (Luby, Mitzenmacher, Shokrollahi, and Spielman; cowinners of the 2002 IEEE Inf. Theory Society best paper award) --> 2000 and later; basis of major startup Digital Fountain,  a new paradigm in coding theory, and  basis of  DVB-S2 standard for satellite transmission of television.
• Smoothed analysis: (Spielman and Teng, 2001) Combines worst-case analysis with average case analysis; a new paradigm for algorithm analysis that helps explain the everyday behaviour of some popular algorithms (such as the Simplex algorithm for linear programming).