Luca Trevisan
Research Areas
- Theory (THY), (Computational Complexity, Randomness in Computation, Combinatorial Optimization)
- Security (SEC)
Research Centers
Biography
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.
Education
- 1997, Ph.D., Computer Science, Sapienza University of Rome
Selected Publications
- O. Reingold, L. Trevisan, and S. Vadhan, "Pseudorandom walks on regular digraphs and the RL vs. L problem," in Proc. 38th Annual ACM Symp. on Theory of Computing, New York, NY: ACM Press, 2006, pp. 457-466.
- A. Samorodnitsky and L. Trevisan, "Gowers uniformity, influence of variables, and PCPs," in Proc. 38th Annual ACM Symp. on Theory of Computing, New York, NY: The Association for Computing Machinery, Inc., 2006, pp. 11-20.
- L. Trevisan, "Approximation algorithms for unique games," in Proc. 46th Annual IEEE Symp. on Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society Press, 2005, pp. 197-205.
- H. Lin, L. Trevisan, and H. Wee, "On hardness amplification of one-way functions," in Lecture Notes in Computer Science: Theory of Cryptography, J. Kilian, Ed., Vol. 3378, Berlin, Germany: Springer-Verlag, 2005, pp. 34-49.
- A. Bogdanov and L. Trevisan, "On worst-case to average-case reductions for NP problems," in Proc. 44th IEEE Symp. on Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society Press, 2003, pp. 308-317.
- B. Chazelle, R. Rubinfeld, and L. Trevisan, "Approximating the minimum spanning tree weight in sublinear time," in Lecture Notes in Computer Science: Automata, Languages and Programming, F. Orejas, P. G. Spirakis, and J. van Leeuwen, Eds., Vol. 2076, London, UK: Springer-Verlag, 2001, pp. 190-200.
- L. Trevisan, "Extractors and pseudorandom generator," J. ACM, vol. 48, no. 4, pp. 860-879, July 2001.
- M. Sudan, L. Trevisan, and S. Vadhan, "Pseudorandom generators without the XOR lemma," J. Computer and System Sciences, vol. 62, no. 2, pp. 236-266, March 2001.
- L. Trevisan and S. Vadhan, "Extracting randomness from samplable distributions," in Proc. 41st Annual Symp. on Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society Press, 2000, pp. 32-42.
- A. Samorodnitsky and L. Trevisan, "A PCP characterization of NP with optimal amortized query complexity," in Proc. 32nd Annual ACM Symp. on Theory of Computing, New York, NY: ACM Press, 2000, pp. 191-199.
- L. Trevisan, "When Hamming meets Euclid: The approximability of geometric TSP and Steiner tree," SIAM J. Computing, vol. 30, no. 2, pp. 475-485, March 2000.
- L. Trevisan, M. Sudan, G. B. Sorkin, and D. P. Williamson, "Gadgets, approximation, and linear programming," in Proc. 37th Annual Symp. on Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society Press, 1996, pp. 617-626.
Awards, Memberships and Fellowships
- Okawa Research Grant, 2002
- Oberwolfach Prize, 2000
