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...

0:57:46

Circuit Complexity and Connections I

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

Parameterized Reductions

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

The Easy Witness Lemma

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

Circuit Complexity and Connections II

Ryan Williams, Stanford University
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/ryan-williams-2015-09-03
Visit talk page
0:55:24

Hardness for Sequence Problems - LCS and Frechet Distance

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

Consequences of ETH: Tight Bounds for Various 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-03
Visit talk page
1:10:7

Proof of NEXP Not in ACC

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

Hardness for Dynamic Problems; Conclusion and Future Research

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

Connections Between Hardness and Randomness in the Algebraic Setting

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

Consequences of SETH: Tight Bounds for Some More 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-04
Visit talk page