Mathematical theory of computation

Intuition on models and their complexity

Nos algorithmes pourraient-ils être BEAUCOUP plus rapides ? (P=NP ?)

Could our algorithms be MUCH faster? (P=NP?)

Exponential Time Hypotheses: ETH and SETH || @ CMU || Lecture 26d of CS Theory Toolkit

Hardness of Random 3XOR and 3Sat || @ CMU || Lecture 26c of CS Theory Toolkit

Computational Indistinguishability || @ CMU || Lecture 25b of CS Theory Toolkit

Information Complexity || @ CMU || Lecture 24c of CS Theory Toolkit

Yao's Minimax Theorem & IP_2's Communication Complexity || @ CMU || Lecture 23d of CS Theory Toolkit

Randomized Communication Complexity || @ CMU || Lecture 23c of CS Theory Toolkit

Deterministic Communication Complexity || @ CMU || Lecture 23b of CS Theory Toolkit

Basics of Communication Complexity || @ CMU || Lecture 23a of CS Theory Toolkit

Great Ideas in Theoretical Computer Science: Introduction (Spring 2016) reupload with improved audio

Treewidth Definitions || @ CMU || Lecture 22b of CS Theory Toolkit

Pseudoexpectations || @ CMU || Lecture 21(d) of CS Theory Toolkit

The Sum-of-Squares (SOS) Proof System || @ CMU || Lecture 21(c) of CS Theory Toolkit

Proof Complexity for CSPs || @ CMU || Lecture 21a of CS Theory Toolkit

CSP Approximability: Optimization and Certification || @ CMU || Lecture 20c of CS Theory Toolkit

Constraint Satisfaction Problems || @ CMU || Lecture 20b of CS Theory Toolkit

Goemans--Williamson: Rounding the Max-Cut SDP || @ CMU || Lecture 20a of CS Theory Toolkit

The SDP Relaxation for Max-Cut || @ CMU || Lecture 19b of CS Theory Toolkit

Min-st-Cut is the dual LP of Max-st-Flow || @ CMU || Lecture 18d of CS Theory Toolkit

Rounding LP Solutions: Min-Vertex-Cover || @ CMU || Lecture 18c of CS Theory Toolkit

Relaxing ILPs to LPs: Bipartite Max-Perfect-Matching || @ CMU || Lecture 18b of CS Theory Toolkit

Expander Graph Application 2: Derandomization || @ CMU || Lecture 16c of CS Theory Toolkit

Cheeger's Inequality || @ CMU || Lecture 15d of CS Theory Toolkit

Epsilon-biased Generators || @ CMU || Lecture 12d of CS Theory Toolkit

Impagliazzo--Wigderson, and Nisan's PRGs || @ CMU || Lecture 12b of CS Theory Toolkit

Pseudorandom Generators || @ CMU || Lecture 12a of CS Theory Toolkit

CQC2T Colloquium/QSI Seminar: Prof Zhengfeng Ji, QSI, Spooky Complexity at a Distance, 26/03/2020

Multivariate Polynomials and the Schwartz--Zippel Lemma || @ CMU || Lecture 10e of CS Theory Toolkit

Communication Complexity of Equality || @ CMU || Lecture 10d of CS Theory Toolkit

Analysis of Boolean functions: Applications || @ CMU || Lecture 8c of CS Theory Toolkit

Boolean Fourier formulas || @ CMU || Lecture 8b of CS Theory Toolkit

Fourier Analysis of Boolean functions || @ CMU || Lecture 8a of CS Theory Toolkit

Complexity of Basic Arithmetic || @ CMU || Lecture 7a of CS Theory Toolkit

The Word RAM Model || @ CMU || Lecture 6c of CS Theory Toolkit

Computational Models: Circuits || @ CMU || Lecture 6b of CS Theory Toolkit

Computational Models: Turing Machines || @ CMU || Lecture 6a of CS Theory Toolkit

How to do CS Theory || @ CMU || Lecture 1b of CS Theory Toolkit

CS Theory Toolkit: Course Outline || @ CMU || Lecture 1a

The Adversary Method: Lecture 20 of Quantum Computation at CMU