Lower Bounds on the Space Complexity of Dynamic Programming

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


Duration: 38:28
542 views
4

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



Other Videos By Simons Institute for the Theory of Computing


2015-11-10Spotting Trees with Few Leaves
2015-11-10Exact Algorithms from FPT Algorithms
2015-11-10Lower Bound Issues in Computational Social Choice
2015-11-10On the Subexponential Time Complexity of the CSP
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-10Lower Bounds on the Space Complexity of Dynamic Programming
2015-11-10An Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space
2015-11-10Improved Deterministic Algorithms for Sparse Max-SAT
2015-11-10Towards General and Tight Hardness Results for Graph Problems
2015-11-10Faster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC^0[p]
2015-11-10Lower Bounds for Problems Parameterized by Clique-width
2015-11-10From Channel Assignment to Subgraph Isomorphism
2015-10-19Computational Efficiency Requires Simple Taxation
2015-10-19The Sample Complexity of Revenue Maximization
2015-10-19Multi-dimensional Virtual Values and Second-degree Price Discrimination
2015-10-19Smoothness and Pricing: Near-Optimal Outcomes in Markets Large and Small


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