Playlist: 20 videos

Fine-Grained Complexity and Algorithm Design Boot Camp

Aug. 31 – Sept. 4, 2015

The Boot Camp is intended to acquaint program participants with the key themes of the program. Each speaker will give a mini-course on the topics below.

Thore Husfeldt (IT University of Copenhagen): "Exponential-Time...

1:7:25

Satisfiability Algorithms I

Mohan Paturi, UC San Diego
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/mohan-paturi-1-2015-08-31
Visit talk page
0:55:47

Satisfiability Algorithms II

Mohan Paturi, UC San Diego
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/mohan-paturi-2-2015-08-31
Visit talk page
0:54:48

Sparsification Lemma and ETH

Mohan Paturi, UC San Diego
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/mohan-paturi-3-2015-08-31
Visit talk page
0:57:36

Exponential-Time Algorithms

Thore Husfeldt, IT University of Copenhagen
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/thore-husfeldt-2015-08-31
Visit talk page
1:7:17

Computational Complexity of Polynomial Time Problems: Introduction

Virginia Vassilevska Williams, Stanford University
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/virginia-williams-2015-09-01
Visit talk page
1:7:39

Boolean Hardness to Randomization

Russell Impagliazzo, UC San Diego
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/russell-impagliazzo-2015-09-01
Visit talk page
1:8:52

Circuit Analysis Algorithms

Ryan Williams, Stanford University
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/ryan-williams-2015-09-01
Visit talk page
1:2:38

Recent Advances in FPT and Exact Algorithms for NP-Complete Problems

Dániel Marx, Hungarian Academy of Sciences
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/daniel-marx-2015-09-01
Visit talk page
0:59:4

Hardness for Graph Problems - Reductions Based on APSP and SETH

Virginia Vassilevska Williams, Stanford University
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/virginia-williams-2015-09-02
Visit talk page
1:1:35

Derandomization to Boolean Circuit Lower Bounds

Russell Impagliazzo, UC San Diego
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/russell-impagliazzo-2015-09-02
Visit talk page