Theoretical Computer Science at Yale

Overview | People | Sample Publications | Awards and Honors | Funding

Overview

The Yale CS Department is home to a very broad-ranging, lively effort in the theoretical aspects of computing. Research interests of the current members of the theory group include algorithmic mechanism design, approximation algorithms, combinatorial algorithms, distributed algorithms, machine learning, massive-data-set algorithms, theoretical aspects of data networking, and the theory of privacy, security, and accountability. Members of the theory group regularly collaborate with colleagues in other areas of Computer Science, including artificial intelligence, databases, networking, and numerical analysis, and with researchers in other departments, including biology, economics, law, and mathematics. Prospective grad students, postdocs, and visitors are encouraged to contact individual faculty members with similar research interests.

People

Faculty
Dana Angluin
James Aspnes
Joan Feigenbaum
Michael Fischer
Ravi Kannan (on leave at Microsoft Research; appointed jointly with Applied Mathematics)
Daniel Spielman (appointed jointly with Applied Mathematics)
Postdocs
Leonor Becerra-Bonache
Bodo Manthey
PhD Students
Samuel Daitch
Ramzi Dakdouk
Aaron Johnson
Pradipta Mitra
Lev Reyzin
Nicholas Ruozzi
Felipe Saint-Jean
Nikhil Srivastava
Yinghua Wu
Yitong Yin

Alumni (Former PhD students and postdocs, with graduation dates)

Karhan Akcoglu, PhD 2003 Josh Benaloh, PhD 1987 Kevin Chang, PhD 2006

Bernard Chazelle, PhD 1980 Jiang Chen, PhD 2006 Miklos Csuros, PhD 2000

Zoe Diamadi, PhD 2004 Petros Drineas, PhD 2003 Michael Elkin, Postdoc 2004

Fernando Esponda, Postdoc 2007 Hong Jiang, PhD 2007 Martins Krikis, PhD 1998

Philip Laird, PhD 1987 Michael Mahoney, Postdoc 2005 Ruben Michel, PhD 1990

Nathaniel Mishkin, PhD 1984 Ravi Montenegro, PhD 2002 Robert Nix, PhD 1983

Sophia A. Paleologou, PhD 1995 Lenny Pitt, PhD 1985 Vijay Ramachandran, PhD 2005

Abhiram Ranade, PhD 1989 Nicholas Reingold, PhD 1992 Rahul Sami, PhD 2003

Gauri Shah, PhD 2003 Ehud Shapiro, PhD 1982 Gregory F. Sullivan, PhD 1986

Thorsten Theobald, Postdoc 2005 Rebecca Wright, PhD 1994 Aleksandr Yampolskiy, PhD 2006

Jian Zhang, PhD 2005 Sheng Zhong, PhD 2004

Sample Publications

Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20 (2007), pages 279-304 (PODC 2006 special issue).
Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu, and Yitong Yin. Fast construction of overlay networks. Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, July 2005, pages 145-154.
Dana Angluin, Michael Fischer, and Hong Jiang. Stabilizing Consensus in Mobile Networks. Proceedings of the 2nd IEEE International Conference on Distributed Computing in Sensor Systems, Springer-Verlag LNCS 4026, 2006, pages 37-50.
Sanjeev Arora and Ravi Kannan. Learning mixtures of separated nonspherical Gaussians. Annals of Applied Probability, 15 (2005), pages 69-92.
David Cheng, Ravi Kannan, Santosh Vempala, and Grant Wang. A Divide-And-Merge Methodology for Clustering. Proceedings of the 24th Annual ACM Symposium on Principles of Database Systems, June 2005, pages 196-205.
Joan Feigenbaum, Vijay Ramachandran, and Michael Schapira. Incentive-Compatible Interdomain Routing. Proceedings of the 7th Annual ACM Conference on Electronic Commerce, June 2006, pages 130-139.
Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan. An Approximate L1-Difference Algorithm for Massive Data Streams. SIAM Journal on Computing, 32 (2002), pages 131-151.
Michael Fischer and Hong Jiang. Self-stabilizing Leader Election in Networks of Finite-state Anonymous Agents. Proceedings of the 10th International Conference on Principles of Distributed Systems, Springer-Verlag LNCS 4305, 2006, pages 395-409.
Jonathan Kelner and Daniel Spielman. A Randomized Polynomial-Time Simplex Algorithm for Linear Programming. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, May 2006, pages 51-60.
Daniel Spielman and Shang-Hua Teng. Smoothed Analysis: Why The Simplex Algorithm Usually Takes Polynomial Time. Journal of the ACM, 51 (2004), pages 385-463.

Awards and Honors

ACM Doctoral Dissertation Award winner: Daniel Spielman (1995)
ACM Fellows: Joan Feigenbaum (2001) and Michael Fischer (1996)
Dijkstra Prize winner: Michael Fischer (2001)
Fulkerson Prize winner: Ravi Kannan (1991)
ICM Invited Speakers: Joan Feigenbaum (1998), Ravi Kannan (2002), and Daniel Spielman (2002)
Information Theory Society Paper Award winner: Daniel Spielman (2002)

Funding

We gratefully acknowledge financial support for our research activities from the National Science Foundation (NSF), the Army Research Office (ARO), the Disruptive Technologies Office (DTO), the US-Israeli Binational Science Foundation (BSF), and the Kern Scholarship and Marie Curie Fellowship programs.

Contact: feigenbaum AT cs DOT yale DOT edu

Karhan Akcoglu, PhD 2003	Josh Benaloh, PhD 1987	Kevin Chang, PhD 2006
Bernard Chazelle, PhD 1980	Jiang Chen, PhD 2006	Miklos Csuros, PhD 2000
Zoe Diamadi, PhD 2004	Petros Drineas, PhD 2003	Michael Elkin, Postdoc 2004
Fernando Esponda, Postdoc 2007	Hong Jiang, PhD 2007	Martins Krikis, PhD 1998
Philip Laird, PhD 1987	Michael Mahoney, Postdoc 2005	Ruben Michel, PhD 1990
Nathaniel Mishkin, PhD 1984	Ravi Montenegro, PhD 2002	Robert Nix, PhD 1983
Sophia A. Paleologou, PhD 1995	Lenny Pitt, PhD 1985	Vijay Ramachandran, PhD 2005
Abhiram Ranade, PhD 1989	Nicholas Reingold, PhD 1992	Rahul Sami, PhD 2003
Gauri Shah, PhD 2003	Ehud Shapiro, PhD 1982	Gregory F. Sullivan, PhD 1986
Thorsten Theobald, Postdoc 2005	Rebecca Wright, PhD 1994	Aleksandr Yampolskiy, PhD 2006
Jian Zhang, PhD 2005	Sheng Zhong, PhD 2004