[#P3144] Is there a truly subcubic algorithm for weighted APSP?

Problem. Does there exist \(\varepsilon>0\) and an \(O(n^{3-\varepsilon})\)-time algorithm for all-pairs shortest paths in directed \(n\)-vertex graphs with integer edge weights of polynomial magnitude and no negative cycle?

All-pairs shortest paths filling a distance matrix. — A structural graph diagram of the statement's mathematical objects.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Context

Known frontier: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Open boundary: A fixed positive exponent saving remains unknown.

2Problem setup

Definition 1 (APSP). Compute the shortest-path distance for every ordered pair of vertices.

Definition 2 (truly subcubic). O(n^{3−ε}) for one fixed ε>0.

Remark 1. The standard dynamic-programming and min-plus product approaches are cubic up to lower-order improvements. The target fixes polynomially bounded weights so bit complexity is explicit.

3What counts as a solution

Give a correct truly subcubic algorithm in the stated word-RAM or bit model.
Or prove an n^{3−o(1)} lower bound in a clearly specified standard model.

1Status

Saved packet · August 1, 2026

What counts as a solution

Saved packet status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Exact unresolved remainder: A fixed positive exponent saving remains unknown.^[1][2]

1Packet records

Show recorded summaries

Record	Kind	Assessment
OPEN as checked on 2026-08-01. Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Exact unresolved remainder: A fixed positive exponent saving remains unknown.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 OPEN as checked on 2026-08-01. Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Exact unresolved remainder: A fixed positive exponent saving remains unknown.^[1][2] Relevance to this problem This is the dated publication status for the canonical target Is there a truly subcubic algorithm for weighted APSP?. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The problem was checked as open on 2026-08-01. The strongest neighboring result found in the cited sources is: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. The exact unresolved remainder is: A fixed positive exponent saving remains unknown. A complete resolution must meet the following acceptance conditions: - Give a correct truly subcubic algorithm in the stated word-RAM or bit model. - Or prove an n^{3−o(1)} lower bound in a clearly specified standard model. Open full record →
The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 2 The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP.^[1][2] Relevance to this problem Locates the present research frontier immediately below Is there a truly subcubic algorithm for weighted APSP?. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. This leaves the following boundary unresolved: A fixed positive exponent saving remains unknown. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Unresolved remainder: A fixed positive exponent saving remains unknown.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Unresolved remainder: A fixed positive exponent saving remains unknown.^[1][2] Relevance to this problem Documents why Is there a truly subcubic algorithm for weighted APSP? was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened The audit ran on 2026-08-01 across the cited primary literature and problem collections, Crossref, arXiv, and stable publisher records, TheoremDB published, prospecting, packet, formal, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - truly subcubic APSP open problem 2026 - weighted all pairs shortest paths n 3 epsilon The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Unresolved remainder: A fixed positive exponent saving remains unknown. Related: Claim 1 Open full record →
A fixed positive exponent saving remains unknown.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 2 A fixed positive exponent saving remains unknown. Relevance to this problem Turns the remaining uncertainty in Is there a truly subcubic algorithm for weighted APSP? into a checkable research target. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: A fixed positive exponent saving remains unknown. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - Give a correct truly subcubic algorithm in the stated word-RAM or bit model. - Or prove an n^{3−o(1)} lower bound in a clearly specified standard model. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion material

Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Exact unresolved remainder: A fixed positive exponent saving remains unknown.

Equivalent-formulation queries: truly subcubic APSP open problem 2026; weighted all pairs shortest paths n 3 epsilon
Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP.
Exact unresolved remainder: A fixed positive exponent saving remains unknown.

How the 4 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemIs there a truly subcubic algorithm for weighted APSP?

All 3 recorded relations between these records and the problem

2See also

Multiplicative complexity of the six-bit threshold-at-least-three functiontheoretical computer science
Polynomial determinization of two-way finite automatatheoretical computer science
Logarithmic DFA separation of binary wordstheoretical computer science

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Is there a truly subcubic algorithm for weighted APSP?.” TheoremDB. P3144. Problem statement; statement text SHA-256 72e3202790f977af6cd1cfb988c3bddbc01c21f8dd745cab34fc1097c8a4e80d. https://theoremdb.org/statement/?ref=P3144

BibTeX

@misc{theoremdb-problem-72e3202790f977af6cd1cfb988c3bddbc01c21f8dd745cab34fc1097c8a4e80d,
  title = {{Is there a truly subcubic algorithm for weighted APSP?}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 72e3202790f977af6cd1cfb988c3bddbc01c21f8dd745cab34fc1097c8a4e80d},
  url = {https://theoremdb.org/statement/?ref=P3144}
}

Plain text: Built Markdown snapshot

This problem includes 4 records joined by 3 typed links, sourced from arxiv.org^[1], current as of August 1, 2026.

1Lean verification

1References

Packet source. R. Williams, Faster all-pairs shortest paths via circuit complexity, STOC 2014. main theorem. ↗preprint · primary source · arXiv:1312.6680, checked 2026-08-01 · checked 2026-08-01Source use: original summary.Gives a subcubic improvement by a subpolynomial factor and explains the circuit connection.Also cited at R. Williams, Faster all-pairs shortest paths via circuit complexity, STOC 2014. main theorem.Source used to assess the problem's recorded status.For Is there a truly subcubic algorithm for weighted APSP?: This is the dated publication status for the canonical target Is there a truly subcubic algorithm for weighted APSP?.Source named by the research packet.
Virginia Vassilevska Williams and Ryan Williams, “Subcubic Equivalences between Path, Matrix and Triangle Problems”. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (2010), 645-654. DOI 10.1109/FOCS.2010.67. subcubic equivalence theorems. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Shows that a breakthrough would transfer to several central weighted graph problems.Source used to assess the problem's recorded status.For Is there a truly subcubic algorithm for weighted APSP?: Shows that a breakthrough would transfer to several central weighted graph problems.

Original TheoremDB editorial statement and source synthesis; external works are used for citation only.

[#P3144] Is there a truly subcubic algorithm for weighted APSP?

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance