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

Work on cryptography


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

Work on sub-linear time algorithms

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.