page under construction
Extractors
[Construction of Extractors Using Pseudorandom Generators]
presentation at STOC'99, May 1999.
[Randomness Extractors and Pseudorandom Generators]
interview talk at Berkeley, Feb. 2000.
[Error-correcting codes and pseudorandom projections]
invited talk at Random'01, August 2001.
Locally decodable codes
[Sublinear Time Error-Correction and Error-Detection]
DIMACS Workshop on sublinear time algorithms, Sept. 2000.
[Sublinear Time Error-Correction and Error-Detection]
Berkeley EECS Colloquium, Oct. 2000.
PCP
[Recycling Queries in PCPs and in Linearity Tests]
presentation at STOC'98.
[Probabilistically Checkable Proofs with Low Amortized Query Complexity]
presentation at FOCS'98.
[A PCP Characterization of NP with Optimal Amortized Query Complexity]
presentation at STOC'00.
[A PCP Characterization of NP with Optimal Amortized Query Complexity]
talk given in several places, including IAS and Oberwolfach.
Property testing
[Lower Bounds for Property Testing]
talk given at Microsoft Research, June 2002
[Lower Bounds for Property Testing]
talk given at Bay Area Theory Symposium, October 2002
[Lower Bounds for Property Testing]
talk given at Oberwolfach, April 2003
MST
[Approximating the MST Weight in Sublinear Time]
talk given at IBM Almaden, May 2001
[Approximating the MST Weight in Sublinear Time]
presentation at ICALP'01
Cryptography
[On the Efficiency of Two Generic Cryptographic Constructions]
talk given at DIMACS workshop, May 2002