Sign inSign in

Ryan O'Donnell is a Carnegie Mellon computer science professor known for the analysis of Boolean functions and quantum computation.

More

Ryan O'Donnell is a Carnegie Mellon computer science professor known for the analysis of Boolean functions and quantum computation. O'Donnell's courses span undergraduate complexity theory to graduate quantum computation, proving IP = PSPACE, Valiant's theorem and the Chernoff bound.

lectures
199
series
6
hours
173

Start here

Series and courses

CMU 15-859BB: Quantum Computation and Quantum Information27 lectures · 34 h
CMU 15-455: Undergraduate Complexity Theory24 lectures · 32 h
CMU 15-859: Analysis of Boolean Functions22 lectures · 28 h
CMU 15-855: Graduate Computational Complexity Theory27 lectures · 36 h
Quantum Computer Programming in 100 Easy Lessons7 lectures · 2 h
CMU 15-750: A Theorist's Toolkitfrom O'Donnell, Analysis of Boolean Functions89 lectures · 38 h
Open the course
  1. 1How to do CS Theory35:51
  2. 2Street Fighting Mathematics26:11
  3. 3Big O and friends28:10
  4. 4Harmonic Numbers Asymptotics22:18
Show 85 more
  1. 5Asymptotics Tricks25:01
  2. 6Birthday Paradox Asymptotics18:10
  3. 7Factorial Asymptotics, Stirling's Formula28:26
  4. 8Binomial Coefficients Asymptotics35:57
  5. 9Central Limit Theorem24:22
  6. 10Gaussian Random Variables38:31
  7. 11Berry–Esseen Theorem16:07
  8. 12Markov and Chebyshev Inequalities38:22
  9. 13Proof of the Chernoff Bound24:34
  10. 14Chernoff, Hoeffding, etc. bounds17:47
  11. 15Computational Models: Turing Machines25:31
  12. 16Computational Models: Circuits29:07
  13. 17The Word RAM Model25:30
  14. 18Complexity of Basic Arithmetic26:58
  15. 19Multiplication via the Discrete Fourier Transform26:04
  16. 20Fast Fourier Transform (FFT) and Integer Multiplication25:34
  17. 21Fourier Analysis of Boolean Functions32:22
  18. 22Boolean Fourier Formulas34:16
  19. 23Analysis of Boolean Functions: Applications in Social Choice13:58
  20. 24Quantum Computing Overview14:34
  21. 25Axioms of Quantum Computing40:46
  22. 26Grover's Algorithm23:22
  23. 27Primes and Prime Fields16:13
  24. 28Non-Prime Fields20:46
  25. 29Communication Complexity of Equality15:16
  26. 30Multivariate Polynomials and the Schwartz Zippel Lemma18:29
  27. 31Error Correcting Codes16:40
  28. 32Linear Error Correcting Codes20:01
  29. 33Hamming Code and Hadamard Code21:46
  30. 34Reed Solomon Codes12:31
  31. 35Pseudorandom Generators20:34
  32. 36Impagliazzo T Wigderson, and Nisan's Pseudorandom Generators12:19
  33. 37k-wise Independent Generators26:07
  34. 38Epsilon-Biased Generators23:25
  35. 39Spectral Graph Theory: The Quadratic Form22:24
  36. 40Spectral Graph Theory: The Standard Random Walk24:39
  37. 41Spectral Graph Theory: Linear Algebra and Irregular Graphs20:24
  38. 42Spectral Graph Theory: Minimizing and Maximizing the Quadratic Form33:26
  39. 43Spectral Graph Theory: The Markov Transition Operator41:10
  40. 44Spectral Graph Theory: The Laplacian and the Spectral Theorem37:39
  41. 45Spectral Graph Theory III: Eigenvalues of the Laplacian22:13
  42. 46Spectral Graph Theory: Conductance and Sparsest-Cut18:04
  43. 47Spectral Graph Theory III: Mixing Time39:28
  44. 48Cheeger's Inequality1:01:40
  45. 49Expander Graphs Overview28:27
  46. 50Expander Graphs Application 1: Good Codes26:04
  47. 51Expander Graph Application 2: Derandomization22:36
  48. 52Expander Graph Constructions48:34
  49. 53Linear Programming Duality22:15
  50. 54Linear Programming: Bit Complexity24:40
  51. 55Linear Programming: Optimization Reduces to Feasibility22:41
  52. 56Max-st-Flow is a Linear Program14:30
  53. 57Relaxing Integer Linear Programs to Linear Programs: Bipartite Maximum Perfect Matching28:44
  54. 58Rounding LP Solutions: Minimum Vertex Cover17:35
  55. 59Min-st-Cut is the Dual LP of Max-st-Flow19:15
  56. 60The Ellipsoid Algorithm30:49
  57. 61The Semidefinite Programming Relaxation for Max-Cut33:22
  58. 62Solving the Max-Cut SDP15:42
  59. 63Goemans-Williamson Algorithm: Rounding the Max-Cut SDP31:43
  60. 64Constraint Satisfaction Problems31:32
  61. 65CSP Approximability: Optimization and Certification33:10
  62. 66Proof Complexity for CSPs: Sherali-Adams and Sum-of-Squares Proof Systems12:48
  63. 67The Sherali-Adams Proof System36:44
  64. 68The Sum-of-Squares (SOS) Proof System22:18
  65. 69Pseudoexpectations13:57
  66. 70Trees and Series-Parallel Graphs21:09
  67. 71Treewidth Definitions32:08
  68. 72Algorithms for Bounded Treewidth28:38
  69. 73Basics of Communication Complexity19:56
  70. 74Deterministic Communication Complexity37:08
  71. 75Yao's Minimax Theorem and IP2\mathrm{IP}_2's Communication Complexity19:42
  72. 76Entropy24:36
  73. 77Mutual Information28:16
  74. 78Information Complexity28:00
  75. 79Introduction to Cryptography: Symmetric Key Encryption and the One-Time Pad16:33
  76. 80Computational Indistinguishability13:46
  77. 81From One-Way Functions to Symmetric Key Encryption27:18
  78. 82Learning With Errors (LWE) and Public Key Encryption25:54
  79. 83Hardness of Random 3XOR and 3Sat23:28
  80. 84Exponential Time Hypotheses: ETH and SETH23:55
  81. 85NP-Hardness of Approximation16:27
  82. 86Statement of the PCP Theorem14:05
  83. 87Dinur's Proof of the PCP Theorem: Outline29:02
  84. 88Dinur's PCP Theorem: Degree-Reduction, Expanderizing, and Mini-PCP25:47
  85. 89Dinur's Proof of the PCP Theorem: The Powering Step18:49
Talks3 lectures · 4 h

In these lectures

Draws on

People cited in the lectures, at the moment of the citation.

  • Peter ShorPublished a polynomial-time algorithm for factoring on a quantum computer in 1994.44:50
  • Claude Shannon1949 paper showing every function on n bits has a circuit of size order 2n/n2^n / n.20:34
  • Ryan WilliamsMIT computer science researcher whose PhD thesis work on SAT lower bounds is cited.3:35
  • Johan HåstadCited for his work on hardness of approximation and dictatorship tests.0:21
  • Manuel BlumFaculty member at the university.0:40
  • László BabaiPublished a 2016 paper giving a quasi-polynomial time algorithm for Graph Isomorphism.1:16:08

Playlists

4

About

Ryan O'Donnell is a Carnegie Mellon computer science professor known for the analysis of Boolean functions and quantum computation. O'Donnell's courses span undergraduate complexity theory to graduate quantum computation, proving IP = PSPACE, Valiant's theorem and the Chernoff bound.

Connections

213

Their places, courses, books and lectures.

Institutions4

Book1

Lectures199

Show 193 more