Some Talks by Oded Goldreich

All files are in the directory T, which contains an index file.

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).
• Demystifing the master thesis (and research in general): Take 1 (2009), Take 2 (2024),
• 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.
  • teaser: (net) four slides (intended for a grant proposal presentation).
  • 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.
• General Cryptographic Protocols (aka Secure Multi-Party Computation). Prepared for Joachim von zur Gathen's 60th B-day, Bonn, Germany, 2010.
  Old slides on how to solve any protopcol problem, late 1980s.
• RC: a candidate one-way function, 2000?
• RC: Private Information Retreival, 1995.

Probabilistic Proof Systems (see surveys and papers)

• A new 50-minute talk (2024).
• 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 LevinFest, July 2024, Boston, US.
  See old slides and notes, prepared for the Workshop on Randomness and Complexity, July 2006, Bristol, England.
• 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)

• Property Testing: Sublinear-Time Approximate Decision, an introduction, Jan 2013.
• 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.
• RC: A property testing double feature: On the Communication Complexity Methodology for proving Lower Bounds and on Multiple Input Problems, June 2013.
• RC: On Learning and Testing Dynamic Environments (laconic notes, 2016).
• RC: Every Set in P is Strongly Testable Under a Suitable Encoding (2019)
• RC: Vertex-Distribution-Free Testing of Graphs (2019)
• RC: On testing subgraphs (2019).
• RC: Adaptivity vs Non-adaptivity in the context of Testing Graphs in the Dense Model (2021).
• RC: Testing Distributions of Huge Objects (2022).
• Recent developments in testing bounded degree graphs, Aug 2024.
• On the importance of scale: Reflections on some of Ronitt Rubinfeld's works, Aug 2024.

Other aspects of complexity theory

• 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).
• RC: Boolean Circuits of Depth Three and Arithmetic Circuits with Arbitrary Gates, March 2014.
• RC: On Derandomizing Algorithms that Err Extremely Rarely, Oct 2014. (+ photo from a board talk, Feb 2015.)

MISC.

• Shafi and Silvio Fests (at MIT and WIS, 2013): dull stories, a perspective on their works, and some favorite metaphors.
• On Content-Oblivious Quality Measures: a short presentation (Hebrew), 2015.
• Some advice to some aspiring researchers and critique of some priviledged scientists (2017)