Input Sparsity and Hardness for Linear Algebra Problems

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


Duration: 43:18
447 views
3

David Woodruff, IBM Almaden
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/david-woodruff-2015-12-03



Other Videos By Simons Institute for the Theory of Computing


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
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-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
2015-11-20Bitcoin's Incentive Structure
2015-11-20Dynamic Pricing in Ride-Sharing Platforms
2015-11-20AGT and Machine Learning
2015-11-20Business Model Analysis


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