A conversation on what theory has done for us

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

10 thoughts on “A conversation on what theory has done for us

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

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

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

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

  5. Good discussion – BTW , if your business needs a Copyright Form VA , my family edited a blank form here https://goo.gl/0QJVlO.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s