Playlist: 30 videos

Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms

Nov. 2 – Nov. 6, 2015

During the last decade, it has been recognized that the complexity assumption known as the (Strong) Exponential Time Hypothesis on satisfiability can explain the complexity of a large number of computational problems in a...

0:25:51

Lower Bounds on the Running Time for Scheduling and Packing Problems

Klaus Jansen, University of Kiel
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/klaus-jansen-2015-11-03
Visit talk page
0:27:6

On the Subexponential Time Complexity of the CSP

Iyad Kanj, DePaul University
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/tbd
Visit talk page
1:0:50

Exact Algorithms from FPT Algorithms

Daniel Lokshtanov, University of Bergen
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/daniel-lokshtanov-2015-11-05
Visit talk page
0:29:25

Spotting Trees with Few Leaves

Łukasz Kowalik, University of Warsaw
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/lukasz-kowalik-2015-11-04
Visit talk page
1:2:6

Fine-Grained Counting Complexity II

Radu-Cristian Curticapean, Universität des Saarlandes
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/radu-cristian-curticapean-2015-11-04
Visit talk page
0:29:28

Subexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds

Marcin Pilipczuk, University of Warsaw
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/marcin-pilipczuk-2015-11-04
Visit talk page
0:33:6

Lower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems

Michał Pilipczuk, University of Warsaw
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/michal-pilipczuk-2015-11-04
Visit talk page
1:4:22

Lossy Kernelization

Saket Saurabh, IMSc + UIB
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/saket-saurabh-2015-11-04
Visit talk page
0:28:52

Color Coding-Related Techniques

Meirav Zehavi, Tel Aviv University
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/meirav-zehavi-2015-11-05
Visit talk page
0:38:28

Lower Bounds on the Space Complexity of Dynamic Programming

Peter Rossmanith, RWTH Aachen
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/peter-rossmanith-2015-11-05
Visit talk page