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

Cites Work

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
The complexity of computing the permanent
Linear-space data structures for range mode query in arrays
Towards polynomial lower bounds for dynamic problems
All pairs shortest paths using bridging sets and rectangular matrix multiplication
Title not available (Why is that?)
Threesomes, degenerates, and love triangles
Finding, minimizing, and counting weighted subgraphs
On the all-pairs-shortest-path problem in unweighted undirected graphs.
Computing dominances in \(E^ n\)
Clustered Integer 3SUM via Additive Combinatorics
Generalized String Matching
On hardness of jumbled indexing
Title not available (Why is that?)
Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
New Bounds on the Complexity of the Shortest Path Problem
On the exponent of all pairs shortest path problem
Faster algorithms for finding lowest common ancestors in directed acyclic graphs
More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
Subcubic cost algorithms for the all pairs shortest path problem
Subcubic equivalences between path, matrix, and triangle problems
Finding heaviest \(H\)-subgraphs in real weighted graphs, with applications
Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
Necklaces, convolutions, and \(X+Y\)
On minimum witnesses for Boolean matrix multiplication
Automata, Languages and Programming
Fast algorithms for \((\max, \min)\)-matrix multiplication and bottleneck shortest paths
All pairs lightest shortest paths
All-pairs bottleneck paths in vertex weighted graphs
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Tight hardness for shortest cycles and paths in sparse graphs
Homomorphisms are a good basis for counting small subgraphs
Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
Approximately counting and sampling small witnesses using a colourful decision oracle
Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
Finding four-node subgraphs in triangle time
Finding, minimizing, and counting weighted subgraphs
Hamming Distance Completeness
Title not available (Why is that?)
Regularity lemmas and combinatorial algorithms
Better approximations for tree sparsity in nearly-linear time
On Multidimensional and Monotone k-SUM
Faster all-pairs shortest paths via circuit complexity
On problems equivalent to \((\min,+)\)-convolution
Title not available (Why is that?)
Title not available (Why is that?)
Quantum algorithms for computational geometry problems
More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
On some fine-grained questions in algorithms and complexity
Fine-grained complexity for sparse graphs
Towards unified approximate pattern matching for Hamming and \(L_1\) distance
Nondecreasing paths in a weighted graph or: how to optimally read a train schedule
Faster Algorithms for All Pairs Non-Decreasing Paths Problem
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
Fine-Grained Reductions from Approximate Counting to Decision

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499239)