[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]

### Like this:

Like Loading...

*Related*

Locality sensitive hashing? And min-wise hashing? And Count-min sketches (goes beyond just streaming)

Also randomized linear algebraic methods.

Sure there are many contributions of TCS. But apple’s proprietary closed implementation of differential privacy is possibly worrisome. See Schneier’s blog or http://blog.cryptographyengineering.com/2016/06/what-is-differential-privacy.html

for more. Unless you want to trust big brother, this is a real concern.

There are tons of example from Crypto: additive and multiplicative homomorphic encryption are already used in practice, secret sharing, secure multi-party computation, deterministic encryption, order preserving encryption, etc. Microsoft Research has “AlwaysEncrypted” database system which is now shipped in Microsoft Azure. Also see the CryptDB project.

akamai

The Monty Python reference was great, loved it!

Hi Luca, I am sure you know the saying — in theory, there is no difference …. 🙂

I think what is missing is the intuition part. Let me give an idea. on the input of n bit there are 2^n possible input combination (a power set). In general ‘a problem’ can map any subset to 1 and complementary to 0. The question is can we divide the space of input into polynomial number (p, p^p= 2^n) of pieces (congruence classes, which may be complicated) such that it would be possible to check the solutions on each class in const time. To be more concrete. In Integer factorization in the sieve method the space is broken onto the set of eliptic curves, where first the existence of solution on the eliptic curve is checked, and then the solution is searched for. Given Shor’s algorithm it appears that it is possible to have polynomial # of set of congruences for factorization. So the question what general (congruence) partition is possible and what specific congruences are useful for particular set of problems. I think just reformulating the problem in this terms will lead to the progress in understanding of computation.

Good discussion – BTW , if your business needs a Copyright Form VA , my family edited a blank form here

`https://goo.gl/0QJVlO`

.Agree with bitvalve: Akamai. Here is a nice paper on the role of algorithms in the origin of CDNs and Akamai.