Sciences formelles & physiques Informatique & CybersécuritéFRThe Switching LemmaRyan O'Donnell30 août 2021 30 min★ ★ ★ ★ ★ 5/5Switching LemmaHåstadAC0
Sciences formelles & physiques Informatique & CybersécuritéFRIQIS Lecture 6.2 — Abstract computation and reversible computationArtur Ekert8 mars 2021 17 min★ ★ ★ ★ ☆ 4/5Computation RéversiblePorte De ToffoliInformatique Quantique
Sciences formelles & physiques Informatique & CybersécuritéFRP=NP?Richard E Borcherds20 janvier 2021 39 min★ ★ ★ ★ ☆ 4/5P=NPComplexité AlgorithmiqueInformatique Théorique
Sciences formelles & physiques Informatique & CybersécuritéFRAQIS '20: Zhengfeng Ji, Spooky complexity at a distanceZhengfeng Ji22 décembre 2020 67 min★ ★ ★ ★ ★ 5/5MIP*Preuves Interactives QuantiquesProblème De Tsirelson
Sciences formelles & physiques Informatique & CybersécuritéFRAQIS '20: François Le Gall, Average-Case Quantum Advantage with Shallow CircuitsFrançois Le Gall22 décembre 2020 57 min★ ★ ★ ★ ☆ 4/5Complexité QuantiqueCircuits QuantiquesSéparation De Classes
Sciences formelles & physiques Informatique & CybersécuritéFRNoisy Variational Quantum Algorithm Simulation lecture by Yipeng HuangYipeng Huang9 août 2020 55 min★ ★ ★ ★ ☆ 4/5Algorithme VariationnelBruit QuantiqueSimulation De Circuits
Sciences formelles & physiques Informatique & CybersécuritéFRDinur's proof of the PCP Theorem: the Powering step || @ CMU || Lecture 27d of CS Theory ToolkitRyan O'Donnell24 juillet 2020 18 min★ ★ ★ ★ ★ 5/5PCP TheoremDinurPowering
Sciences formelles & physiques Informatique & CybersécuritéFRDinur's PCP: degree-reduction, expanderizing, mini-PCP || @ CMU || Lecture 27c of CS Theory ToolkitRyan O'Donnell23 juillet 2020 25 min★ ★ ★ ★ ☆ 4/5Théorème PCPExpandeursComplexité
Sciences formelles & physiques Informatique & CybersécuritéFRDinur's Proof of the PCP Theorem: outline || @ CMU || Lecture 27b of CS Theory ToolkitRyan O'Donnell22 juillet 2020 29 min★ ★ ★ ★ ☆ 4/5Théorème PCPPreuve De DinurAmplification De Trou
Sciences formelles & physiques Informatique & CybersécuritéFRStatement of the PCP Theorem || @ CMU || Lecture 27a of CS Theory ToolkitRyan O'Donnell21 juillet 2020 14 min★ ★ ★ ★ ☆ 4/5Théorème PCPComplexité AlgorithmiquePreuves Vérifiables Probabilistiquement
Sciences formelles & physiques Informatique & CybersécuritéFRNP-Hardness of Approximation || @ CMU || Lecture 26e of CS Theory ToolkitRyan O'Donnell20 juillet 2020 16 min★ ★ ★ ★ ★ 5/5NP-DuretéApproximationLabel Cover
Sciences formelles & physiques Informatique & CybersécuritéFRIntuition on models and their complexityDr. Eitan Farchi20 juillet 2020 18 min★ ★ ★ ☆ ☆ 3/5ModèleComplexitéSur-Apprentissage
Sciences formelles & physiques Informatique & CybersécuritéFRExponential Time Hypotheses: ETH and SETH || @ CMU || Lecture 26d of CS Theory ToolkitRyan O'Donnell17 juillet 2020 23 min★ ★ ★ ★ ★ 5/5ETHSETHComplexité
Sciences formelles & physiques Informatique & CybersécuritéFRHardness of Random 3XOR and 3Sat || @ CMU || Lecture 26c of CS Theory ToolkitRyan O'Donnell16 juillet 2020 23 min★ ★ ★ ★ ★ 5/5ComplexitéNP-Dureté3SAT
Sciences formelles & physiques Informatique & CybersécuritéFRComputational Indistinguishability || @ CMU || Lecture 25b of CS Theory ToolkitRyan O'Donnell9 juillet 2020 13 min★ ★ ★ ★ ☆ 4/5CryptographieIndistingabilité ComputationnelleHybrid Argument
Sciences formelles & physiques Informatique & CybersécuritéFRInformation Complexity || @ CMU || Lecture 24c of CS Theory ToolkitRyan O'Donnell7 juillet 2020 28 min★ ★ ★ ★ ☆ 4/5Complexité De CommunicationThéorie De L'informationInformatique Théorique
Sciences formelles & physiques Informatique & CybersécuritéFRYao's Minimax Theorem & IP_2's Communication Complexity || @ CMU || Lecture 23d of CS Theory ToolkitRyan O'Donnell2 juillet 2020 19 min★ ★ ★ ★ ★ 5/5Complexité De CommunicationThéorème Minimax De YaoAnalyse De Fourier
Sciences formelles & physiques Informatique & CybersécuritéFRRandomized Communication Complexity || @ CMU || Lecture 23c of CS Theory ToolkitRyan O'Donnell1 juillet 2020 13 min★ ★ ★ ★ ☆ 4/5Complexité De CommunicationRandomisationThéorie De L'information
Sciences formelles & physiques Informatique & CybersécuritéFRDeterministic Communication Complexity || @ CMU || Lecture 23b of CS Theory ToolkitRyan O'Donnell30 juin 2020 37 min★ ★ ★ ★ ★ 5/5Complexité De CommunicationInformatique ThéoriqueProtocoles
Sciences formelles & physiques Informatique & CybersécuritéFRBasics of Communication Complexity || @ CMU || Lecture 23a of CS Theory ToolkitRyan O'Donnell29 juin 2020 19 min★ ★ ★ ★ ★ 5/5Complexité De CommunicationInformatique ThéoriqueAlgorithmes
Sciences formelles & physiques Informatique & CybersécuritéFRGreat Ideas in Theoretical Computer Science: Introduction (Spring 2016) reupload with improved audioRyan O'Donnell28 juin 2020 72 min★ ★ ★ ★ ☆ 4/5Informatique ThéoriqueAlgorithmesComplexité
Sciences formelles & physiques Informatique & CybersécuritéFRTreewidth Definitions || @ CMU || Lecture 22b of CS Theory ToolkitRyan O'Donnell25 juin 2020 32 min★ ★ ★ ★ ★ 5/5TreewidthThéorie Des GraphesComplexité Algorithmique
Sciences formelles & physiques Informatique & CybersécuritéFRPseudoexpectations || @ CMU || Lecture 21(d) of CS Theory ToolkitRyan O'Donnell23 juin 2020 13 min★ ★ ★ ★ ☆ 4/5PseudoexpectationsSherali-AdamsSOS
Sciences formelles & physiques Informatique & CybersécuritéFRThe Sum-of-Squares (SOS) Proof System || @ CMU || Lecture 21(c) of CS Theory ToolkitRyan O'Donnell22 juin 2020 22 min★ ★ ★ ★ ★ 5/5Sum-of-SquaresPreuvesOptimisation Combinatoire
Sciences formelles & physiques Informatique & CybersécuritéFRProof Complexity for CSPs || @ CMU || Lecture 21a of CS Theory ToolkitRyan O'Donnell18 juin 2020 12 min★ ★ ★ ★ ☆ 4/5Complexité Des PreuvesCSPProgrammation Linéaire
Sciences formelles & physiques Informatique & CybersécuritéFRCSP Approximability: Optimization and Certification || @ CMU || Lecture 20c of CS Theory ToolkitRyan O'Donnell17 juin 2020 33 min★ ★ ★ ★ ★ 5/5CSPApproximationComplexité
Sciences formelles & physiques Informatique & CybersécuritéFRConstraint Satisfaction Problems || @ CMU || Lecture 20b of CS Theory ToolkitRyan O'Donnell16 juin 2020 31 min★ ★ ★ ★ ★ 5/5CSPSatisfiabilitéDichotomie
Sciences formelles & physiques Informatique & CybersécuritéFRGoemans--Williamson: Rounding the Max-Cut SDP || @ CMU || Lecture 20a of CS Theory ToolkitRyan O'Donnell15 juin 2020 31 min★ ★ ★ ★ ★ 5/5Max-CutSDPGoemans-Williamson
Sciences formelles & physiques Informatique & CybersécuritéFRThe SDP Relaxation for Max-Cut || @ CMU || Lecture 19b of CS Theory ToolkitRyan O'Donnell11 juin 2020 33 min★ ★ ★ ★ ★ 5/5Max-CutSDPOptimisation
Sciences formelles & physiques Informatique & CybersécuritéFRMin-st-Cut is the dual LP of Max-st-Flow || @ CMU || Lecture 18d of CS Theory ToolkitRyan O'Donnell9 juin 2020 19 min★ ★ ★ ★ ★ 5/5Dualité en Programmation LinéaireFlot MaximalCoupe Minimale
Sciences formelles & physiques Informatique & CybersécuritéFRRounding LP Solutions: Min-Vertex-Cover || @ CMU || Lecture 18c of CS Theory ToolkitRyan O'Donnell8 juin 2020 17 min★ ★ ★ ★ ★ 5/5Programmation LinéaireVertex CoverApproximation
Sciences formelles & physiques Informatique & CybersécuritéFRRelaxing ILPs to LPs: Bipartite Max-Perfect-Matching || @ CMU || Lecture 18b of CS Theory ToolkitRyan O'Donnell5 juin 2020 28 min★ ★ ★ ★ ★ 5/5Programmation LinéaireCouplage ParfaitGraphe Biparti
Sciences formelles & physiques Informatique & CybersécuritéFRExpander Graph Application 2: Derandomization || @ CMU || Lecture 16c of CS Theory ToolkitRyan O'Donnell4 mai 2020 22 min★ ★ ★ ★ ☆ 4/5Graphes ExpanseursDérandomisationComplexité
Sciences formelles & physiques Informatique & CybersécuritéFRCheeger's Inequality || @ CMU || Lecture 15d of CS Theory ToolkitRyan O'Donnell3 mai 2020 61 min★ ★ ★ ★ ★ 5/5Inégalité De CheegerThéorie Spectrale Des GraphesConductance
Sciences formelles & physiques Informatique & CybersécuritéFREpsilon-biased Generators || @ CMU || Lecture 12d of CS Theory ToolkitRyan O'Donnell23 avril 2020 23 min★ ★ ★ ★ ☆ 4/5Epsilon-Biased GeneratorsPseudorandomnessCodes Correcteurs
Sciences formelles & physiques Informatique & CybersécuritéFRImpagliazzo--Wigderson, and Nisan's PRGs || @ CMU || Lecture 12b of CS Theory ToolkitRyan O'Donnell21 avril 2020 12 min★ ★ ★ ★ ☆ 4/5ComplexitéPseudo-AléatoireDérandomisation
Sciences formelles & physiques Informatique & CybersécuritéFRSpooky Complexity at a DistanceZhengfeng Ji20 avril 2020 77 min★ ★ ★ ★ ★ 5/5MIP*=REPreuves InteractivesIntrication Quantique
Sciences formelles & physiques Informatique & CybersécuritéFRPseudorandom Generators || @ CMU || Lecture 12a of CS Theory ToolkitRyan O'Donnell20 avril 2020 20 min★ ★ ★ ★ ☆ 4/5PseudorandomnessDérandomisationBPP
Sciences formelles & physiques Informatique & CybersécuritéFRMultivariate Polynomials and the Schwartz--Zippel Lemma || @ CMU || Lecture 10e of CS Theory ToolkitRyan O'Donnell28 mars 2020 18 min★ ★ ★ ★ ★ 5/5Polynômes MultivariésLemme De Schwartz-ZippelComplexité Algorithmique
Sciences formelles & physiques Informatique & CybersécuritéFRCommunication Complexity of Equality || @ CMU || Lecture 10d of CS Theory ToolkitRyan O'Donnell27 mars 2020 15 min★ ★ ★ ★ ★ 5/5Complexité De CommunicationPolynômesCorps Finis
