Conditional Lower Bounds for Longest Common Subsequence

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


Duration: 41:05
318 views
0

Karl Bringmann, ETH Zürich
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/conditional-lower-bounds-longest-common-subsequence



Other Videos By Simons Institute for the Theory of Computing


2015-12-10The Computational Benefit of Correlated Instances
2015-12-09Why Only Us: Language and Evolution
2015-12-09The Power of Hashing
2015-12-08Clustered Integer 3SUM via Additive Combinatorics
2015-12-08Higher Lower Bounds from the 3SUM Conjecture
2015-12-083SUM Hardness of Triangle Enumeration Problems, and their Consequences
2015-12-08Playing with Grammars: What Have We Known So Far!
2015-12-08The New P
2015-12-08Lower Bounds and Open Problems in Streams
2015-12-083SUM, 3XOR, Triangles
2015-12-08Conditional Lower Bounds for Longest Common Subsequence
2015-12-08Simulating Branching Programs with Edit Distance and Friends
2015-12-08Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
2015-12-08Upper and Lower Bounds for Graph Problems in Computer Aided Verification
2015-12-08Deterministic APSP, Orthogonal Vectors, and More
2015-12-08Some Emergency Barriers to Worst-Case Dynamic MST
2015-12-08Input Sparsity and Hardness for Linear Algebra Problems
2015-12-08Deterministic Edge Connectivity in Near-Linear Time
2015-12-08Finding k Simple Shortest Paths and Cycles
2015-12-08Light Spanners
2015-12-08Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs


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