Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015)
2015-12-08
Berkeley, United States
| title | author | length |
|---|---|---|
| Higher Lower Bounds from the 3SUM Conjecture | Seth Pettie | 48m |
Shows a direct reduction that reduces 3SUM directly to set disjointness and to reporting set intersection using hashing, giving stronger lower bounds and a… | ||
| 3SUM Hardness of Triangle Enumeration Problems, and their Consequences | Tsvi Kopelovitz | 38m |
Proves a chain of reductions from 3SUM hardness to offline set intersection to triangle enumeration to vertex-triangle queries to induced subgraph and finally… | ||
| Clustered Integer 3SUM via Additive Combinatorics | Moshe Lewenstein | 40m |
Claims a preprocessing scheme that uses Balog-Szemerédi-Gowers structure to cover A0,B0,S0 in randomized O~(n^2) preprocessing and answer subset three-sum… | ||
| 3SUM, 3XOR, Triangles | Emanuele Viola | 43m |
Shows a two-way quantitative reduction: if 3SUM runs in n^{1+ε} then triangle listing on m-edge graphs runs in about m^{4/3 - Θ(ε)}, and conversely Patrascu’s… | ||
| The New P | amir Abboud | 21m |
Introduces a colored-triangle detection problem: given colored nodes and threshold delta, trivial O(n^3) search exists and constant-delta cases admit truly… | ||
| Playing with Grammars: What Have We Known So Far! | Barna Saha | 44m |
Simple randomized stack algorithm gives an O(D) approximation for Dyck edit distance by deleting mismatches (analysis maps to a gambler’s‑ruin walk); refining… | ||
| Lower Bounds and Open Problems in Streams | Raphaël Clifford | 40m |
Proves unconditional streaming lower bounds in the cell-probe model: online convolution requires Ω(Δ·log n / w) amortized cell probes per output (Δ = bits per… | ||
| Optimal Data-Dependent Hashing for Nearest Neighbor Search | Alex Andoni | 49m |
Claims a concrete improvement over LSH: using data-dependent hashing and a tree of partitions that alternates dense-cluster extraction and cap carving… | ||
| Conditional Lower Bounds for Longest Common Subsequence | Karl Bringmann | 41m |
Proves conditional lower bounds for Longest Common Subsequence under SETH-based reductions by reducing Orthogonal Vectors into fine-grained parameter settings… | ||
| Fast Combinatorial 3SUM breaks BMM | Kasper Green Larsen | 40m |
Claim: a combinatorial 3SUM algorithm running in N^{3/2 - ε} would yield a subcubic combinatorial Boolean matrix multiplication algorithm, so under the… | ||
| Which Regular Expression Patterns are Hard to Match? | Arturs Backurs | 23m |
Arturs Backurs, Massachusetts Institute of Technology
Computational Complexity of Low-Polynomial Time… | ||
| Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter | Fabrizio Grandoni | 49m |
Fabrizio Grandoni, IDSIA, University of Lugano
Computational Complexity of Low-Polynomial Time Problems
https://simons.berkeley.edu/talks/fabrizo-grandoni-2015… | ||
| Upper and Lower Bounds for Graph Problems in Computer Aided Verification | Monika Henzinger | 50m |
Defines graph and MDP objectives and proves fine-grained separations: disjunctive reachability on MDPs requires roughly K·M^(2−o(1)) time under triangle/OV… | ||
| Simulating Branching Programs with Edit Distance and Friends | amir Abboud | 45m |
Proves a concrete reduction from BP-SAT to LCS/edit distance: satisfiability of nondeterministic branching programs (width w, length T on n variables) maps to… | ||
| Deterministic APSP, Orthogonal Vectors, and More | Ryan Williams | 47m |
Claims deterministic subquadratic algorithms for Orthogonal Vectors when d = c log n (randomized version runs in n^{2−ε}; deterministic matches up to… | ||
| Some Emergency Barriers to Worst-Case Dynamic MST | Danupon Nanongkai | 45m |
Identifies an explicit barrier: to beat the 30-year-old O(sqrt n) worst-case update for dynamic MST one must first build an emergency cut size oracle whose… | ||
| Deterministic Edge Connectivity in Near-Linear Time | Mikkel Thorup | 50m |
Deterministic algorithm finds global edge connectivity and a min-cut cactus for simple graphs in near‑linear time (polylog overhead), by repeatedly certifying… | ||
| Finding k Simple Shortest Paths and Cycles | Vijaya Ramachandran | 51m |
Presents a new algorithmic framework using path extensions plus distance‑sensitivity tools to compute K simple shortest paths and cycles. Claims an all‑pairs… | ||
| Light Spanners | Shiri Chechik | 40m |
New construction claims lightness O(n^{1/k}) while keeping stretch about 2k (more precisely a (2+ε)·k-style bound in the paper) and number of edges ≈… | ||
| Input Sparsity and Hardness for Linear Algebra Problems | David P. Woodruff | 43m |
Proves approximate Frobenius low-rank can run in input-sparsity time by sketching: multiply A by a sparse count sketch (one nonzero per column), project rows… | ||
| ETH Hardness for Densest-k-Subgraph with Perfect Completeness | Aviad Rubinstein | 18m |
Claim: under ETH there is no quasi‑polynomial algorithm for Densest‑k‑Subgraph with perfect completeness; the reduction blows up to about 2^{√n} vertices and… | ||
| Subquadratic Algorithms for Succinct Stable Matching | Daniel Moeller | 21m |
Provides subquadratic algorithms and matching lower bounds for succinct preference models. Claims a subquadratic one-sided D-attribute finding algorithm when… | ||
| Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs | Josh Wang | 27m |
Gives matching conditional upper and lower bounds: diameter needs a 3/2-approx in truly subquadratic time under Orthogonal Vectors, radius hardness comes from… | ||
| Orthogonal Vectors is Hard for First-Order Properties on Sparse Graphs | Jiawei Gao | 23m |
Shows that sparse Orthogonal Vectors implies hardness for first-order model checking: if two disjoint sets on m edges admits subquadratic time then model… | ||
| nothing matches | ||