Graph algorithms · all-pairs shortest paths · min-plus product · fine-grained complexity

Truly Subcubic Exact APSP Conjecture

Collaboration beta

Sampling, exact carry bookkeeping, and compact target cloning narrow the problem, but the algorithm still needs sparse-target replacements for dense uniformization and low-doubling stages.

APSP (n) = O (n^{3 - δ} polylog n) for some δ > 0

Known results and sources

Exact APSP is reduced to structured sparse-target questions, but the truly subcubic conclusion remains conditional.

Research problem

Exact mathematical statement

For an n-vertex directed graph with O(log n)-bit integer edge weights and no negative cycle, compute every exact shortest-path distance in randomized or deterministic word-RAM time

O\left(n^{3-\delta}\operatorname{polylog} n\right)

for some fixed constant $\delta>0$ . Equivalently up to polylogarithmic factors, compute exact square min-plus product in the same time. The source explicitly reports no unconditional completion; path reconstruction and negative-cycle propagation are outside this distance-only target.

Problem infographic

Problem at a glance

Four-stage source-bound explainer: sampled min-plus candidates, exact dyadic carry families, compact sparse target cloning, and two unresolved sparse-target interfaces. — The source reports exact reductions through compact sparse targets; uniformization and target-only low-doubling remain open.

Current mathematical picture

Where work on Truly Subcubic Exact APSP Conjecture stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureFixed-precision bilinear power-grid evaluation and a few global scalings

Invalid tensor-support coordinates can force arbitrarily deep valuation cancellation, while explicit metric families require n^(1-o(1)) independently evaluated global scaling charts. Input-adaptive or symbolic arithmetic, a prefix-specific target detector, and the structured sparse-target equality route remain open within the source's stated boundaries.

Route status · Narrowed route

Main reductionCurrent reduction

Reduce exact min-plus product to sampled strict prefixes, convert each strict comparison into sparse low-rank equality families with exact dyadic carry handling, and recover all candidate labels by compact target-cloned binary splitting.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeReplace the remaining dense low-rank-to-slice, heavy/light, uniformization, and later rank-reduction scans by sparse-target operations without losing equivalence.Task status · Ready to work on

Work mapped so far

Truly Subcubic Exact APSP Conjecture in numbers

810retained lines of mathematical investigation810 in the current working snapshot

Argument development: 575 · 71%
Explored or eliminated routes: 26 · 3%
Computational analysis: 112 · 14%
Open obligations: 52 · 6%
Definitions and setup: 45 · 6%

9selected mapped statements1routes investigated3open questions3contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Status checkedAug 30, 2026

Source recordedAug 30, 2026

Recommended next task

Replace the remaining dense low-rank-to-slice, heavy/light, uniformization, and later rank-reduction scans by sparse-target operations without losing equivalence.

Suggested move: Audit the first post-regularization source stage operation by operation and prove a target-linear replacement or construct a compact-clone counterexample.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

13 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

1 recorded

Narrowed routeFixed-precision bilinear power-grid evaluation and a few global scalings

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Replace the remaining dense low-rank-to-slice, heavy/light, uniformization, and later rank-reduction scans by sparse-target operations without losing equivalence.Suggested move: Audit the first post-regularization source stage operation by operation and prove a target-linear replacement or construct a compact-clone counterexample.

Ready to work on

Preserve compact base potentials, clone maps, incidence bounds, exceptions, and original-dimension caps through every later transform.Suggested move: Represent every rounded, shifted, sliced, popular-sum, and masked target by base certificate, family transform, and sparse clone list with target-linear traversal.

Ready to work on

Solve the uniform low-doubling instances with shared algebraic work while returning only requested target entries and adding no polynomial batching factor.Suggested move: After the sparse front end closes, prove a target-only low-doubling solver or isolate a promise-respecting obstruction for the carry-and-cloning instances.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 30, 2026

Current statusOpen conjecture

The unrestricted exact weighted APSP algorithmic question remains open in this scoped collection. A 2023 paper states that no truly subcubic exact algorithm is known and calls the opposing hardness prediction the APSP conjecture; a 2025 paper obtains truly subcubic time only under a restriction on the number of distinct weights per node. Neither source proves a general lower bound or supplies the unrestricted algorithm pursued by this workspace.

