Higher Lower Bounds from the 3SUM Conjecture

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


Duration: 47:41
807 views
6

Seth Pettie, University of Michigan
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/seth-pettie-2015-11-30



Other Videos By Simons Institute for the Theory of Computing


2015-12-10Human Computation
2015-12-10Perfect Matchings
2015-12-10Quantum NP and Beyond
2015-12-10Some Current Computational Challenges in Bioinformatics
2015-12-10Some New Results on Random Points in the Unit Square
2015-12-10A Personal History (With Karp Reductions!)
2015-12-10Orthogonal Remarks
2015-12-10The Computational Benefit of Correlated Instances
2015-12-09Why Only Us: Language and Evolution
2015-12-09The Power of Hashing
2015-12-08Higher Lower Bounds from the 3SUM Conjecture
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-08Fast Combinatorial 3SUM breaks BMM
2015-12-08Conditional Lower Bounds for Longest Common Subsequence
2015-12-08Which Regular Expression Patterns are Hard to Match?
2015-12-08Optimal Data-Dependent Hashing for Nearest Neighbor Search
2015-12-08Simulating Branching Programs with Edit Distance and Friends
2015-12-08Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter


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