---
type: "post"
id: "lovett-and-karingula-post-a-simplified-proof-of-a20347"
slug: "lovett-and-karingula-post-a-simplified-proof-of-a20347"
title: "Lovett and Karingula post a simplified proof of the 3SUM and APSP improvements on ECCC"
description: "Sankeerth Rao Karingula and Shachar Lovett have published a simplified proof of polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP)."
retrieval_nugget: "Sankeerth Rao Karingula and Shachar Lovett have published a simplified proof of polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP). For builders, the result is not deployable software, but it offers a more inspectable account of a fine-grained complexity result and the assumptions behind it."
published_at: "2026-10-28"
updated_at: "2026-10-28"
record_date: "2026-10-28"
date_kind: "published_at"
topics: []
entities: ["Sankeerth Rao Karingula","Shachar Lovett","ECCC","3SUM","All-Pairs Shortest Paths"]
related_patterns: []
novelty_label: "new_fact"
what_changed: "Karingula and Lovett publish a simplified proof of the 3SUM and APSP improvements, using selected-entry matrix multiplication and weaker exponents."
prior_refs: ["memory:201b9ab8-92d4-8bf7-ab34-50daed2a59e1","memory:bc1459b4-c5e6-8524-a24f-d90b3d5fbef4"]
source_url: "https://eccc.weizmann.ac.il/report/2026/247"
source_urls: ["https://eccc.weizmann.ac.il/report/2026/247"]
schema_version: "newruntime-agent-readable-v0.2"
stable_id: "post:lovett-and-karingula-post-a-simplified-proof-of-a20347"
status: "published"
visuals: []
editor: {"role":"editor","name":"Andrey Reshetnikov","profile":"https://newruntime.com/owner-profile.md","profile_json":"https://newruntime.com/owner-profile.json","same_as":["https://www.linkedin.com/in/reshetnikov1/","https://t.me/lapetuse"]}
routes: {"html":"https://newruntime.com/posts/lovett-and-karingula-post-a-simplified-proof-of-a20347/","markdown":"https://newruntime.com/posts/lovett-and-karingula-post-a-simplified-proof-of-a20347.md","json":"https://newruntime.com/posts/lovett-and-karingula-post-a-simplified-proof-of-a20347.json"}
---

# Lovett and Karingula post a simplified proof of the 3SUM and APSP improvements on ECCC

## Retrieval answer

Sankeerth Rao Karingula and Shachar Lovett have published a simplified proof of polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP). For builders, the result is not deployable software, but it offers a more inspectable account of a fine-grained complexity result and the assumptions behind it.

## Summary
Sankeerth Rao Karingula and Shachar Lovett have published a simplified proof of polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP). For builders, the result is not deployable software, but it offers a more inspectable account of a fine-grained complexity result and the assumptions behind it.

## What happened
ECCC report TR26-247, “A simplified proof of polynomial improvements for 3SUM and APSP,” was published on October 11, 2026 by Sankeerth Rao Karingula and Shachar Lovett. The report concerns two well-known problems in fine-grained complexity: integer 3SUM and all-pairs shortest paths, or APSP. Its stated contribution is a simplified proof of polynomial improvements previously established by Alman and Vassilevska Williams. The report is explicit that its exponents are weaker than those in the earlier result.

The central ingredient is selected-entry matrix multiplication. Instead of computing every entry in the product of dense rectangular matrices, the task is to compute a prescribed set of entries. That narrower output requirement is not presented as a mere implementation shortcut. It is the structure around which the proof is organized: the authors aim to exploit the fact that the reduction requests only certain outputs rather than a complete dense matrix product.

The report says the construction starts from Schonhage’s inner/outer-product identity. From there, it builds a multiplication rule that shares intermediate products among many requested outputs. In the authors’ account, the benefit comes from reuse: work needed for one requested entry can contribute to others, rather than being charged as if each output were computed independently.

The multiplication rule is then applied recursively. The analysis bounds the work by counting requested entries at each level of the recursion. This is a meaningful shift in how the proof is described. The relevant resource is not simply the cost of materializing a full matrix product; it is the changing number and arrangement of entries the recursive construction has been asked to return.

