Goemans--Williamson: Rounding the Max-Cut SDP || @ CMU || Lecture 20a of CS Theory Toolkit
Goemans--Williamson: Arrondi du SDP de Max-Cut || @ CMU || Leçon 20a du CS Theory Toolkit
★
★
★
★
★
5/5
Ryan O'Donnell
@RyanODonnellTeaching
Solving the Max-Cut SDP || @ CMU || Lecture 19c of CS Theory Toolkit
Résoudre le SDP Max-Cut || @ CMU || Cours 19c du CS Theory Toolkit
★
★
★
★
☆
4/5
The SDP Relaxation for Max-Cut || @ CMU || Lecture 19b of CS Theory Toolkit
La relaxation SDP pour Max-Cut || @ CMU || Conférence 19b de CS Theory Toolkit
★
★
★
★
★
5/5
The Ellipsoid Algorithm || @ CMU || Lecture 19a of CS Theory Toolkit
L'algorithme de l'ellipsoïde || @ CMU || Conférence 19a du CS Theory Toolkit
★
★
★
★
★
5/5
Min-st-Cut is the dual LP of Max-st-Flow || @ CMU || Lecture 18d of CS Theory Toolkit
Min-st-Cut est le programme linéaire dual de Max-st-Flow || @ CMU || Cours 18d du CS Theory Toolkit
★
★
★
★
★
5/5
Rounding LP Solutions: Min-Vertex-Cover || @ CMU || Lecture 18c of CS Theory Toolkit
Arrondir les solutions LP : Min-Vertex-Cover || @ CMU || Cours 18c de CS Theory Toolkit
★
★
★
★
★
5/5
Relaxing ILPs to LPs: Bipartite Max-Perfect-Matching || @ CMU || Lecture 18b of CS Theory Toolkit
Relaxation des ILP en LP : Bipartite Max-Perfect-Matching || @ CMU || Leçon 18b du CS Theory Toolkit
★
★
★
★
★
5/5
Max-st-Flow is an LP || @ CMU || Lecture 18a of CS Theory Toolkit
Max-st-Flow est un LP || @ CMU || Cours 18a de CS Theory Toolkit
★
★
★
★
☆
4/5
Linear Programming: Optimization Reduces to Feasibility || @ CMU || Lecture 17d of CS Theory Toolkit
Programmation Linéaire : L'Optimisation se Réduit à la Faisabilité || @ CMU || Cours 17d du Kit d'Outils de Théorie CS
★
★
★
★
☆
4/5
Linear Programming: Bit Complexity || @ CMU || Lecture 17c of CS Theory Toolkit
Programmation linéaire : Complexité des bits || @ CMU || Conférence 17c de la boîte à outils de théorie CS
★
★
★
★
★
5/5
Linear Programming Duality || @ CMU || Lecture 17b of CS Theory Toolkit
Dualité de la programmation linéaire || @ CMU || Cours 17b de CS Theory Toolkit
★
★
★
★
★
5/5
Linear Programming: Definitions || @ CMU || Lecture 17a of CS Theory Toolkit
Programmation linéaire : Définitions || @ CMU || Leçon 17a de CS Theory Toolkit
★
★
★
★
☆
4/5
Expander Graphs Overview || @ CMU || Lecture 16a of CS Theory Toolkit
Aperçu des graphes expanseurs || @ CMU || Cours 16a de CS Theory Toolkit
★
★
★
★
★
5/5
Expander Graphs Application 1: Good Codes || @ CMU || Lecture 16b of CS Theory Toolkit
Application des graphes expanseurs 1 : Bons codes || @ CMU || Cours 16b de CS Theory Toolkit
★
★
★
★
☆
4/5
Expander Graph Constructions || @ CMU || Lecture 16d of CS Theory Toolkit
Constructions de graphes expanseurs || @ CMU || Conférence 16d du CS Theory Toolkit
★
★
★
★
☆
4/5
Expander Graph Application 2: Derandomization || @ CMU || Lecture 16c of CS Theory Toolkit
Application Expander Graph 2 : Dérandomisation || @ CMU || Cours 16c du module CS Theory Toolkit
★
★
★
★
☆
4/5
Cheeger's Inequality || @ CMU || Lecture 15d of CS Theory Toolkit
Inégalité de Cheeger || @ CMU || Cours 15d du module d'outils de théorie informatique
★
★
★
★
★
5/5
Spectral Graph Theory: mixing time || @ CMU || Lecture 15c of CS Theory Toolkit
Théorie spectrale des graphes : temps de mélange || @ CMU || Conférence 15c du CS Theory Toolkit
★
★
★
★
☆
4/5
Spectral Graph Theory: conductance and Sparsest-Cut || @ CMU || Lecture 15b of CS Theory Toolkit
Théorie spectrale des graphes : conductance et coupe la plus clairsemée || @ CMU || Cours 15b de la boîte à outils de théorie CS
★
★
★
★
☆
4/5
Spectral Graph Theory: eigenvalues || @ CMU || Lecture 15a of CS Theory Toolkit
Théorie spectrale des graphes : valeurs propres || @ CMU || Cours 15a du CS Theory Toolkit
★
★
★
★
★
5/5
Spectral Graph Theory: the Laplacian, and the Spectral Theorem || @ CMU || 14b of CS Theory Toolkit
Théorie spectrale des graphes : le laplacien et le théorème spectral || @ CMU || 14b de CS Theory Toolkit
★
★
★
★
★
5/5
Spectral Graph Theory: the Markov transition operator || @ CMU || Lecture 14a of CS Theory Toolkit
Théorie spectrale des graphes : l'opérateur de transition de Markov || @ CMU || Conférence 14a du CS Theory Toolkit
★
★
★
★
☆
4/5
Spectral Graph Theory: Minimizing/Maximizing the Quadratic Form || @ CMU || 13d of CS Theory Toolkit
Théorie spectrale des graphes : minimiser/maximiser la forme quadratique || @ CMU || 13e du CS Theory Toolkit
★
★
★
★
★
5/5
Spectral Graph Theory: Enter Linear Algebra || @ CMU || Lecture 13c of CS Theory Toolkit
Théorie spectrale des graphes : entrez dans l'algèbre linéaire || @ CMU || Conférence 13c du kit d'outils de théorie de l'informatique
★
★
★
★
☆
4/5
Spectral Graph Theory: The Standard Random Walk || @ CMU || Lecture 13b of CS Theory Toolkit
Théorie spectrale des graphes : La marche aléatoire standard || @ CMU || Leçon 13b du CS Theory Toolkit
★
★
★
★
★
5/5
Spectral Graph Theory: The Quadratic Form || @ CMU || Lecture 13a of CS Theory Toolkit
Théorie spectrale des graphes : La forme quadratique || @ CMU || Conférence 13a sur la boîte à outils de la théorie CS
★
★
★
★
★
5/5
Epsilon-biased Generators || @ CMU || Lecture 12d of CS Theory Toolkit
Générateurs à polarisation epsilon || @ CMU || Cours 12d du module d'outils de théorie informatique
★
★
★
★
☆
4/5
k-wise Independent Generators || @ CMU || Lecture 12c of CS Theory Toolkit
Générateurs indépendants k-sages || @ CMU || Leçon 12c de la boîte à outils de théorie CS
★
★
★
★
☆
4/5
Impagliazzo--Wigderson, and Nisan's PRGs || @ CMU || Lecture 12b of CS Theory Toolkit
Impagliazzo--Wigderson, et les PRG de Nisan || @ CMU || Conférence 12b du kit d'outils de théorie CS
★
★
★
★
☆
4/5
Pseudorandom Generators || @ CMU || Lecture 12a of CS Theory Toolkit
Générateurs pseudo-aléatoires || @ CMU || Cours 12a du module d'outils théoriques en informatique
★
★
★
★
☆
4/5
Asymptotically "Good" Codes || @ CMU || Lecture 11e of CS Theory Toolkit
Codes asymptotiquement « bons » || @ CMU || Cours 11e de la boîte à outils de théorie informatique
★
★
★
★
☆
4/5
Reed--Solomon Codes || @ CMU || Lecture 11d of CS Theory Toolkit
Codes Reed-Solomon || @ CMU || Cours 11d du module d'outils théoriques en informatique
★
★
★
★
★
5/5
Hamming Code and Hadamard Code || @ CMU || Lecture 11c of CS Theory Toolkit
Code de Hamming et code Hadamard || @ CMU || Cours 11c de la boîte à outils de théorie informatique
★
★
★
★
★
5/5
Linear Error Correcting Codes || @ CMU || Lecture 11b of CS Theory Toolkit
Codes Correcteurs d'Erreurs Linéaires || @ CMU || Conférence 11b du CS Theory Toolkit
★
★
★
★
☆
4/5
Error Correcting Codes || @ CMU || Lecture 11a of CS Theory Toolkit
Codes correcteurs d'erreurs || @ CMU || Cours 11a du module de théorie de l'informatique
★
★
★
★
☆
4/5
Multivariate Polynomials and the Schwartz--Zippel Lemma || @ CMU || Lecture 10e of CS Theory Toolkit
Polynômes multivariés et le lemme de Schwartz--Zippel || @ CMU || Leçon 10e du CS Theory Toolkit
★
★
★
★
★
5/5
Communication Complexity of Equality || @ CMU || Lecture 10d of CS Theory Toolkit
Complexité de communication de l'égalité || @ CMU || Cours 10d du CS Theory Toolkit
★
★
★
★
★
5/5
Non-Prime Fields || @ CMU || Lecture 10c of CS Theory Toolkit
Corps non premiers || @ CMU || Cours 10c du module d'outils théoriques en informatique
★
★
★
★
★
5/5
Primes and Prime Fields || @ CMU || Lecture 10b of CS Theory Toolkit
Nombres premiers et corps premiers || @ CMU || Cours 10b de CS Theory Toolkit
★
★
★
★
☆
4/5
Expander Graphs (full lecture) || @ CMU || Lecture 16 of CS Theory Toolkit
Expander Graphs (conférence complète) || @ CMU || Conférence 16 de CS Theory Toolkit
★
★
★
★
★
5/5