Luca Trevisan

Luca Trevisan

Division of Computer Science/EECS
Research Expertise and Interest
theory(THY), (computational complexity, randomness in computation, combinatorial optimization
Research Description

Luca Trevisan studied at the University "La Sapienza" in Rome, advised by Pierluigi Crescenzi. Before coming to Berkeley, Professor Trevisan was a post-doc at MIT (with the Theory of Computing Group) and at DIMACS, and then on the faculty of Columbia University and Stanford. He is presently a joint appointee of the UC Berkeley EECS Department and the Simons Institute for Theory of Computing.

Luca's research is in theoretical computer science, and most of his work has been in two areas: (i) pseudo-randomness and its relation to average-case complexity and derandomization; and (ii) the theory of probabilistically checkable proofs and its relation to the approximability of combinatorial optimization problems. Lately, he has been working on spectral graph theory and its applications to graph algorithms.

Luca received the STOC'97 Danny Lewin (best student paper) award, the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship. He was an invited speaker at the 2006 International Congress of Mathematicians in Madrid.

Update Faculty Profile

Update your profile
Loading Class list ...