

Luca Trevisan
Professor
Research Areas
Biography
Luca Trevisan studied at the University "La Sapienza" in Rome, advised by Pierluigi Crescenzi. Before coming to Berkeley, Professor Trevisan was a postdoc at MIT (with the Theory of Computing Group) and at DIMACS, and then on the faculty of Columbia University. He is presently a joint appointee of the UC Berkeley EECS Department and the Simons Institute for Theory of Computing.
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. 457466.
 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. 1120.
 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. 197205.
 H. Lin, L. Trevisan, and H. Wee, "On hardness amplification of oneway functions," in Lecture Notes in Computer Science: Theory of Cryptography, J. Kilian, Ed., Vol. 3378, Berlin, Germany: SpringerVerlag, 2005, pp. 3449.
 A. Bogdanov and L. Trevisan, "On worstcase to averagecase reductions for NP problems," in Proc. 44th IEEE Symp. on Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society Press, 2003, pp. 308317.
 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: SpringerVerlag, 2001, pp. 190200.
 L. Trevisan, "Extractors and pseudorandom generator," J. ACM, vol. 48, no. 4, pp. 860879, 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. 236266, 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. 3242.
 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. 191199.
 L. Trevisan, "When Hamming meets Euclid: The approximability of geometric TSP and Steiner tree," SIAM J. Computing, vol. 30, no. 2, pp. 475485, 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. 617626.



