Subcubic equivalences between path, matrix and triangle problems

DOI10.1109/FOCS.2010.67MaRDI QIDQ6990284zbMATH OpenFDO

Authors Virginia Vassilevska Williams, Ryan Williams

Publication date 29 April 2025

Full work available at URL https://doi.org/10.1109/FOCS.2010.67

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX) Information and communication theory, circuits (94-XX)

Cited in

(12)

• Conditionally optimal approximation algorithms for the girth of a directed graph
• Faster algorithms for dual-failure replacement paths
• It's hard to HAC average linkage!
• Approximating the geometric knapsack problem in near-linear time and dynamically
• Depth-3 circuit lower bounds for k-OV
• Polynomial formulations as a barrier for reduction-based hardness proofs
• Shortest beer path queries in digraphs with bounded treewidth
• When are cache-oblivious algorithms cache adaptive? A case study of matrix multiplication and sorting
• Elastic-degenerate string comparison
• Algorithms and hardness for multidimensional range updates and queries
• 3sum and related problems in fine-grained complexity (invited talk)
• (Multivariate) k-SUM as barrier to succinct computation

This page was built for publication: Subcubic equivalences between path, matrix and triangle problems

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