# click the upper-left icon to select videos from the playlist
source: Simons Institute 2015年11月10日
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 way, showing the optimality of known algorithms. This connection has transformed the field of parameterized complexity by refining the question of which problems are fixed-parameter tractable to a fine-grained optimality program that tries to determine the best possible running time for all problems. Recent results show that such an understanding is possible for a wide range of problems, but there are still no tight bounds in many cases. This indicates that further work is needed on understanding the complexity assumptions related to satisfiability, transferring these lower bounds to various specific problem domains, and obtaining matching algorithmic upper bounds. The goal of the workshop is to bring together researchers from satisfiability, classical computational complexity, parameterized complexity and algorithm design to present recent results in these areas and initiate a discussion on connections between the complexity of satisfiability and the fine-grained complexity of other problems, and their implications for algorithm design.
For more information, please visit https://simons.berkeley.edu/workshops/complexity2015-2.
These presentations were supported in part by an award from the Simons Foundation.
Fine-Grained Complexity of Exact Algorithms 57:01 Fedor Fomin, University of Bergen https://simons.berkeley.edu/talks/fed...
More Needles in the Hay Might Make it Harder to Find One? 24:28
Parameterized and Promised Streaming 37:13
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reduc 59:21
Lower Bound Results for Hard Problems Related to Finite Automata 30:05
New Unconditional Lower Bounds for Algorithms and Enumeration Problems 31:14
Fine-Grained Counting Complexity I 1:02:04
Dense Subset Sum May Be the Hardest 32:34
Parameterized Inapproximability of Max k-Subset Intersection under ETH 29:47
Lower Bound Issues in Computational Social Choice 58:20
Lower Bounds on the Running Time for Scheduling and Packing Problems 25:51
On the Subexponential Time Complexity of the CSP 27:06
Exact Algorithms from FPT Algorithms 1:00:50
Spotting Trees with Few Leaves 29:25
Fine-Grained Counting Complexity II 1:02:06
Subexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds 29:28
Lower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems 33:06
Lossy Kernelization 1:04:23
Color Coding-Related Techniques 28:52
Lower Bounds on the Space Complexity of Dynamic Programming 38:28
Constructive Algorithm for Matroid Pathwidth 31:02
Engineering Motif Search for Large Graphs 30:31
Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse 33:14
The Square Root Phenomenon in Planar Graphs -- Survey and New Results 1:06:23
Improved Deterministic Algorithms for Sparse Max-SAT 29:05
Towards General and Tight Hardness Results for Graph Problems 22:53
An Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space 29:08
Lower Bounds for Problems Parameterized by Clique-width 25:26
Faster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC^0[p] 30:37
From Channel Assignment to Subgraph Isomorphism 17:28
No comments:
Post a Comment