Deterministic filtering: from a modular counting oracle to All-Edges Exact Triangle
ProvedLight.Filter.filter_hostFor every program whose procedure solves the counting oracle task oracleTask within steps with need , there are procedures and an index such that procedure of solves All-Edges Exact Triangle (aeTask: for each pair of an -vertex instance with weights bounded by , the flag whether some has ) within filterTime To n U steps and with need filterNeed νo n U; and filterNeed νo is polynomially bounded whenever is.
filterTime is the time of the host: computing the parameters, a sieve for the prime pool in , 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 ; then the final answer (the certified flags under the guard, or a scan of the remaining candidates).
/-
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}
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