|
|
|
Luca Trevisan
Associate Professor
Research Areas
Teaching Schedule
(Spring 2008)
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.
|
|
|
|