Nick Reingold, 1961 -- 2008

Nicholas L. Reingold, 47, passed away on July 3 of a sudden illness. Nick graduated from Yale University in 1992 with a Ph.D. in Computer Science, and joined Bell Labs Research in 1992. In 1996 he went with AT&T Labs Research, which was newly formed from the Lucent/AT&T split, and where he worked as a valued and productive researcher until his death.

Nick's PhD research included a collaboration solving a fundamental open problem in complexity theory, showing that the class PP is closed under intersection. This sophisticated proof resolved a problem first posed by J. Gill fourteen years earlier. Nick also contributed a number of fundamental results to the theory of online optimization. He was one of the first scientists to study the use of randomization in designing algorithms for such classic problems as dynamic storage allocation and symbol table searching, as well as newer problems in distributed data management and Internet routing. Nick produced surprising upper and lower bounds on the efficiency of algorithms for very general classes of online problems such as "k-server" and "request-answer games." To prove his theorems, Nick typically combined a vast range of mathematical knowledge in probabilistic analysis, competitive analysis and game theory. His hallmark was a technique for proving the optimality of algorithms by constructing linear or non-linear programs, which could then be solved by sophisticated software to yield the proof result.

In the more-applied side of his work at AT&T, Nick also made major contributions to the fields of telecommunications network optimization and data mining. He designed and implemented algorithms for optimizing SONET optical ring design in long-distance networks, for digital cross-connect mesh network design and routing, and for packet network design and restoration. He built systems for routing and topology visualization of highly complex metro ring networks and dense wave-division multiplexing networks, and he developed new techniques in the complex field of performance analysis of multi-layer IP-over-Optical networks.

He was a joy to work with and will be profoundly missed by all who knew him.

(The above tribute is a collaborative effort by Nick's friends at AT&T and Fox Television.)