I found the "work profiles" by Julie Rehmeyer on the ICM website to be good for a very high level view. But I like the idea of getting many different perspectives.
I can only speak to Dan Spielman. His most widely known work is in two areas
(1) Smoothed Analysis of Algorithms: The simplex algorithm for linear programming is fast in practice, but slow in theory. This gap is bothersome to theorists. "Smoothed analysis" provides a new method of analyzing the running time of algorithms by looking at how fast an algorithm runs on random perturbations of worst case inputs. Spielman and Shang-Hua Teng proved that the simplex algorithm runs "fast in theory" in their framework. This created a degree of excitement and inspired much further work. My impression is that while smoothed analysis is a very nice model the analysis is not necessarily easy to do and hence worst case analysis still predominates. But it is a useful tool to have for those anomalous cases like the simplex algorithm.
(2) Fast Error Correcting Codes Low Density Parity Codes have been known since the 60s, but were rarely used because they were considered too computationally inefficient. In the mid 90s new algorithms were discovered by Spielman and others which made these codes appear more attractive. In particular Spielman invented codes based on expander graphs and proved that they could be encoded and decoded particularly fast. In many cases these codes can almost achieve the theoretical bound for information transmission. This is a large and very active area of research in Electrical Engineering and many of the advances came from that community. These codes are now considered competitive with the best and are widely used in practice.
No comments:
Post a Comment