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

0:57:1

Fine-Grained Complexity of Exact Algorithms

Fedor Fomin, University of Bergen
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/fedor-fomin-2015-11-02
Visit talk page
0:24:28

More Needles in the Hay Might Make it Harder to Find One?

Andreas Björklund, Lund University
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/andreas-bjorklund-2015-11-02
Visit talk page
0:37:13

Parameterized and Promised Streaming

MohammadTaghi Hajiaghayi, University of Maryland
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/mohamma-taghi-hajiaghayi-2015-11-02
Visit talk page
0:59:21

Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility

Stefan Schneider, UC San Diego
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/tbd-1
Visit talk page
0:30:5

Lower Bound Results for Hard Problems Related to Finite Automata

Henning Fernau, University of Trier
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/henning-fernau-2015-11-02
Visit talk page
0:31:14

New Unconditional Lower Bounds for Algorithms and Enumeration Problems

Serge Gaspers, University of New South Wales
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/serge-gaspers-2015-11-02
Visit talk page
1:2:4

Fine-Grained Counting Complexity I

Holger Dell, Universität des Saarlandes
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/holger-dell-2015-11-03
Visit talk page
0:32:34

Dense Subset Sum May Be the Hardest

Jesper Nederlof, Eindhoven University of Technology
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/jesper-nederlof-2015-11-3
Visit talk page
0:29:47

Parameterized Inapproximability of Max k-Subset Intersection under ETH

Bingkai Lin, University of Tokyo
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/bingkai-lin-2015-11-03
Visit talk page
0:58:20

Lower Bound Issues in Computational Social Choice

Rolf Niedermeier, TU Berlin
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/tbd-0
Visit talk page