Some Talks by Oded Goldreich

I intend to make a collection of scanned slides of some of my past talks and all of my future talks (i.e., starting 2008). Note that the files dating prior to 2008 are the result of scanning handwritten slides.

See also my list of publication and list of papers available on-line.

The talks are arranged by topics. In each topic, survey talks come first, and research contributions (marked RC) follow.

General Overviews

• A short orientation talk for graduate students (at Weizmann): generic (3 slides) and randomness and computation (4 slides).
• The P-vs-NP Question and NP-completeness:
  • On the limitation of efficient computation [slides for a presentation for wide WIS audience].
  • Is solving harder than checking? [slides for a 45-minute popular talk].
  • A short overview intended for a general audience, prepared for the Shimon Even Memorial Lecture, MTA, June 2005.
• Randomness and Computation: general overviews.
  • skeleton: four slides (intended for graduate students at Weizmann).
  • brief overview: ten slides.

Foundations of Cryptography (see surveys and a two-volume book)

• The bright side of hardness: Demomstrates the usefulness of computational intractability (in cryptography). Prepared for the mini-Workshop on Cryptography of ECM08, July 2008, Amsterdam, The Netherlands.
  See slides and notes.
  (Superseeds a shorter presentation (4 slides + extras), prepared for an advanced undergraduate class (Tsinghua University, Beijing, China, April 2006).)
• On the Foundations of Modern Cryptography: Advocating the need for firm foundations. Prepared for Crypto'97, Santa Barbara, Cal., USA.
• RC: a candidate one-way function, 2000?
• RC: Private Information Retreival, 1995.

Probabilistic Proof Systems (see surveys and papers)

• A very high-level overview, intended for general seminars, very light on the technical details, prepared in the late 1990s, last revised 2008.
• A slightly more detailed overview, also intended for general seminars, prepared for ICM94, updated and revised in 2003.

Pseudorandomness (see surveys and papers)

• An overview of the general paradigm and some of its instantiations, prepared for the Workshop on Randomness and Complexity, July 2006, Bristol, England.
  See slides and notes.
• A short survey focused on general-purpose pseudorandom generators, somewhat technical, prepared in 1989.
• RC: In a world of BPP=P, see also some thoughts regarding unconditional derandomization, August 2010.

Property Testing (see surveys and papers)

• RC: On Proximity Oblivious Testing, 2008/09.
• RC: On Testing Computability by Small Width OBDDs, August 2010.
• RC: Finding Cycles and Trees in Sublinear Time, May 2011.

MISC.

• A survey of average-case complexity, 1989.
  Note: the "unnatural" distributional versions (of natural NPC problems) that are mentioned in slide 17 refer to a relaxed definition of P-computable distributions (which allows arbitrary efficiently computable order of strings).