Work supported by NSF Grant 9984703/0406156

This page contains work supported by the National Science Foundation under Grants No. 9984703 and 0406156. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).
 

Research Work

Grants  9984703 and 0406156 funded work on PCP and hardness of approximation and on randomized computations, with particular focus on pseudorandomness and randomness extraction. Motivated by their occurrence in PCP constructions, we studied locally decodable codes as combinatorial objects of independent interest. The work on the power of probabilistic algorithms led us to consider the power of sub-linear time algorithms, in the setting of property testing and in the setting of approximation algorithms. Towards the end of the grant, the work started branching in new directions, including cryptographic applications and data compression.
 

Work on average-case complexity, pseudorandomness and randomness extraction

• Andrej Bogdanov and Luca Trevisan
  On Worst-Case to Average-Case Reductions for NP Problems
  In Proc. of 44th FOCS, IEEE, pp. 308-317, 2003
  [Draft full version] [Conference Proceedings] 
• Luca Trevisan
  List Decoding Using the XOR Lemma
  In Proc. of 44th FOCS, IEEE, pp. 126-135, 2003
  [Conference Proceedings]
• Elchanan Mossel, Amir Shpilka and Luca Trevisan
  On epsilon-Biased Generators in NC0
  In Proc. of 44th FOCS, IEEE, pp. 136-145, 2003
  [Manuscript]
• Luca Trevisan and Salil Vadhan
  Pseudorandomness and Average-case Complexity via Uniform Reductions
  In Proc. of 17th  Computational Complexity Conference, pages 129-138, IEEE, 2002
  [Conference proceedings]
• Z. Bar-Yossef, O. Reingold, R. Shaltiel and L. Trevisan
  Streaming Computation of Combinatorial Objects
  In Proc. of 17th  Computational Complexity Conference, pages165-174, IEEE, 2002
  [Draft full version]
• R. Gennaro and L. Trevisan.
  Lower bounds on the efficiency of generic cryptographic constructions.
  In Proc. of 41st FOCS, pages 305-313, IEEE, 2000
  [Conference proceedings]
• Luca Trevisan and Salil Vadhan.
  Extracting Randomness from Samplable Distributions
  In Proc. of 41st FOCS, pages 32-42, IEEE, 2000
  [Conference proceedings]

Work on cryptography

• Omer Reingold, Luca Trevisan and Salil Vadhan
  Notions of Reducibility between Cryptographic Primitives
  In Proc. of 1st Theory of Cryptography Conference, Springer-Verlag, pp. 1-20, 2004
  [Conference Proceedings]
• Cynthia Dwork, Ronen Shaltiel, Adam Smith and Luca Trevisan
  List Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument
  In Proc. of 1st Theory of Cryptography Conference, Springer-Verlag, pp. 101-120, 2004
  [Conference Proceedings]

Work on PCP, hardness of approximation, and locally decodable codes

• L. Trevisan
  Non-approximability Results for Optimization Problems on Bounded Degree Instances.
  In Proc. of the 33rd ACM STOC, 2001
  [Conference Proceedings]
• O. Goldreich, H. Karloff, L. Schulman, and L. Trevisan

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval
In Proc. of 17th  Computational Complexity Conference, pages 175-183, IEEE, 2002
[Manuscript]

Work on sub-linear time algorithms

• A. Bogdanov and L. Trevisan
  Lower Bounds for Testing Bipartiteness in Dense Graphs
  In Proc. of 19th Computational Complexity Conference, IEEE, 2004
  [Manuscript]
• A. Bogdanov, K. Obata and L. Trevisan
  A Lower Bound for Testing 3-Colorability in Bounded-degree Graphs
  In Proc. of 43rd FOCS, pages 93-102, IEEE, 2002
  [Conference Proceedings]
• Oded Goldreich and Luca Trevisan
  Three Theorems Regarding Testing Graph Properties
  In Proc. of 42nd FOCS, pages 460-469, IEEE, 2001.
  Also accepted for publication in Random Structures and Algorithms
  [Journal version]
• Bernard Chazelle, Ronitt Rubinfeld and Luca Trevisan
  Approximating the Minimum Spanning Tree Weight in Sublinear Time
  In Proc. of 28th ICALP, pages 190-200, Springer-Verlag, 2001.
  [Conference Proceedings]

Exploratory work on data compression

• Luca Trevisan, Salil Vadhan and David Zuckerman
  Compression of Samplable Sources
  In Proc. of 19th Computational Complexity Conference, pages 1-14, IEEE, 2004
  [Conference Proceedings]
• Hoeteck Wee
  On Pseudoentropy versus Compressibility
  In Proc. of 19th Computational Complexity Conference, pages 29-41, IEEE, 2004
  

Educational Work

I designed a Computational Complexity course for beginning graduate students with a strong emphasis on recent results on probabilistically checkable proofs and on derandomization. The use of error-correcting codes in such applications is abstracted, and coding-theoretic results are presented as well.

• Home page of the Spring'01 class, Lecture notes (165 pages)
• Home page of the Fall'02 class, Lecture notes (171 pages)

David Wagner and I designed a cryptography course with a focus on both formal proofs of security and applications.
Click here to see the syllabus and download lecture notes for almost every lecture.

I designed a course on applications of coding theory to computational complexity. The first half of the course was a general introduction to algorithmic coding theory, and the second half presented applications to cryptography, average case complexity and probabilistically checkable proofs. After the class, I wrote a survey paper on applications of coding theory to complexity.

• Home page of class on applications of coding theory to complexity
• Survey paper  (52 pages)
   

I wrote a survey on inapproximability results.

• Survey paper (39 pages)