Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter

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


Duration: 48:44
233 views
1

Fabrizio Grandoni, IDSIA, University of Lugano
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/fabrizo-grandoni-2015-12-02



Other Videos By Simons Institute for the Theory of Computing


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-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-08Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
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
2015-12-08Subquadratic Algorithms for Succinct Stable Matching
2015-12-08Orthogonal Vectors is Hard for First-Order Properties on Sparse Graphs
2015-12-08ETH Hardness for Densest-k-Subgraph with Perfect Completeness
2015-12-08From the Inside: Fine-Grained Complexity and Algorithm Design
2015-12-08From the Inside: Economics and Computation


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