Some Talks by Oded Goldreich

This webpage records very old slides and more recent PPT presentations for various talks. The organization and annotation is quite tentative.

• General opinions
  • On graduate studies (2008).
  • Demystifying the Master Thesis: 2009, 2024
  • Some advice to some aspiring researchers and critique of some priviledged scientists (2017)
  • On Content-Oblivious Measures of Research Quality: WIS (2021), BGU (2015), A4E (2017)
• Surveys
  • On P, NP and NPC: P vs NP (PPT 2011), a wider perspective alas more concise, and P, NP, and NPC (slides 2008).
  • On Randomness and Computation (brief overviews): A PPT (2013). See also 10 slides (2008) and 4 slides (2008).
  • On the Foundations of Cryptography: CRYPTO97
  • The Bright Side of Hardness (cf. Cryptography): 2008. (See also old slides).
  • On Pseudorandomness: 2024. See older short (2008) and long (2006) versions (also same in lower resolution)
  • On Probabilistic Proof Systems: 2024 and 10-minute talk on IP and ZK. See older slides from 1994 and 2008 (light)
  • On doubly-efficient Interactive Proof Systems: 2017
  • On Property Testing: 2013 and 2018 (short)
  • On average-case complexity (2008)
  • On Distributed Computation: two slides (2008)
• Specific works: Cryptography and Complexity
  • How to Solve any Protocol Problem [GMW87]: A relatively recent PPT (2022), which is a revision of 2010, and very old slides (1980s).
  • On Private Information Retrieval (slides from the 1990s): 1 and 2
  • A candidate one-way function based on expander graphs: slides from the 2000s
  • Some thoughts on unconditional derandomization RANDOM10; see also In a World of BPP=P (2011).
  • On Quantified Derandomization (2014/5): a photo and a PPTX
  • On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions 2016 (and 2014).
• Specific works: Property Testing
  • On Proximity Oblivius Testers (2008): 1, 2, and 3
  • On testing computability by small width OBDDs (2010)
  • Proximity Oblivious Testers and the Role of Invariances (2011)
  • Testing Graph Blow-ups (2011)
  • Finding cycles and trees in sublinear time (2013)
  • A double feature (on property testing): combining the two forgoing talks (2011).
  • On Multiple-Instance Problems in Property Testing 2014
  • A double feature (on property testing): combining the above talk with a presetation on lower bounds based on communication complexity (2013).
  • On Testing Dynamic Environments: notes (2016)
  • Every Set in P is Strongly Testable Under a Suitable Encoding (2019)
  • Vertex-Distribution-Free Testing of Graphs (2019)
  • On testing subgraphs (2019).
  • Adaptivity vs Non-adaptivity in the context of Testing Graphs in the Dense Model (2021).
  • 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.
• Personal angles
  • Thanking the Celebrators of my 60th B-day (2017): welcome (pptx) and farewell (txt)
  • On Shafi and Silvio (2013): metaphors and stories (presented at at MIT, ??, and at WIS).
  • On Avi (vs Shafi and Silvio): the flight story (2013).
  • A gift to Shafi (2019)
  • On Benny Chor: 2017 and 2021
  • Introducing Boaz, Irit, Johan, Salil and Dick Karp (2013)
  • The Knuth lecture (2017): html, pdf, and pptx

Back to Oded Goldreich's homepage.