# 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.