Overview
Our efforts in Theoretical Computer Science span traditional algorithms and complexity, and often make contact with pure math (algebra, combinatorics, geometry, probability). Leonard Schulman works on aspects of coding and communication, combinatorics and probability, theoretical machine learning, and algorithmic game theory. Chris Umans works on algorithms and complexity with connections to algebra, and has an ongoing interest in algorithms for matrix multiplication that employ group theory and representation theory. Thomas Vidick is known for his work in quantum complexity and cryptography, particularly in studying the power of quantum interactive proofs. Urmila Mahadev has established landmark results regarding the classical verification of quantum computation, and is interested in problems at the intersection of quantum computation and cryptography.
Caltech is a place that is infused with theory, and many CMS and affiliated faculty make contributions in TCS as part of their work, including Babak Hassibi, Michelle Effros and Victoria Kostina (coding and information theory), Joel Tropp (matrix concentration and randomized algorithms), Erik Winfree and Lulu Qian (molecular programming), Fernando Brandao, Alexei Kitaev, and John Preskill (quantum information and computing), and Omer Tamuz (algorithmic economics, probability and statistics), and Adam Wierman (online algorithms and algorithmic economics).