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
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
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 error-correcting codes
in such applications is abstracted, and coding-theoretic 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.