–
Existentially Polytime Theorems

Jack Edmonds (University of Waterloo)
Video
–
Hypotheses about Satisfiability and their Consequences

Russell Impagliazzo (UC San Diego)
Video
–
Total Function Problems in the Polynomial Hierarchy

Christos Papadimitriou (Columbia University)
Video
–
On the Usefulness of the Strong Exponential Time Hypothesis

Ryan Williams (MIT)
Video
–
Progress in Symbolic Satisfiability Solving

Moshe Vardi (Rice University)
Video
–
On Symmetry and Quantification: A New Approach to Verify Distributed Protocols

Karem Sakallah (University of Michigan)
Video
–
The Dawn of Computational Complexity Theory

Dick Karp (UC Berkeley)
Video
–
Are we aging well?

Avi Wigderson (Institute for Advanced Study)
Video
–
Belief and Survey Propagation

Amin Coja-Oghlan (Goethe University)
Video
–
Information Efficiency of Proof Systems

Jan Krajicek (Charles University in Prague)
Video
–
Proofs and Circuits: Connections via Interpolation and Lifting

Susanna de Rezende (Czech Academy of Sciences)
Video
–
Short Proofs in Strong Proof Systems

Marijn Heule (Carnegie Mellon University)
Video
–
SAT for Optimization

Fahiem Bacchus (University of Toronto)
Video
–
Branching on Formulas: A Perspective From Knowledge Compilation

Adnan Darwiche (UCLA)
Video
–
Classifying the Complexity of SAT and CSP: Are we there yet?

Andrei Krokhin (Durham University)
Video
–
Complexity and Diversity

Les Valiant (Harvard University)
Video
–
Where The Really Hard Problems Really Are?

Lenka Zdeborova (EPFL)
Video
–
Strict NP: Expressive Power, Structure, and Complexity

Phokion Kolaitis (UC Santa Cruz  & IBM Research)
Video
–
Constraint Satisfaction and Expansion

Irit Dinur (Weizmann Institute)
Video
–
Symmetric Properties and Boolean Complexity

Alasdair Urquhart (University of Toronto)
Video
–
Cooperative Competition: A New Way of Solving SAT and other NP-Hard Problems in AI and Beyond

Holger Hoos (Leiden University & University of British Columbia)
Video
–
A Personal History of Practical SAT Solving

Armin Biere (Johannes Kepler University)
Video
–
On Time, and Space, and Width, and Depth

Sasha Razborov (University of Chicago)
Video