[2][3]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2025
PreprintAbboud, Fischer, Jin, Vassilevska Williams, and Xi gave truly subcubic algorithms when each node has sufficiently few distinct outgoing-edge weights, while identifying the unrestricted case as the classical…[3]
2023
PreprintSaha and Ye obtained faster approximation algorithms while explicitly distinguishing them from the still-unknown truly subcubic exact weighted APSP algorithm.[2]
2018
Peer reviewedVassilevska Williams and Williams established subcubic equivalences among exact weighted APSP, min-plus product verification, negative-triangle detection, and several other graph and matrix problems; these…[1]

Mathematical neighborhood

Related results and reusable starting points

Current focusTruly Subcubic Exact APSP Conjecture

Equivalent formulationtruly subcubic min-plus product and negative-triangle detection

Under subcubic reductions and polylogarithmic weight dependence, exact weighted APSP is equivalent to central min-plus and negative-triangle problems.

[1]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetNo source in this scoped collection supplied a checked formal statement that fixes the current work's exact word-RAM, bit-length, randomization, and output conventions together.
Formalization targetNo checked proof or certificate resolves existence or nonexistence of a truly subcubic algorithm for unrestricted exact weighted APSP.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

6 standing statements3 proposed statements3 open questions1 narrowed routes

Statements by mathematical role9 selected mapped statements

theorem candidate1 of 91
reduction3 of 93
lemma3 of 93
special case1 of 91
negative result1 of 91

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.22 displayed rows · 1 route included

retained route statementCan exact weighted APSP achieve a fixed polynomial saving over cubic time?
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementSampled-prefix normal formintermediate
retained route statementCompact cloning and family volumeintermediate
retained route statementSparse regular-rank splitintermediate
retained route statementConditional truly subcubic exponentintermediate
retained route statementBounded-spread min-plus productintermediate
retained route statementScoped arithmetic barriersintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureFixed-precision bilinear power-grid evaluation and a few global scalingsreported failure
Research targetReplace the remaining dense low-rank-to-slice, heavy/light, uniformization, and later rank-reduction scans by sparse-target operations without losing equivalence.open
Research targetPreserve compact base potentials, clone maps, incidence bounds, exceptions, and original-dimension caps through every later transform.open
Research targetSolve the uniform low-doubling instances with shared algebraic work while returning only requested target entries and adding no polynomial batching factor.open
Narrowed routeFixed-precision bilinear power-grid evaluation and a few global scalingsInvalid tensor-support coordinates can force arbitrarily deep valuation cancellation, while explicit metric families require n^(1-o(1)) independently evaluated global scaling charts. Input-adaptive or symbolic arithmetic, a prefix-specific target detector, and the structured sparse-target equality route remain open within the source's stated boundaries.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeReplace the remaining dense low-rank-to-slice, heavy/light, uniformization, and later rank-reduction scans by sparse-target operations without losing equivalence.

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointReplace the remaining dense low-rank-to-slice, heavy/light, uniformization, and later rank-reduction scans by sparse-target operations without losing equivalence.

Truly Subcubic Exact APSP Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Sampling, exact carry bookkeeping, and compact target cloning narrow the problem, but the algorithm still needs sparse-target replacements for dense uniformization and low-doubling stages.

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references3 cited works · next context review by Nov 30, 2026

The mathematical context was checked on Aug 30, 2026. Status can be refreshed sooner after a material result or claim.

1
Subcubic Equivalences Between Path, Matrix, and Triangle Problemspeer reviewed result · Virginia Vassilevska Williams, Ryan Williams · Journal of the ACM · 2018 · DOI 10.1145/3186893 · accessed Aug 30, 2026
2
Faster Approximate All Pairs Shortest Pathspreprint · Barna Saha, Christopher Ye · arXiv · 2023 · ARXIV 2309.13225 · accessed Aug 30, 2026
3
All-Pairs Shortest Paths with Few Weights per Nodepreprint · Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi · arXiv · 2025 · ARXIV 2506.20017 · accessed Aug 30, 2026

Important qualifications

The current work pursues existence of a truly subcubic exact algorithm, while the literature commonly calls the opposing hardness hypothesis the APSP conjecture; this record keeps those logical directions separate.
The scoped search emphasized exact weighted APSP, min-plus equivalences, and recent structured-input algorithms; it did not attempt a complete survey of approximate, unweighted, sparse, or dynamic variants.
No dedicated formalization, independently reproduced computation, certificate, or general-APSP implementation was verified in this collection; empty readiness lists do not establish nonexistence.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces