Ryan Williams Unveils Backdoors to Typical Case Complexity 🔍
Discover how Ryan Williams explores innovative approaches to understanding and solving problems related to typical case complexity in computational theory, presented at the Beyond Worst Case Analysis Workshop.
Stanford Computer Science Theory
698 views • Oct 16, 2011
About this video
Videos from the Beyond Worst Case Analysis Workshop
Stanford, CA
Sept 19-21, 2011
Ryan Williams: Backdoors to Typical Case Complexity
In areas such as planning and finite model-checking, current solution techniques can solve combinatorial problems with millions of variables and constraints. The good scaling behavior of these methods appears to defy what one would expect based on worst-case complexity. This talk will survey a framework for understanding the tractability of real-world problem instances, developed in collaboration with Gomes and Selman. The central concept is that of a "backdoor" to an instance: a small variable subset "sufficient" for solving that instance. Informally, a backdoor measures the "distance" of a problem instance from a polynomial-time solvable subset of instances. Empirical results have shown that many real-world problems possess small backdoors (with respect to polynomial-time heuristics built into the solvers), and much theoretical work on parametrized and exact algorithms can be reinterpreted in the language of backdoors.
Stanford, CA
Sept 19-21, 2011
Ryan Williams: Backdoors to Typical Case Complexity
In areas such as planning and finite model-checking, current solution techniques can solve combinatorial problems with millions of variables and constraints. The good scaling behavior of these methods appears to defy what one would expect based on worst-case complexity. This talk will survey a framework for understanding the tractability of real-world problem instances, developed in collaboration with Gomes and Selman. The central concept is that of a "backdoor" to an instance: a small variable subset "sufficient" for solving that instance. Informally, a backdoor measures the "distance" of a problem instance from a polynomial-time solvable subset of instances. Empirical results have shown that many real-world problems possess small backdoors (with respect to polynomial-time heuristics built into the solvers), and much theoretical work on parametrized and exact algorithms can be reinterpreted in the language of backdoors.
Video Information
Views
698
Likes
6
Duration
29:29
Published
Oct 16, 2011