New Unconditional Lower Bounds for Algorithms and Enumeration Problems

Channel:

Subscribers:

68,700

Published on November 10, 2015 6:45:14 PM ● Video Link: https://www.youtube.com/watch?v=b49fUAeSaOc

Duration: 31:14

89 views

Serge Gaspers, University of New South Wales
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
https://simons.berkeley.edu/talks/serge-gaspers-2015-11-02

Other Videos By Simons Institute for the Theory of Computing

2015-11-20	Security Games: Key Algorithmic Principles, Deployed Applications and Research Challenges(*)
2015-11-20	Algorithmic Trading and Machine Learning
2015-11-20	Informational Substitutes and Complements for Prediction
2015-11-20	Incentive Auctions and Spectrum Repacking
2015-11-13	Research Challenges in Designing the US Incentive Auction
2015-11-10	The Square Root Phenomenon in Planar Graphs -- Survey and New Results
2015-11-10	Parameterized and Promised Streaming
2015-11-10	Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reduc
2015-11-10	Fine-Grained Complexity of Exact Algorithms
2015-11-10	More Needles in the Hay Might Make it Harder to Find One?
2015-11-10	New Unconditional Lower Bounds for Algorithms and Enumeration Problems
2015-11-10	Spotting Trees with Few Leaves
2015-11-10	Exact Algorithms from FPT Algorithms
2015-11-10	Lower Bound Issues in Computational Social Choice
2015-11-10	On the Subexponential Time Complexity of the CSP
2015-11-10	Lower Bounds on the Running Time for Scheduling and Packing Problems
2015-11-10	Color Coding-Related Techniques
2015-11-10	Fine-Grained Counting Complexity II
2015-11-10	Subexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds
2015-11-10	Lower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
2015-11-10	Lossy Kernelization

Tags:

Simons Institute

UC Berkeley

computer science

theory of computing

Fine-Grained Complexity and Algorithm Design

Serge Gaspers