Theory of Computation

Theory faculty and their research interests:

Alexei Kitaev  Quantum algorithms, error correction, complexity, and physical models. 

Leonard Schulman  Algorithms and communication protocols; combinatorics and probability; coding and information theory; quantum computation.

Chris Umans  Computational complexity; derandomization; hardness of approximation; algorithms and graph theory.

Group members:

·  Bill Fefferman (grad)

·  Jeremy Hurwitz (grad)

·  Zeyu Guo (grad)

 

Alumni:

·  Dan Feldman (Caltech postdoc  → MIT)

·  Daniel Golovin (Caltech postdoc → Google)

·  Yi-Kai Liu (Caltech postdoc → NIST)

·  Ben Recht (Caltech senior postdoc → U Wisconsin)

·  Shripad Thite (Caltech postdoc → Google)

·  Eyal Rozenman (Caltech postdoc → Brightsource Energy)

·  Vera Asodi (Caltech postdoc → VMware)

·  Yury Lifshits (Caltech postdoc → Yahoo Research)

·  Yair Bartal (Caltech sabbatical visitor, Hebrew U)

·  Ben Reichardt (Caltech postdoc → U Waterloo)

·  Shengyu Zhang (Caltech postdoc → Chinese U Hong Kong)

·  Michael Langberg (Caltech postdoc → Open U Israel)

·  Chaitanya Swamy (Caltech postdoc → U Waterloo)

·  Nevin Kapur (Caltech postdoc → Latham & Watkins LLP)

·  Jie Gao (Caltech postdoc → SUNY Stony Brook)

·  Manor Mendel (Caltech postdoc → Open U Israel)

·  Sean Hallgren (Caltech postdoc → NEC Labs)

·  Ashwin Nayak (Caltech postdoc → U Waterloo)

·  Yaoyun Shi (Caltech postdoc → U Michigan)

·   David Buchfuhrer (grad)

·  Chih-Kai (Kevin) Ko (Caltech grad → First Quadrant LP)

·  Shankar Kalyanaraman (Caltech grad → Yahoo)

·  Xiaojie Gao (Caltech grad → QVT Financial LP)

·  Po-Shen Loh (Caltech undergraduate → Cambridge U)

·  Miroslav Dudik (Caltech undergraduate → Princeton U)

·  Elitza Maneva (Caltech undergraduate → UC Berkeley)

The theory group has ongoing collaborations with other research groups, including Shuki Bruck's group (parallel and distributed systems), Michelle Effros' group (data compression), John Preskill's group (quantum computing and quantum information), and Erik Winfree's group (biomolecular computation).

Almost all of the faculty in the Information Sciences at Caltech have a large theoretical or mathematical component to their work, and interdisciplinary research is common. We encourage you to peruse the web pages of the Options in Mathematics, Control and Dynamical Systems, Electrical Engineering, Computation and Neural Systems, and Applied and Computational Mathematics.

Seminars:

·  Theory Seminar

·  CS Seminar

Some of our courses:

·  Probability and Algorithms (CS150)

·  Complexity Theory (CS 151)

·  Quantum Computing (CS 219)

·  Mathematics of Information Seminar (CS 286)

·  Combinatorial Geometry (CS 101 Special Topics)

·  Algorithms Around the Web (CS 101 Special Topics)

Centers:

·  Institute for Quantum Information (IQI)

·  Center for the Mathematics of Information (CMI)

Postions available:

·  CMI Postdoctoral Fellow Program 

·  Faculty Positions

Prospective graduate students:

Information on how to apply may be found here. Please indicate an interest in Theory of Computation.