Formal & Physical Sciences Computing & CybersecurityENSimon's Algorithm: Lecture 13 of Quantum Computation at CMURyan O'DonnellOctober 23, 2018 81 min★ ★ ★ ★ ★ 5/5Simon's AlgorithmQuantum ComputingFourier Sampling
Formal & Physical Sciences Computing & CybersecurityENRevealing XOR-patterns II: Lecture 12 of Quantum Computation at CMURyan O'DonnellOctober 18, 2018 81 min★ ★ ★ ★ ★ 5/5Quantum ComputingFourier TransformHadamard Transform
Formal & Physical Sciences Computing & CybersecurityENRevealing XOR-patterns I: Lecture 11 of Quantum Computation at CMURyan O'DonnellOctober 14, 2018 83 min★ ★ ★ ★ ★ 5/5Quantum ComputingXORHadamard Transform
Formal & Physical Sciences Computing & CybersecurityENBasics of Quantum Computing: Lecture 10 of Quantum Computation at CMURyan O'DonnellOctober 11, 2018 82 min★ ★ ★ ★ ★ 5/5Quantum ComputingCircuit ModelReversible Computation
Formal & Physical Sciences Science — General & HistoryENQuantum Money: Lecture 9 of Quantum Computation at CMURyan O'DonnellOctober 6, 2018 84 min★ ★ ★ ★ ★ 5/5Quantum MoneyQuantum CryptographyNo-Cloning Theorem
Formal & Physical Sciences PhysicsENNo Cloning Theorem, and Quantum Teleportation: Lecture 8 of Quantum Computation at CMURyan O'DonnellOctober 4, 2018 82 min★ ★ ★ ★ ★ 5/5Quantum ComputingNo-Cloning TheoremQuantum Teleportation
Formal & Physical Sciences Computing & CybersecurityENThe CHSH Game: Lecture 7 of Quantum Computation at CMURyan O'DonnellSeptember 29, 2018 53 min★ ★ ★ ★ ★ 5/5CHSH GameQuantum EntanglementBell's Inequality
Formal & Physical Sciences Computing & CybersecurityENPartial Measurements and Spooky Action at a Distance: Lecture 6 of Quantum Computation at CMURyan O'DonnellSeptember 22, 2018 82 min★ ★ ★ ★ ☆ 4/5Quantum ComputationPartial MeasurementEntanglement
Formal & Physical Sciences PhysicsENMultiplying By A Global Phase Doesn't Make A Difference: Lecture 5.5 of Quantum Computation at CMURyan O'DonnellSeptember 22, 2018 11 min★ ★ ★ ★ ☆ 4/5Quantum ComputationGlobal PhaseQuantum States
Formal & Physical Sciences Computing & CybersecurityENMulti-Qubit Systems: Lecture 5 of Quantum Computation at CMURyan O'DonnellSeptember 19, 2018 82 min★ ★ ★ ★ ★ 5/5Quantum ComputingMulti-Qubit SystemsTensor Product
Formal & Physical Sciences Computing & CybersecurityENDiscriminating Two Qubits: Lecture 4.5 of Quantum Computation at CMURyan O'DonnellSeptember 16, 2018 17 min★ ★ ★ ★ ☆ 4/5Quantum ComputingQubit DiscriminationQuantum Measurement
Formal & Physical Sciences Computing & CybersecurityENUnitary Transformations and the Elitzur--Vaidman Bomb: Lecture 4 of Quantum Computation at CMURyan O'DonnellSeptember 14, 2018 81 min★ ★ ★ ★ ★ 5/5Quantum ComputingUnitary TransformationsElitzur-Vaidman Bomb
Formal & Physical Sciences PhysicsENUnderstanding and Measuring One Qubit: Lecture 3 of Quantum Computation and Information at CMURyan O'DonnellSeptember 13, 2018 81 min★ ★ ★ ★ ★ 5/5Quantum ComputingQubitQuantum Mechanics
Formal & Physical Sciences Computing & CybersecurityENRotate, Compute, Rotate: Lecture 2 of Quantum Computation and Information at CMURyan O'DonnellSeptember 8, 2018 80 min★ ★ ★ ★ ☆ 4/5Quantum ComputingProbabilistic ComputingPrimality Testing
Formal & Physical Sciences Computing & CybersecurityEN10^500 Parallel Universes: Lecture 1 of Quantum Computation and Information at CMURyan O'DonnellSeptember 6, 2018 68 min★ ★ ★ ★ ☆ 4/5Quantum ComputingComputational ComplexityMany-Worlds Interpretation
Formal & Physical Sciences Computing & CybersecurityENToda's 2nd Theorem and lower bounds for uniform ACC: Graduate Complexity Lecture 23 at CMURyan O'DonnellDecember 15, 2017 76 min★ ★ ★ ★ ★ 5/5Toda's TheoremACC CircuitsComplexity Theory
Formal & Physical Sciences Computing & CybersecurityENRazborov--Smolensky lower bounds for AC0[p]: Graduate Complexity Lecture 22 at CMURyan O'DonnellDecember 15, 2017 72 min★ ★ ★ ★ ★ 5/5Circuit ComplexityLower BoundsAC0
Formal & Physical Sciences Computing & CybersecurityENIronic complexity: Graduate Complexity Lecture 27 at CMURyan O'DonnellDecember 15, 2017 79 min★ ★ ★ ★ ★ 5/5Complexity TheoryCircuit Lower BoundsNEXP
Formal & Physical Sciences Computing & CybersecurityENHardness vs. Randomness II: Graduate Complexity Lecture 25 at CMURyan O'DonnellDecember 15, 2017 77 min★ ★ ★ ★ ★ 5/5Complexity TheoryPseudorandomnessBPP
Formal & Physical Sciences Computing & CybersecurityENHardness vs. Randomness I: Graduate Complexity Lecture 24 at CMURyan O'DonnellDecember 15, 2017 82 min★ ★ ★ ★ ★ 5/5Computational ComplexityHardness vs RandomnessPseudorandom Generators
Formal & Physical Sciences Computing & CybersecurityENHardness amplification: Graduate Complexity Lecture 26 at CMURyan O'DonnellDecember 15, 2017 79 min★ ★ ★ ★ ★ 5/5Hardness AmplificationYao's XOR LemmaImpagliazzo's Hard-Core Set Lemma
Formal & Physical Sciences Computing & CybersecurityENMonotone circuit lower bounds: Graduate Complexity Lecture 21 at CMURyan O'DonnellNovember 19, 2017 83 min★ ★ ★ ★ ★ 5/5Complexity TheoryMonotone CircuitsLower Bounds
Formal & Physical Sciences Computing & CybersecurityENToda's 1st Theorem and the Permanent: Graduate Complexity Lecture 14 at CMURyan O'DonnellNovember 12, 2017 78 min★ ★ ★ ★ ★ 5/5Toda's TheoremPermanentComplexity Theory
Formal & Physical Sciences Computing & CybersecurityENPermanent is #P-complete: Graduate Complexity Lecture 20 (out of order) at CMURyan O'DonnellNovember 12, 2017 73 min★ ★ ★ ★ ★ 5/5#P-CompletenessPermanentComplexity Theory
Formal & Physical Sciences Computing & CybersecurityENThe Switching Lemma: PRST version: Graduate Complexity Lecture 19 at CMURyan O'DonnellNovember 8, 2017 55 min★ ★ ★ ★ ★ 5/5Switching LemmaComputational ComplexityCircuit Complexity
Formal & Physical Sciences Computing & CybersecurityENAlgebraic "NP vs. P" vs. "Boolean NP vs. P": Graduate Complexity Lecture 15 postscript at CMURyan O'DonnellNovember 7, 2017 14 min★ ★ ★ ★ ★ 5/5Computational ComplexityAlgebraic ComplexityP vs NP
Formal & Physical Sciences Computing & CybersecurityENRandom Restrictions and AC0 Circuit Lower Bounds: Graduate Complexity Lecture 18 at CMURyan O'DonnellNovember 5, 2017 79 min★ ★ ★ ★ ★ 5/5AC0Circuit Lower BoundsRandom Restrictions
Formal & Physical Sciences Computing & CybersecurityENIP = PSPACE: Graduate Complexity Lecture 17 at CMURyan O'DonnellNovember 5, 2017 78 min★ ★ ★ ★ ★ 5/5Computational ComplexityInteractive ProofsPSPACE
Formal & Physical Sciences Computing & CybersecurityENInstance Checking and the Permanent: Graduate Complexity Lecture 16 at CMURyan O'DonnellNovember 5, 2017 80 min★ ★ ★ ★ ★ 5/5Computational ComplexityPermanentInstance Checking
Formal & Physical Sciences Computing & CybersecurityENAlgebraic Circuit Complexity: Graduate Complexity Lecture 15 at CMURyan O'DonnellNovember 5, 2017 80 min★ ★ ★ ★ ★ 5/5Algebraic ComplexityArithmetic CircuitsComplexity Theory
Formal & Physical Sciences Computing & CybersecurityENValiant--Vazirani Theorem, and Exact Counting (#P): Graduate Complexity Lecture 13 at CMURyan O'DonnellOctober 21, 2017 76 min★ ★ ★ ★ ★ 5/5Computational ComplexityValiant-Vazirani#P
Formal & Physical Sciences Computing & CybersecurityENApproximate counting: Graduate Complexity Lecture 12 at CMURyan O'DonnellOctober 21, 2017 79 min★ ★ ★ ★ ★ 5/5Computational ComplexityApproximate CountingInteractive Proofs
Formal & Physical Sciences Computing & CybersecurityENMore on constant-round interactive proof systems: Graduate Complexity Lecture 12 at CMURyan O'DonnellOctober 19, 2017 81 min★ ★ ★ ★ ★ 5/5Computational ComplexityInteractive ProofsMA
Formal & Physical Sciences Computing & CybersecurityENIntroduction to Arthur-Merlin classes, MA and AM: Graduate Complexity Lecture 10 at CMURyan O'DonnellOctober 19, 2017 82 min★ ★ ★ ★ ★ 5/5Complexity TheoryArthur-MerlinMA
Formal & Physical Sciences Computing & CybersecurityENTime/Space Tradeoffs for SAT: Graduate Complexity Lecture 9 at CMURyan O'DonnellOctober 3, 2017 91 min★ ★ ★ ★ ★ 5/5Complexity TheorySATTime-Space Tradeoff
Formal & Physical Sciences Computing & CybersecurityENThe Polynomial Time Hierarchy: Graduate Complexity Lecture 7 at CMURyan O'DonnellSeptember 29, 2017 79 min★ ★ ★ ★ ★ 5/5Complexity TheoryPolynomial HierarchyNP
Formal & Physical Sciences Computing & CybersecurityENOracles, and the Polynomial Time Hierarchy vs. circuits: Graduate Complexity Lecture 8 at CMURyan O'DonnellSeptember 29, 2017 82 min★ ★ ★ ★ ★ 5/5Computational ComplexityOracle Turing MachinesPolynomial Time Hierarchy
Formal & Physical Sciences Computing & CybersecurityENQuasilinear Cook--Levin Theorem: Graduate Complexity Lecture 6 at CMURyan O'DonnellSeptember 22, 2017 77 min★ ★ ★ ★ ★ 5/5Cook-Levin TheoremQuasilinear TimeComplexity Theory
Formal & Physical Sciences Computing & CybersecurityENProbabilistic Complexity Classes: Graduate Complexity Lecture 5 at CMURyan O'DonnellSeptember 19, 2017 80 min★ ★ ★ ★ ★ 5/5Complexity TheoryProbabilistic Turing MachinesBPP
Formal & Physical Sciences Computing & CybersecurityENHopcroft--Paul--Valiant Theorem: Graduate Complexity Lecture 3 at CMURyan O'DonnellSeptember 18, 2017 80 min★ ★ ★ ★ ★ 5/5Complexity TheorySpace ComplexityTime Complexity
![Razborov--Smolensky lower bounds for AC0[p]: Graduate Complexity Lecture 22 at CMU](https://i.ytimg.com/vi/TI-xKI3Uy4E/maxresdefault.jpg)
