[Inspired by Lance Fortnow’s retrospective post on the “Karp report,” Avi Wigderson’s response, and the Monty Python]
And what has the theory of computing done for us in the last twenty years?
Differential privacy? Apple just announced it will be used in iOS 10
Yes, and the application to preventing false discovery and overfitting is now used in production.
Ok, fine, but apart from differential privacy, what has theory done for us in the last twenty years?
Quantum algorithms? There wouldn’t be such a push to realize quantum computers if it wasn’t for Shor’s algorithm.
And quantum error correcting! There would be no hope of realizing quantum computers without quantum error correction
Very well, but apart from differential privacy and quantum computing, what has theory done for us in the …
Streaming algorithms? It all started with a theory paper and now it is a major interdisciplinary effort.
Yes, fair enough, but apart from differential privacy, quantum computing, and streaming algorithms, what has theory done for us…
Linear time decodable LDPC error-correcting codes? The first generation was not practical, but now they are part of major standards
Sure, ok, but apart from differential privacy, quantum computing, streaming algorithms, and error-correcting codes, what has theory…
Homomorphic encryption? The first-generation solutions were inefficient, but it might be only a matter of time before we have usable homomorphic encryption standards.
Linear-time SDD solvers? Algorithms like this and this are implementable and we may be one more idea away from algorithms that can be put in production.
Sublinear time algorithms like sparse FFT?
All right! But apart from differential privacy, quantum computing, streaming algorithms, error-correcting codes, homomorphic encryption, linear-time equation solvers and sub-linear time algorithms, what has the theory of computing ever done for us in the past twenty years?
. . .
[Could be continued. Indeed, please continue in the comments]