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 sublinear 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 averagecase complexity, pseudorandomness and randomness extraction

Andrej Bogdanov and Luca Trevisan
On WorstCase to AverageCase Reductions for NP Problems
In Proc. of 44th FOCS,
IEEE, pp. 308317, 2003
[Draft full version] [Conference
Proceedings]

Luca Trevisan
List Decoding Using the XOR Lemma
In Proc. of 44th FOCS,
IEEE, pp. 126135, 2003
[Conference Proceedings]

Elchanan Mossel, Amir Shpilka and Luca Trevisan
On epsilonBiased Generators in NC0
In Proc. of 44th FOCS,
IEEE, pp. 136145, 2003
[Manuscript]

Luca Trevisan and Salil Vadhan
Pseudorandomness and Averagecase Complexity via Uniform Reductions
In Proc. of 17th
Computational Complexity Conference, pages 129138, IEEE,
2002
[Conference proceedings]

Z. BarYossef, O. Reingold, R. Shaltiel and L. Trevisan
Streaming Computation of Combinatorial Objects
In Proc. of 17th
Computational Complexity Conference, pages165174, 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 305313, IEEE, 2000
[Conference proceedings]

Luca Trevisan and Salil Vadhan.
Extracting Randomness from Samplable Distributions
In Proc. of 41st FOCS,
pages 3242, IEEE, 2000
[Conference proceedings]
Work on cryptography
Work on PCP, hardness of approximation, and locally decodable codes

L. Trevisan
Nonapproximability 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 175183, IEEE, 2002
[Manuscript]
Work on sublinear 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 3Colorability in Boundeddegree Graphs
In Proc. of 43rd FOCS,
pages 93102, IEEE, 2002
[Conference Proceedings]

Oded Goldreich and Luca Trevisan
Three Theorems Regarding Testing Graph Properties
In Proc. of 42nd
FOCS, pages 460469, 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 190200, SpringerVerlag, 2001.
[Conference
Proceedings]
Exploratory work on data compression
Educational Work
I gave lectures on pseudorandomness at the IAS/PCMI
summer school on computational complexity.
These are the lecture
notes from the lectures.
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 errorcorrecting codes
in such applications is abstracted, and codingtheoretic results are presented
as well.
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.
I wrote a survey on inapproximability results.