Faculty Publications - Luca Trevisan

Books

• A. Bogdanov and L. Trevisan, Average-Case Complexity, Foundations and Trends in Theoretical Computer Science, Vol. 2, Hanover, MA: Now Publishers Inc., 2006.

Book chapters or sections

• L. Trevisan, "Learning Heavy Fourier Coefficients of Boolean Functions," in Encyclopedia of Algorithms, M. Y. Kao, Ed., Springer Reference, New York, NY: Springer US, 2008.
• R. Canetti, R. Rivest, M. Sudan, L. Trevisan, S. Vadhan, and H. Wee, "Amplifying collision resistance: A complexity-theoretic treatment," in Advances in Cryptology: Proc. 27 Annual Intl. Cryptology Conf. (CRYPTO 2007), A. Menezes, Ed., Lecture Notes in Computer Science, Vol. 4622, Berlin, Germany: Springer-Verlag, 2007, pp. 264-283.
• L. Trevisan, "Fun with Sub-Linear Time Algorithms (Invited Talk)," in Fun with Algorithms: Proc. 4th Intl. Conf. (FUN 2007), P. Crescenzi, G. Prencipe, and G. Pucci, Eds., Lecture Notes in Computer Science, Vol. 4475, Berlin, Germany: Springer-Verlag, 2007, pp. 15-15.
• A. Hall and C. Papadimitriou, "Approximating the distortion," in Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, C. Chekuri, K. Jansen, J. D. P. Rolim, and L. Trevisan, Eds., Lecture Notes in Computer Science, Vol. 3624, Berlin, Germany: Springer-Verlag, 2005, pp. 111-122.
• 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.
• 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.

Articles in journals or magazines

• L. Trevisan, "Approximation algorithms for unique games," Theory of Computing, vol. 4, pp. 111-128, Oct. 2008.
• L. Trevisan and S. Vadhan, "Pseudorandomness and average-case complexity via uniform reductions," Computational Complexity, vol. 16, no. 4, pp. 331-364, Dec. 2007.
• A. Bogdanov and L. Trevisan, "On worst-case to average-case reductions for NP problems," SIAM J. Computing, vol. 36, no. 4, pp. 1119-1159, 2006.
• O. Goldreich, H. Karloff, L. J. Schulman, and L. Trevisan, "Lower bounds for linear locally decodable codes and private information retrieval," Computational Complexity, vol. 15, no. 3, pp. 263-296, Oct. 2006.
• E. Mossel, A. Shpilka, and L. Trevisan, "On epsilon-based generators in NC^0," Random Structures and Algorithms, vol. 29, no. 1, pp. 56-81, Aug. 2006.
• B. Chazelle, R. Robinfeld, and L. Trevisan, "Approximating the minimum spanning tree weight insublinear time," SIAM J. Computing, vol. 34, no. 6, pp. 1370-1379, 2005.
• R. Gennaro, Y. Gertner, J. Katz, and L. Trevisan, "Bounds on the efficiency of generic cryptographic constructions," SIAM J. Computing, vol. 35, no. 1, pp. 217-246, 2005.
• L. Trevisan, S. Vadhan, and D. Zuckerman, "Compression of samplable sources," Computational Complexity, vol. 14, no. 3, pp. 186-227, Dec. 2005.
• L. Trevisan, "On local versus global satisfiability," SIAM J. Discrete Mathematics, vol. 17, no. 4, pp. 541-547, 2004.
• S. Khanna, M. Sudan, L. Trevisan, and D. P. Williamson, "The approximability of constraint satisfaction problems," SIAM J. Computing, vol. 30, no. 6, pp. 1863-1920, 2001.
• 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, G. B. Sorkin, M. Sudan, and D. P. Williamson, "Gadgets, approximation, and linear programming," SIAM J. Computing, vol. 29, no. 6, pp. 2074-2097, 2000.
• 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.
• P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan, "Structure in approximation classes," SIAM J. Computing, vol. 28, no. 5, pp. 1759-1782, 1999.

Articles in conference proceedings

• L. Trevisan, S. Vadhan, O. Reingold, and M. Tulsiania, "Dense subsets of pseudorandom sets," in Proc. 49th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2008), Los Alamitos, CA: IEEE Computer Society, 2008.
• G. Schoenebeck, L. Trevisan, and M. Tulsiani, "Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut," in Proc. 39th Annual ACM Symp. on Theory of Computing (STOC 2007), New York, NY: The Association for Computing Machinery, Inc., 2007, pp. 302-310.
• G. Schoenebeck, L. Trevisan, and M. Tulsiani, "A linear round lower bound for Lovasz-Schrijver SDP relaxations of vertex cover," in Proc. 22nd Annual IEEE Conf. on Computational Complexity (CCC 2007), Los Alamitos, CA: IEEE Computer Society, 2007, pp. 205-216.
• L. Trevisan, "Pseudorandomness and combinatorial constructions," in Proc. 2006 Intl. Congress of Mathematicians (ICM '06), M. Sanz-Sole, J. Soria, J. L. Varona, and J. Verdera, Eds., Vol. 3, Helsinki, Finland: European Mathematical Society, 2007, pp. 1111-1136.
• 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.
• 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.
• 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, 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.

Technical Reports

• O. Reingold, L. Trevisan, M. Tulsiani, and S. Vadhan, "Dense Subsets of Pseudorandom Sets," Electronic Colloquium on Computational Complexity, Tech. Rep. ECCC-TR08-045, April 2008.