Luca Trevisan

I am a professor of Electrical Engineering and Computer Sciences and of Mathematics at U.C. Berkeley and a senior scientist at the Simons Institute for the Theory of Computing.

I am from Rome, where I studied at the Sapienza University of Rome, advised by Pierluigi Crescenzi. I have also been a post-doc at MIT (with theTheory of Computing Group) and at DIMACS, an assistant professor at Columbia University and a professor at Stanford.

I am interested in Theoretical Computer Science.

Office hours:

Quick links [PAPERS] [Lecture Notes] [in theory]


[PAPERS by topic]

[PAPERS by year]



current students

past PhD students


  • Or Meir (2011-12)
  • Irit Dinur (2003-04)
  • Ali Sinop (2014-2015)


[Lecture notes]

at Columbia
Fall 98: W4231, Analysis of Algorithms I
Spring 99: E6291,Topics in Cryptography
Fall 99: W4231, Analysis of Algorithms I
at Berkeley
Spring 01: CS278,Complexity Theory
Fall 01: CS170, Algorithms
Spring 02: CS276,Cryptography
Fall 02: CS278, Complexity Theory
Spring 03: CS174,Randomized Algorithms
Fall 03: CS294, Coding Theory and Complexity
Spring 04: CS172, Computability and Complexity
Fall 04: CS278, Complexity Theory
Spring 05: CS170, Algorithms
Fall 05:CS172, Computability and Complexity
CS294, Pseudorandomness
Spring 06: CS294, PCP and Hardness of Approximation
Spring 07: CS172, Computability and Complexity
CS70, Discrete Mathematics
Spring 08: CS278, Complexity Theory
Spring 09: CS276, Cryptography
Fall 09: CS172, Computability and Complexity
at Stanford
Spring 10: CS254, Computational Complexity
Winter 11: CS359G: Graph Partitioning and Expanders
CS261: Optimization and Algorithmic Paradigms
Spring 11: CS154 Automata, Computability and Complexity
Winter 12: CS 154: Automata, Computability and Complexity
CS254: Computational Complexity
Fall 12: CS 259Q: Quantum Computing
Winter 13: CS366: Graph Partitioning and Expanders
Spring 13: CS161: Algorithms
Winter 14: CS54: Computational Complexity
Spring 14: CS103: Mathematics for Computer Science
at Berkeley
Spring 15: CS172: Computability and Complexity
Spring 16: CS294: Spectral Algorithms and Expanders
Fall 16: CS170: Algorithms
Fall 17: CS294: Beyond Worst-Case Analysis

How to contact me

email: luca at berkeley dot edu

mail: Luca Trevisan, Computer Science Division, U.C. Berkeley, 625 Soda Hall, Berkeley, CA 94720, USA