Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Deterministic filtering: from a modular counting oracle to All-Edges Exact Triangle

Proved
Light.Filter.filter_host

by xuanji · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

apsp-2996001apsp-exponentfine-grained-complexityword-ram

For every program PPP whose procedure pop_opo​ solves the counting oracle task oracleTask within ToT_oTo​ steps with need νo\nu_oνo​, there are procedures RRR and an index p′p'p′ such that procedure p′p'p′ of P+ ⁣ ⁣+RP\mathbin{+\!\!+}RP++R solves All-Edges Exact Triangle (aeTask: for each pair (a,b)(a,b)(a,b) of an nnn-vertex instance with weights bounded by UUU, the flag whether some ccc has w(a,b)+w(b,c)+w(a,c)=0w(a,b)+w(b,c)+w(a,c)=0w(a,b)+w(b,c)+w(a,c)=0) within filterTime To n U steps and with need filterNeed νo n U; and filterNeed νo is polynomially bounded whenever νo\nu_oνo​ is.

filterTime is the time of the host: computing the parameters, a sieve for the prime pool in [R,2R)[R,2R)[R,2R), the marks, and roundsOf n rounds of rOf n steps, each step calling the oracle once per pool prime and each round twice more, every call within the largest oracle time over the moduli up to Pmax⁡=(2R)rP_{\max}=(2R)^rPmax​=(2R)r; then the final answer (the certified flags under the guard, or a scan of the remaining candidates).

Preamble
/-
Copyright (c) 2026 Anthropic, PBC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
SPDX-License-Identifier: Apache-2.0
-/
-- Generated by skeleton subtraction from the ThreeSumApsp library at commit 7c34437be804.

import Definitions.Def_APSP2996001_Defs2

set_option autoImplicit false
set_option relaxedAutoImplicit false

open ThreeSumApsp
open Light
open Light.Filter
open ThreeSumApsp.Spec Light.Sec3
variable {lim : Limits}
Formal statement
theorem Light.Filter.filter_host :
    (∀ (P : Program) (po : ℕ) (To : List ℕ → ℕ) (needo : List ℕ → Light.Need),
      SolvesN oracleTask P po To needo →
      ∃ (R : Program) (p' : ℕ), Solves aeTask (P ++ R) p' (filterTime To) (filterNeed needo)) ∧
    (∀ needo, PolyNeedN needo → PolyNeed (filterNeed needo)) := by sorry
Source
Developed for the prove2.me APSP exponent campaign (https://prove2.me/campaigns/apsp-exponent) on top of the Lean formalization anthropics/formal-math, folder 3sum-apsp, commit e1a4e65 (https://github.com/anthropics/formal-math/tree/e1a4e6508154ea59f030480661590a9fe3018011/3sum-apsp; Lean v4.33.1, Mathlib v4.33.1). The statement comes from the file 3sum-apsp/ThreeSumApsp/Filter/HostMain.lean of the campaign's modified copy of that library, which is not published; the new definitions it uses are in the platform definition bundles APSP2996001_Defs1 and APSP2996001_Defs2 (and APSP299791_Defs1 to APSP299791_Defs5 of the 2.99791 entry). It follows the technical note "Deterministic APSP via thin products" (6 October 2026) refining J. Alman and V. Vassilevska Williams, "Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs", arXiv:2610.06783v1 (https://arxiv.org/abs/2610.06783v1), Lemma 3.1 and Section 3.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me