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

Cites work

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

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)