What innovations in CS theory from the last 10 years have had an impact outside of academia?

Answer by Jelani Nelson:

I''ll add two more:

  • Algorithmic Game Theory studies optimization problems in which there are strategic agents whose rationality you have to take into account. For example, you're Google and want to design an ad auction system that optimizes your profit, taking into account that advertisers will try their best when using your platform to game the system to maximize their utility. A founding paper in this area of "algorithmic mechanism design" is [1].
  • Faster Numerical Linear Algebra via Randomization has been a recent development that's spread fast. Imagine you have a huge matrix, e.g. rows are users and columns are products, and an entry is that user's rating for that product. Most entries are empty, since most users don't rate most products; e.g. the Netflix matrix is only ~1% filled in [2]. Predicting unfilled entries is known as the "matrix completion" problem and is at the heart of some recommendation systems. Other problems people care about for large matrices include regression and principal component analysis (PCA). Earlier research showed how to use non-uniform sampling to get some speedup, but Sarlos showed [3] how to use fast random projections (a concept mentioned in another answer by Ghalib) to obtain speedup, which I think really changed the game. Since then, Clarkson and Woodruff showed [4] how to solve these problems even faster using ideas related to Sarlos (in time dominated by the number of nonzeroes in the matrix, which as mentioned before is often much smaller than the size of the matrix), and IBM has been putting together a linear algebra library based on these ideas [5].

[1] Noam Nisan, Amir Ronen: Algorithmic Mechanism Design. Games and Economic Behavior 35(1-2): 166-196 (2001)
[2] Yunhong Zhou, Dennis M. Wilkinson, Robert Schreiber, and Rong Pan. Large-scale parallel collaborative filtering for the Netflix prize. In Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM), pages 337–348, 2008.
[3] Tamás Sarlós: Improved Approximation Algorithms for Large Matrices via Random Projections. FOCS 2006: 143-152
[4] Kenneth L. Clarkson, David P. Woodruff: Low rank approximation and regression in input sparsity time. STOC 2013: 81-90
[5] Sketching Linear Algebra Kernel

What innovations in CS theory from the last 10 years have had an impact outside of academia?


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