Theory of Computation

We work on all aspects of theoretical computer science dealing with foundational questions in computer science. Of particular interest are algorithms, communication complexity, computational complexity, cryptography, distributed computing, learning theory, pseudorandomness, optimization, security and privacy.

Faculty

Eli Gafni	Raghu Meka	Rafail Ostrovsky	Amit Sahai	Sasha Sherstov

Yuval Ishai
Visiting P`rofessor

Current Students

• Prabhanjan Ananth
• Saikrishna Badrinarayanan
• Aayush Jain
• Rex Fernandez
• Dakshita Khurana
• Peter Rasmussen
• Arman Yousefi
• Josh Lampkins
• Pei Wu
• Yuan He

News and Awards

• Prof. Eli Gafni and his former student Elizabeth Borowski to receive Dijkstra Prize for 2017.
• Prof. Rafi Ostrovsky received the 2017 IEEE Computer Society Technical Achievement Award.
• Prof. Rafi Ostrovsky is elected as a IEEE Fellow in 2017.
• Prof. Amit Sahai along with former students Vipul Goyal, Omkant Pandey, and Brent Waters received the ACM CCS Test of Time Award for 2016.
• Prof. Amit Sahai received the 2016 Lockheed Martin Excellence in Teaching Award.
• Prof. Raghu Meka received a NSF Career Award for 2016.
• Prof. Sasha Sherstov received the 2014 Northrop Grumman Excellence in Teaching Award.
• Prof. Sasha Sherstov is seleceted as a receipient of Alfred P. Sloan Foundation Research Fellowship for 2014.
• Former student Sanjam Garg received the 2013 ACM Doctoral Dissertation Award for his thesis.
• Prof. Sasha Sherstov received a NSF Career Award for 2012.

Alumni: Students

• Will Rosenbaum (2016). Now postdoctoral researcher at Tel-Aviv University.
• Wutichai Chongchitmate (2016). Now postdoctoral researcher at UCLA.
• Vanishree Rao (2015). Now research scientist at PARC.
• Divya Gupta (2015). Now postdoctoral researcher at UC Berkeley.
• David Felber (2015). Now ow researcher at Google.
• Ran Gelles (2014). Assistant professor Bar-Ilan University.
• Alan Roytman (2014). Now postdoctoral researcher at Tel-Aviv University Computer Science.
• Silas Richelson (2014). Now Postdoc at MIT.
• Akshay Wadia (2014). Now researcher at Silicon-Valley Startup.
• Chongwon Cho (2013). Now researcher at HRL.
• Abhishek Jain (2012). Now Assistant Professor at Johns Hopkins University.
• Sanjam Garg (2012). Now Assistant Professor at UC Berkeley.
• Cheng-Keui Lee (2012). Now Security Researcher, LinkedIn.
• Hakan Seyalioglu (2012). Now researcher at Google.
• Joshua Baron (2012). Now researcher at RAND corporation.
• Nishanth Chandran (2011). Now Researcher at Microsoft.
• Clint Givens (2011). Now Assistant Professor at University of Science and Arts of Oklahoma
• Vladimir Braverman (2011). Now Assistant Professor at Johns Hopkins University.
• Omkant Pandey (2010). Now Assistant Professor, SUNY Stony Brook.
• Brett Hemenway (2010). Now Assistant Professor at at U. Penn.
• Paul Bunn (2010). Now Researcher at Google.)
• Ryan Moriarty (2010). Entrepreneur in Silicon Valley. Startups: apprats, flotate.
• Vipul Goyal (2009). Now Associate Professor at CMU.
• Steve Lu (2009). Researcher at Stealth Software Technologies, Inc.
• William Skeith (2007). Associate Professor at City College of NY).
• Elizabeth Borowsky (1995). Director at Akamai.
• Valmir Barbosa (1986). Professor at Federal University of Rio de Janeiro.
• Yehuda Afek (1985). Professor at Tel Aviv University.

Alumni: Postdocs

• Eric Miles. Now at Google.
• Anat Paskin. Now Assistant Professor at Ariel University, Israel.
• Vassilis Zikas. Now Assistant Professor at RPI.
• Hemanta Maji. Now Assistant Professor at Purdue.
• Alessandra Scafuro. Now Postdoc at Boston Univeristy.
• Omkant Pandey. Now Assistant Professor at Drexel.
• Bhavana Kanukurthi. Now Assistant Professor at Indian Institute of Science (IISC), Bangalore, India.
• Shweta Agrawal. Now Assistant Professor at IIT Madras.
• Jens Groth. Now Associate Professor at University College of London.

Courses

• CS180: Introduction to Algorithms. Eli Gafni, Raghu Meka, Rafail Ostrovsky, Majid Sarrafzadeh.
• CS181: Languages and Automata Theory. Amit Sahai, Sasha Sherstov.
• CS183: Introduction to Cryptography. Rafail Ostrovsky.
• CS280RA: Randomized Algorithms. Eli Gafni.
• CS280D: Distributed Algoritms. Eli Gafni.
• CS289: Pseudorandomness. Raghu Meka.
• CS289: Algorithmic Machine Learning. Raghu Meka.
• CS289: Advanced Topics in Cryptography. Rafail Ostrovsky.
• CS289CO: Cryptography. Amit Sahai.
• CS289: Advanced Topics in Cryptography. Amit Sahai.
• CS281: Computability and Complexity. Sasha Sherstov.
• CS289: Communication Complexity. Sasha Sherstov.