ETH FalseRyan ODonnell2026-11-17 | ETH FalseThe secret GCD method they didnt teach you in school.Ryan ODonnell2022-12-19 | A video about the Greatest Common Divisor, and also brushing your teeth. Scratch app: https://scratch.mit.edu/projects/778900018
Script assistance: Alex Tolon Thumbnail/title assistance: Mark O'Donnell and Alex Tolon
Music by DJ Q-Bert, from the album Wave Twisters.This ONE Instruction Instantly Makes Scratch Into A Quantum Computer!!Ryan ODonnell2022-09-03 | Try it out! https://scratch.mit.edu/projects/725831669/editor
If you like this video, smash that H.A.T.! button!
Title and thumbnail creation by Alex Tolon.Quantum Monte Carlo: Mean Estimation when you have the source codeRyan ODonnell2022-08-21 | Tired of remembering all the different quantum quadratic speedups... Grover, quantum counting, amplitude estimation...? Just remember this one simple trick -- Grover with complex phases!
Opening tune: "Cathexis", by Nothing Painted Blue. Prof. Bruno, this video is for mathematical education purposes only; as a guy who once used the word 'lemma' in a song, I hope you don't mind.
Closing tune: "Above Average", by Teen Ravine. Glad you liked the idea, Nicky :)
Some fonts by Tom7: http://tom7.orgThe SYK Model: Classical and Quantum AlgorithmsRyan ODonnell2022-06-22 | Can quantum computers solve problems in quantum chemistry exponentially more efficiently than classical ones? In this talk, based on joint work with Matt Hastings ("Optimizing Strongly Interacting Fermionic Hamiltonians", arxiv.org/abs/2110.10701), I discuss the optimization problem for fermionic Hamiltonians, the SYK model, and new classical and quantum algorithms.
Opening tune: "Black Hole Sun" by Soundgarden, performed by Haley Reinhardt and Scott Bradlee's Postmodern Jukebox. Sorry they're playing ads on the video.
Closing tune: "S.O.S." by Abba, performed by the great Dwayne Gretzky, dwaynegretzkyband.comLearning About Quantum States 8: Learning the eigenvectors via GL(d) representation theoryRyan ODonnell2022-06-03 | I describe a bit about the representation theory of the general linear group GL(d), highest weight vectors, and how these lead to Keyl's method for estimating the eigenvectors of an unknown quantum state.
Opening tune by Salt-N-Pepa-N-Spinderella. Thumbnail İznik ceramic from Gallery 460 of The Met. Forgot to mention in previous credits: Hockey Is Lif font by Tom7.Learning About Quantum States 7: Majorization theorems for the RSK processRyan ODonnell2022-06-02 | I discuss two purely combinatorial theorems about the RSK process applied to random words; both concern how the Young diagram you get in one scenario majorizes the Young diagram you get in another scenario.
Opening tune by Bahamadia. Thumbnail İznik ceramic from Gallery 460 of The Met.Learning About Quantum States 6: Central Limit Theorems and more for the RSK process on random wordsRyan ODonnell2022-06-01 | Suppose you form a random word of length n, where the letters are chosen i.i.d. from a probability distribution p = (p_1, ..., p_d) (probabilities in descending order). Let lambda be the Young diagram resulting from passing the word through the RSK process. We expect the normalized row lengths (lambda_1/n, ..., lambda_d/n) to be close to (p_1, ..., p_d). But how close? Does a Central Limit Theorem hold? Is a Central Limit Theorem even good enough?
Opening tune is C-Mone rapping with The Streets. Thumbnail İznik ceramic from Gallery 460 of The Met.Learning About Quantum States 5: The Robinson Schensted Knuth AlgorithmRyan ODonnell2022-05-31 | The RSK (Robinson--Schensted--Knuth) algorithm is explained through Pokémon. Also mentioned is Greene's Theorem and the Vershik--Kerov Theorem saying that when the RSK is a random n-letter word with letter probabilities p_1, ..., p_d, the jth row of the resulting Young diagram will asymptotically have ~p_j n boxes.
Opening rap by Myrtle Sarrosa. Thumbnail İznik ceramic from Gallery 460 of The Met.Learning About Quantum States 4: The Schur Weyl DistributionRyan ODonnell2022-05-30 | If you are trying to learn about about a mixed quantum state, and you only care about its 'probabilities' (eigenvalues), then the optimal measurement you can perform on n copies is the "Schur--Weyl measurement", which returns a Young diagram (sorted histogram) from the "Schur--Weyl distribution".
Opening tune is Ladybug Mecca from Digable Planets. Thumbnail İznik ceramic from Gallery 460 of The Met.Learning About Quantum States 3: Very Balanced or Very Rigged?Ryan ODonnell2022-05-29 | For quantum (and classical) dice, how to tell if they are 'very rigged' (almost pure) or 'very balanced' (close to maximally mixed) from just two copies, using the decomposition into the Symmetric and Alternating subspaces.
Opening tune by Dee & Atach Tatuq. Thumbnail İznik ceramic from Gallery 460 of The Met.Learning About Quantum States 2: Quantum Dice, and MeasurementsRyan ODonnell2022-05-28 | The classical and quantum concepts of randomness sources (dice, and quantum mixed states); classical and quantum events; and, classical and quantum measurements.
Opening tune by Jean Grae (as What What) and Herbaliser. Thumbnail İznik ceramic from Gallery 460 of The Met.Learning About Quantum States 1: Intro to Quantum ComputationRyan ODonnell2022-05-27 | The introduction to a multi-part series on learning quantum states (quantum tomography).
Opening tune by Sampa The Great. Thumbnail İznik ceramic from Gallery 460 of The Met.
Bugfix: the phrase "mix quantum state" on the final screen should say "𝐦𝐢𝐱𝐞𝐝 quantum state"!Entropy, and cryptographic pseudorandom generators || @ CMU || Recitation 12 of CS Theory ToolkitRyan ODonnell2022-04-27 | In this recitation/OH, we talk about the two problems on Homework #11: bounding the entropy of a funny random variable (and how one might 'invent' conditional entropy and mutual information); and, how to show security of a cryptographic PRG of stretch poly(n) built from a cryptographic PRG of stretch 1.
Recitation 12 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)A problem re the k-Consistency Algorithm for CSPs || @ CMU || Recitation 11 of CS Theory ToolkitRyan ODonnell2022-04-21 | In this recitation/OH, we talk about one problem on Homework #10, concerning the "k-consistency algorithm" for CSPs, and how it (supposedly) works correctly and efficiently on any instance whose primal has treewidth at most k. Recitation 11 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Semidefinite relaxation problems || @ CMU || Recitation 10 of CS Theory ToolkitRyan ODonnell2022-04-14 | In this recitation/OH, we talk about one problem on Homework #9, which concerns a semidefinite programming relaxation for the 'Betweenness' problem. Recitation 10 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)High-Dimensional Expanders: How I learned to stop worrying and love group-theoretic constructionsRyan ODonnell2022-04-08 | A talk based on joint work with Kevin Pratt ( https://www.cs.cmu.edu/~kpratt/ ): "High-Dimensional Expanders from Chevalley Groups" (arxiv.org/abs/2203.03705)
In this presentation I talk about high- (well, mostly 2-)dimensional expanders, graphs of constant link (and why they are tough to find), and motivations for using group theory to construct HDXes. There's also some Classification of Finite Simple Groups stuff in there.
All music used without permission for educational purposes.Linear Programming problems, and Convex Programming || @ CMU || Recitation 9 of CS Theory ToolkitRyan ODonnell2022-03-30 | In this recitation/OH, we talk a bit about Homework #8, which involves problems on linear programming, but more time is spent just chit-chatting about convex programming, duality, and kernel methods in machine learning. Recitation 8 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Spectral Graph Theory problems || @ CMU || Recitation 8 of CS Theory ToolkitRyan ODonnell2022-03-23 | In this recitation/OH, we talk about Homework #7, which involves problems on spectral graph theory. Recitation 8 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Error Correcting Codes problems || @ CMU || Recitation 7 of CS Theory ToolkitRyan ODonnell2022-03-02 | In this recitation/OH, we talk about Homework #6, which involves problems on coding theory (and derandomization, which we didn't get to). Recitation 7 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Finite fields and Grover rotations || @ CMU || Recitation 6 of CS Theory ToolkitRyan ODonnell2022-02-24 | In this recitation/OH, we talk about Homework #5, including the analogy between Grover's algorithm and pucks sliding toward a wall, and the analogy between finite fields geometry and regular geometry. Recitation 6 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Fourier, Decision Trees, Learning Algorithms || @ CMU || Recitation 5 of CS Theory ToolkitRyan ODonnell2022-02-16 | In this recitation/OH, we talk about Homework #4, all things Fourier, including the Fourier coefficients of decision trees, learning functions under the uniform distribution, and solving kSUM-type problems. Recitation 5 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Moments, Concentration, and Initializing an Array || @ CMU || Recitation 4 of CS Theory ToolkitRyan ODonnell2022-02-09 | In this recitation/OH, we talk about Homework #3. Recitation 4 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Layer cakes and slivers || @ CMU || Recitation 3 of CS Theory ToolkitRyan ODonnell2022-02-02 | In this recitation/OH, we talk about Homework #2, involving Stirling's formula, Berry--Esseen, and the Layer Cake formula for expectations. Recitation 3 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Inequalities, asymptotics, primes || @ CMU || Homework 1 / Recitation 2 of CS Theory ToolkitRyan ODonnell2022-01-26 | Recitation #2 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)The Central Binomial Coefficient || @ CMU || Recitation 1 of CS Theory ToolkitRyan ODonnell2022-01-19 | Asymptotics of the Central Binomial Coefficient. Recitation 1 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Panteleev Kalachev Codes: Asymptotically good quantum LDPC codes and classical LTCsRyan ODonnell2021-12-24 | In this talk I (try to) describe the breakthrough construction of quantum LDPC codes of linear distance and dimension, as well as the breakthrough construction of classical locally testable codes of linear distance and dimension, due to Pavel Panteleev and Gleb Kalachev: arxiv.org/abs/2111.03654
Opening music "I Wish I Had An Evil Twin" by Stephin Merritt/The Magnetic Fields (Nonesuch Records). Closing music "Square One" by InI/Pete Rock (BBE Records). Used without permission for educational purposes.Quantum Computing with Just 1 Qubit | The Elitzur Vaidman Bomb AlgorithmRyan ODonnell2021-12-21 | A description of the laws of quantum computing with just one qubit, and the Elitzur--Vaidman 'bomb-detection algorithm'.
Music: "The Rest of My Life", by Sloan (murderecords), used without permission, thanks guys! Thumbnail also from the video, directed by Wendy Morgan.
Outro music from My Dear Kuttichathan, by Ilaiyaraaja.The Switching LemmaRyan ODonnell2021-08-30 | A complete proof of Håstad's form of the Switching Lemma, following a long line of proof ideas from Furst--Saxe--Sipser through Thapen.
Opening tune "Switch" by Will Smith, Universal Music Group / Interscope. Closing tune "Dancing Queen" by Abba, performed by Gunhild Carling and Scott Bradlee's Postmodern Jukebox. Both used without permission, but I hope it's okay, it's all for educational purposes.Pauli error estimation via Population RecoveryRyan ODonnell2021-07-01 | A very simple method for learning a Pauli channel. Joint work with Steve Flammia (Amazon), presented at TQC 2021.
Title tune written and produced by Ray Davies, performed by the Kinks. Used without permission of Sanctuary Records, for educational purposes only!Improved Quantum Data Analysis (Shadow Tomography)Ryan ODonnell2021-02-06 | A talk on a paper (arxiv.org/abs/2011.10908) joint with Costin Bădescu (costinbadescu.com) that solves the (adaptive) Quantum Shadow Tomography problem with the best known dependence on m (the number of observables to estimate), d (the dimension of the unknown state), and epsilon (the error tolerance for the estimates). I also explain the connections between this problem and the classical problem of Adaptive Data Analysis.
The following were all used without permission... thanks very much in advance, I hope no one minds, it's all for strictly educational purposes only. . Cuphead images by StudioMDHR Entertainment (http://www.cupheadgame.com) . Cuphead music by Kristofer Maddigan (open.spotify.com/artist/2jR6Lr47O21Iq7l5Bs2mig) . Minit images by Devolver Digital . Ranking website layout by speedrun.com . Celeste character images by Matt Makes Games . Dream image by Dream (youtube.com/c/dream) . Home: We're Finally Landing music by Randy Goffe (soundcloud.com/home-2001) . Concept of using said music by Summoning Salt (youtube.com/c/SummoningSalt) . Super Mario images by Nintendo . Mario speedrun comparison image by Bismuth (youtube.com/user/BismuthWasTaken)Fiber bundle codes: Breaking the N¹ᐟ² polylog(N) barrier for quantum LDPC codesRyan ODonnell2020-10-12 | Talk by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell) on a paper -- arxiv.org/abs/2009.03921 -- that achieves quantum LDPC (CSS) codes on N qubits with minimum distance essentially N³ᐟ⁵.
First premiered at the UT Austin Quantum Information Center.
Intro music by The Pharcyde / Brand New Heavies for Craft Recording. Outro music by Abbey House Lessons and Isolated Tracks. Thumbnail image by Paul Martinson.
UPDATE: the bug about weight reduction has been fixed; see the latest version of the paper on the arXiv.Fourier Analysis of Boolean Functions, in Harvards CS 121 class. Learning, quantum, voting, & more!Ryan ODonnell2020-09-27 | A very brief introduction to Fourier Analysis of Boolean Functions, given by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell) as an enrichment lesson in Harvard's CS 121 course.
Thanks to Madhu Sudan for inviting me to give this lecture.
Thumbnail portrait by @tichaesqueRyan ODonnell Live StreamRyan ODonnell2020-08-31 | ...Dinurs proof of the PCP Theorem: the Powering step || @ CMU || Lecture 27d of CS Theory ToolkitRyan ODonnell2020-07-24 | The final and most important piece of Dinur's proof of the PCP Theorem by gap amplification: Powering. Lecture 27d of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture: Course on "The PCP Theorem and Hardness of Approximation" by O'Donnell and Guruswami, https://courses.cs.washington.edu/courses/cse533/05au/
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Dinurs PCP: degree-reduction, expanderizing, mini-PCP || @ CMU || Lecture 27c of CS Theory ToolkitRyan ODonnell2020-07-23 | The three more 'standard' parts of Irit Dinur's proof of the PCP Theorem (though there are innovations in these steps, too): degree-reduction, expanderizing, and alphabet-reduction (AKA composition with a constant-size PCPP). Lecture 27c of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture: Course on "The PCP Theorem and Hardness of Approximation" by O'Donnell and Guruswami, https://courses.cs.washington.edu/courses/cse533/05au/
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Dinurs Proof of the PCP Theorem: outline || @ CMU || Lecture 27b of CS Theory ToolkitRyan ODonnell2020-07-22 | An outline of Dinur's iterative proof of the PCP Theorem by "gap amplification". Lecture 27b of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture: Course on "The PCP Theorem and Hardness of Approximation" by O'Donnell and Guruswami, https://courses.cs.washington.edu/courses/cse533/05au/
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Statement of the PCP Theorem || @ CMU || Lecture 27a of CS Theory ToolkitRyan ODonnell2020-07-21 | Remarks about the PCP Theorem, Dinur's proof of it, and a full statement of the theorem, including its hardness-of-approximation interpretation and its proof-checking interpretation. Lecture 27a of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture: Course on "The PCP Theorem and Hardness of Approximation" by O'Donnell and Guruswami, https://courses.cs.washington.edu/courses/cse533/05au/
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)NP-Hardness of Approximation || @ CMU || Lecture 26e of CS Theory ToolkitRyan ODonnell2020-07-20 | The powerful theorems on NP-hardness of approximation: Raz and Raz--Moshkovitz's Label-Cover hardness, and a discussion of Unique Games. Lecture 26e of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture:
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Exponential Time Hypotheses: ETH and SETH || @ CMU || Lecture 26d of CS Theory ToolkitRyan ODonnell2020-07-17 | NP ≠ P tells us that k-SAT is not in polynomial time, but just how much non-polynomial time *does* it take? This is the subject of the ETH (Exponential Time Hypothesis) and SETH (Strong Exponential Time Hypothesis). Lecture 26d of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture:
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Hardness of Random 3XOR and 3Sat || @ CMU || Lecture 26c of CS Theory ToolkitRyan ODonnell2020-07-16 | Sparse Parities with Noise and Håstad's 3XOR NP-hardness of approximation. Also, the hardness of random 3Sat, and Feige's Hypothesis.
Lecture 26c of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Learning Parity with Noise|| @ CMU || Lecture 26b of CS Theory ToolkitRyan ODonnell2020-07-15 | The LPN Assumption (LWE's cousin over the finite field of size 2). Lecture 26b of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture:
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Hardness Assumptions Beyond NP ≠ P || @ CMU || Lecture 26a of CS Theory ToolkitRyan ODonnell2020-07-14 | The beginning of a lecture about alternative hardness assumptions beyond just the usual "NP ≠ P". Lecture 26 of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Learning With Errors (LWE) and Public Key Encryption || @ CMU || Lecture 25d of CS Theory ToolkitRyan ODonnell2020-07-13 | Concepts such as Public Key Encryption, Trapdoor Permutations, the important LWE (Learning With Errors) problem, and lattice-based cryptography. Lecture 25d of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture: "A course in cryptography" by Pass and Shelat.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)From One-Way Functions to Symmetric Key Encryption || @ CMU || Lecture 25c of CS Theory ToolkitRyan ODonnell2020-07-10 | Definitions of cryptographic pseudorandom generators (PRGs), one-way functions (OWFs), and related concepts. The famous [HILL] Theorem proving that PRGs and hence symmetric key encryption (SKE) can be constructed from (weak) OWFs is mentioned, as are Impagliazzo's Five Worlds. Lecture 25c of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture: "A course in cryptography" by Pass and Shelat.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Computational Indistinguishability || @ CMU || Lecture 25b of CS Theory ToolkitRyan ODonnell2020-07-09 | The definition of "computational indistinguishability" for probabilistic ensembles, and the main workhorse in crypto proofs: the Hybrid Argument. Lecture 25b of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture: "A course in cryptography" by Pass and Shelat.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Intro to Cryptography || @ CMU || Lecture 25a of CS Theory ToolkitRyan ODonnell2020-07-08 | Symmetric (shared) Key Encryption, the One-Time Pad, computationally bounded adversaries. Lecture 25a of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture: "A course in cryptography" by Pass and Shelat.
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Information Complexity || @ CMU || Lecture 24c of CS Theory ToolkitRyan ODonnell2020-07-07 | Information Complexity: a modern way to understand communication complexity. Includes a sketch of how the linear lower bound on the randomized communication complexity of Disjointness is proven. Lecture 24c of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resources for this lecture: . "Elements of Information Theory" by Cover and Thomas . Slides and notes of Mark Braverman
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Mutual Information || @ CMU || Lecture 24b of CS Theory ToolkitRyan ODonnell2020-07-06 | The basics of Mutual Information in information theoory. Lecture 24b of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resources for this lecture: . "Elements of Information Theory" by Cover and Thomas . Slides and notes of Mark Braverman
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Entropy || @ CMU || Lecture 24a of CS Theory ToolkitRyan ODonnell2020-07-03 | The basics definitions and intuitions for entropy. Lecture 24a of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resources for this lecture: . "Elements of Information Theory" by Cover and Thomas . Slides and notes of Mark Braverman
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (rebeccakphoto.com)Yaos Minimax Theorem & IP_2s Communication Complexity || @ CMU || Lecture 23d of CS Theory ToolkitRyan ODonnell2020-07-02 | Herein: the statement of Yao's Minimax Theorem, the main tool for proving randomized communication complexity lower bounds; and, using this and Fourier analysis of Boolean functions to show that the randomized communication complexity of the inner-product-mod-2 function is linear.
Lecture 23d of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resources for this lecture: "Communication Complexity", book by Kushilevitz and Mansour "Communication Complexity and Applications", book by Rao and Yehudayoff
Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/