Luca Trevisan

Associate Professor

Research Areas

• Security (SEC)
• Theory (THY), (Computational Complexity, Randomness in Computation, Combinatorial Optimization)

Teaching Schedule (Spring 2008)

• CS 278. Machine-Based Complexity Theory, T T 2:00-3:30P, 405 Soda

Biography

He 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 theTheory of Computing Group) and at DIMACS and then an assistant professor at Columbia University.

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: ACM Press, 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.