Lower Bounds on the Running Time for Scheduling and Packing Problems

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=vZx6cCU-EBw


Duration: 25:51
387 views
1

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



Other Videos By Simons Institute for the Theory of Computing


2015-11-10The Square Root Phenomenon in Planar Graphs -- Survey and New Results
2015-11-10Parameterized and Promised Streaming
2015-11-10Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reduc
2015-11-10Fine-Grained Complexity of Exact Algorithms
2015-11-10More Needles in the Hay Might Make it Harder to Find One?
2015-11-10Fine-Grained Counting Complexity I
2015-11-10New Unconditional Lower Bounds for Algorithms and Enumeration Problems
2015-11-10Dense Subset Sum May Be the Hardest
2015-11-10Parameterized Inapproximability of Max k-Subset Intersection under ETH
2015-11-10Lower Bound Results for Hard Problems Related to Finite Automata
2015-11-10Lower Bounds on the Running Time for Scheduling and Packing Problems
2015-11-10Color Coding-Related Techniques
2015-11-10Fine-Grained Counting Complexity II
2015-11-10Subexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds
2015-11-10Lower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
2015-11-10Lossy Kernelization
2015-11-10Constructive Algorithm for Matroid Pathwidth
2015-11-10Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse
2015-11-10Engineering Motif Search for Large Graphs
2015-11-10Lower Bounds on the Space Complexity of Dynamic Programming
2015-11-10An Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space


Tags:
Simons Institute
UC Berkeley
computer science
theory of computing
Fine-Grained Complexity and Algorithm Design
Klaus Jansen