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).