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:31:2

Constructive Algorithm for Matroid Pathwidth

Eunjung Kim, CNRS/Paris Dauphine University
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/eunjung-kim-2015-11-05
Visit talk page
0:30:31

Engineering Motif Search for Large Graphs

Petteri Kaski, Aalto University
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/petteri-kaski-2015-11-05
Visit talk page
0:33:14

Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse

Michael Lampis, Université Paris Dauphine
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/michael-lampis-2015-11-05
Visit talk page
1:6:23

The Square Root Phenomenon in Planar Graphs -- Survey and New Results

Dániel Marx, Hungarian Academy of Sciences
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/daniel-marx-2015-11-06
Visit talk page
0:29:5

Improved Deterministic Algorithms for Sparse Max-SAT

Rahul Santhanam, University of Edinburgh
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/rahul-santhanam-2015-11-06
Visit talk page
0:22:53

Towards General and Tight Hardness Results for Graph Problems

Christian Komusiewicz, Technische Universität Berlin
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/christian-komusiewicz-2015-11-03
Visit talk page
0:29:8

An Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space

Yijia Chen, Fudan University
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks-yijia-chen-2015-11-06
Visit talk page
0:25:26

Lower Bounds for Problems Parameterized by Clique-width

Petr Golovach, University of Bergen
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/petr-golovach-2015-11-06
Visit talk page
0:30:37

Faster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC^0[p]

Suguru Tamaki, Kyoto University
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/suguru-tamaki-2015-11-06
Visit talk page
0:17:28

From Channel Assignment to Subgraph Isomorphism

Arkadiusz Socała, University of Warsaw
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/channel-assignment-subgraph-isomorphism
Visit talk page