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

Articles in conference proceedings

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.