Some Talks by Oded Goldreich

last updated: June 2022

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 2017 2017
- Some advice to aspiring researchers (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 (2006-08): short and long (also same in lower resolution)
- On Probabilistic Proof Systems: 2021. 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).
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.