Computational Complexity of Low-Polynomial Time Problems

# click the upper-left icon to select videos from the playlist

source: Simons Institute    2015年12月8日
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/set...
Nov. 30 – Dec. 3, 2015
Despite the widely demonstrated usefulness of the notion of NP-hardness, there are many situations in which it is not applicable. This is the case, for example, when the goal is to show hardness of problems that are known to have polynomial time solutions. For instance, in the context of massive data computation even a quadratic-time algorithm is considered inefficient, but for many interesting problems no sub-quadratic algorithms are known. It would be of great interest to give complexity-theoretic evidence that no such algorithms exist at all. Mimicking NP-hardness, one would want to say that a problem is hard because if it had a sub-quadratic time algorithm, then many other important problems would have such algorithms as well.
To this end, one needs more refined notions of reducibility between problems that preserve a designated running time. Such reductions (for sub-quadratic, sub-cubic and near-linear runtimes) have been found in a number of isolated contexts: between problems in computational geometry, combinatorial pattern matching and problems related to shortest paths in graphs. However, the overarching framework is still mostly missing. The purpose of the workshop is to bring together researchers interested in these questions, in order to share their insights and develop a future research agenda. One of the outcomes of the workshop will be a list of key open problems in the field.
For more information, please visit https://simons.berkeley.edu/workshops/complexity2015-3.
These presentations were supported in part by an award from the Simons Foundation.

Higher Lower Bounds from the 3SUM Conjecture Seth Pettie, University of Michigan 47:41
3SUM Hardness of Triangle Enumeration Problems, and their Consequences 38:07
Clustered Integer 3SUM via Additive Combinatorics 39:58
3SUM, 3XOR, Triangles 43:06
The New P 21:19
Playing with Grammars: What Have We Known So Far! 43:51
Lower Bounds and Open Problems in Streams 39:38
Optimal Data-Dependent Hashing for Nearest Neighbor Search 49:09
Conditional Lower Bounds for Longest Common Subsequence 41:04
Fast Combinatorial 3SUM breaks BMM 39:44
Which Regular Expression Patterns are Hard to Match? 23:27
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter 48:43
Upper and Lower Bounds for Graph Problems in Computer Aided Verification 49:32
Simulating Branching Programs with Edit Distance and Friends 45:24
Deterministic APSP, Orthogonal Vectors, and More 47:14
Some Emergency Barriers to Worst-Case Dynamic MST 44:50
Deterministic Edge Connectivity in Near-Linear Time 49:43
Finding k Simple Shortest Paths and Cycles 50:56
Light Spanners 39:29
Input Sparsity and Hardness for Linear Algebra Problems 43:18
ETH Hardness for Densest-k-Subgraph with Perfect Completeness 18:17
Subquadratic Algorithms for Succinct Stable Matching 20:42
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs 26:50
Orthogonal Vectors is Hard for First-Order Properties on Sparse Graphs 22:43