Applied to incidence matrices, the construction yields an algorithm for Offline Set Disjointness over a small universe. The report then invokes known deterministic reductions to obtain truly subquadratic integer 3SUM and truly subcubic APSP for polynomially bounded integer inputs. Those qualifications matter: the supplied source does not say that every formulation of 3SUM or APSP receives the same guarantee, or that the result is an empirical speedup on deployed workloads.

The public ECCC page identifies the work as TR26-247 and lists “fine grained complexity” and “matrix multiplication” as keywords. It recorded 2,050 downloads in the supplied source material. The paper is a research report, not a product release: the source provides no API, library, implementation package, pricing, access tier, or benchmark result. Its concrete claim is a simpler proof route to known polynomial improvements, with weaker exponents, rather than a new best-known practical algorithm.

## What the archive adds
We have not covered this before; it opens a new thread.

## Trend signal
No supplied pattern is a genuine fit: this is a theoretical algorithm result rather than evidence about an operating pattern for AI systems.

## Why it matters
For teams building with AI, this is not a new model, agent framework, inference endpoint, or optimization that can be adopted this week. Its value is indirect but real for organizations that need to distinguish theoretical algorithmic progress from operational performance claims. A simplified proof can make a result easier to inspect, teach, challenge, and potentially adapt in later work.

That is especially relevant when engineering decisions depend on research summaries. Terms such as “subquadratic” and “subcubic” describe asymptotic behavior under stated conditions; they do not establish that an existing pipeline will become faster, cheaper, or easier to operate. The report’s structure makes the boundaries visible: selected rather than complete matrix outputs, a recursive work count, a small-universe Offline Set Disjointness step, deterministic reductions, and polynomially bounded integer inputs.

Teams working near graph, search, optimization, or matrix-style workloads can use this kind of result as input to technical radar work. The appropriate action is to ask whether a downstream problem has the same input structure and whether the reduction preserves the operational constraints that matter. It is not to infer a production advantage from the existence of the theorem alone.

## Limits and uncertainty
The report establishes a theoretical result, not an implementation, benchmark suite, library, or practical performance comparison. The supplied material includes no runtime measurements on real datasets and no information about constants, memory use, hardware behavior, engineering trade-offs, or a deployment recipe. Its guarantees apply to polynomially bounded integer inputs, and they should not be generalized to arbitrary input models without examining the complete proof.

The source also says that the simplified proof has weaker exponents than the earlier improvements. It does not provide those exponents in the supplied excerpt. As a result, this note cannot quantify the gap, determine whether the simpler route is useful for a particular implementation, or judge where its asymptotic trade-off becomes material. The evidence supports the report’s stated proof outline, not a claim of practical superiority.

Nor does the source establish a connection to AI-agent performance, formal verification tooling, or present-day model capabilities. The result may be relevant to researchers who study algorithmic foundations, but that relevance should not be confused with an announced improvement to an AI system.

## Skill to build now
When an algorithmic claim enters an engineering discussion, separate three questions before treating it as a roadmap input: what inputs the theorem covers, what operation is being reduced, and whether the improvement is asymptotic or measured. This week, take one performance claim in a planning document and label those three items explicitly.

For this report, the boundaries are unusually clear: prescribed matrix entries rather than a full product, polynomially bounded integer inputs, and asymptotic improvements reached through deterministic reductions. Recording those constraints prevents a research result from being converted prematurely into a generic performance promise.

## Reader takeaway
Karingula and Lovett offer a simpler route to known polynomial improvements for integer 3SUM and APSP, using selected-entry matrix multiplication and recursive accounting of requested outputs. It is a meaningful fine-grained complexity result and a useful reminder to read theorem conditions closely, not evidence of an immediate software or AI-performance upgrade.

Editor: [Andrey Reshetnikov](https://newruntime.com/owner-profile.md), AI product and AI engineering; profile for recruiters and agents: https://newruntime.com/owner-profile.json

## Continue in the graph

Next records for an agent, linked to their Markdown twins. Replace `.md` with `.json` for structured fields, including `next_reads`.

- collection: [Field Notes](https://newruntime.com/posts.json): Open the latest editorial analysis.
- collection: [Source Ledger](https://newruntime.com/source-ledger.json): Inspect the public source evidence graph.
- whole graph: [discovery graph](https://newruntime.com/discovery-graph.json) (typed nodes and edges) and [site index](https://newruntime.com/site-index.md)