Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Necklaces, convolutions, and \(X+Y\)
On minimum witnesses for Boolean matrix multiplication
The complexity of computing the permanent
All-pairs bottleneck paths in vertex weighted graphs
Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
On the all-pairs-shortest-path problem in unweighted undirected graphs.
Computing dominances in \(E^ n\)
On the exponent of all pairs shortest path problem
Subcubic cost algorithms for the all pairs shortest path problem
Linear-space data structures for range mode query in arrays
Faster algorithms for finding lowest common ancestors in directed acyclic graphs
All pairs lightest shortest paths
Finding, Minimizing, and Counting Weighted Subgraphs
Towards polynomial lower bounds for dynamic problems
Finding heaviest H -subgraphs in real weighted graphs, with applications
Nondecreasing paths in a weighted graph or
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Clustered Integer 3SUM via Additive Combinatorics
More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
All pairs shortest paths using bridging sets and rectangular matrix multiplication
Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
Generalized String Matching
New Bounds on the Complexity of the Shortest Path Problem
Faster All-Pairs Shortest Paths via Circuit Complexity
Threesomes, Degenerates, and Love Triangles
Better Approximations for Tree Sparsity in Nearly-Linear Time
Subcubic Equivalences Between Path, Matrix, and Triangle Problems
On Problems Equivalent to (min,+)-Convolution
Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
More Logarithmic-factor Speedups for 3SUM, (median,+)-convolution, and Some Geometric 3SUM-hard Problems
Homomorphisms are a good basis for counting small subgraphs
Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Fine-Grained Reductions from Approximate Counting to Decision
Hamming Distance Completeness
Faster Algorithms for All Pairs Non-Decreasing Paths Problem
On Multidimensional and Monotone k-SUM
ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
Approximately counting and sampling small witnesses using a colourful decision oracle
On Hardness of Jumbled Indexing
Finding, minimizing, and counting weighted subgraphs
Fine-grained complexity for sparse graphs
Finding Four-Node Subgraphs in Triangle Time
Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
Automata, Languages and Programming
Quantum algorithms for computational geometry problems

This page was built for publication: Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more