Parallel algorithms with two oracles: matroid intersection and submodular maximization (§1)
DefinitionParallelMatroidBasis_Main_Supplement_MultiOracleThe round model is that of the base mission: an algorithm is fixed before the input, one procedure for every ground-set size ; in each round it submits a finite batch of queries, and each batch and the final output are functions of its private random tape and of the earlier batches with their answers only.
- For an algorithm with oracle , every run uses at most rounds means that for every random tape the run halts after at most batches; at most queries per round means every batch of every run has at most queries; at most queries of a kind in total means that, on every run, the number of queries of that kind summed over all rounds is at most .
- Matroid intersection (PDF p.5). The queries are independence queries to either of two matroids , on the same ground set , answered by or . A set solves the matroid intersection problem if and for every , i.e. .
- Submodular maximization under a matroid constraint (PDF p.5). The queries are independence queries to a matroid and value queries returning the exact real value of a set function . For , a set is a -approximate solution if and
- The success probabilities are the probabilities, over the random tape, that the run halts with a solution in the sense of 2 or 3.
These are the problems of Theorems 1.4 and 1.5.
Formalization Note Both models instantiate the published ExactParallelSampling.QuasiUniform.Protocol: intersection queries are pairs with Boolean answers; submodular queries are Finset (Fin n) ⊕ Finset (Fin n) with answers in Bool ⊕ ℝ. The maximum over is written as " for every independent ", which is the same condition since is finite and contains . Total query counts sum the batch sizes over every step of a run; batches after halting are empty.
import Mathlib
import Definitions.Def_ExactParallelSampling_QuasiUniform_Protocol
import Definitions.Def_ParallelMatroidBasis_Main_QueryModel
noncomputable section
open Classical MeasureTheory
namespace ParallelMatroidBasis.Main.Supplement
/-! # Parallel algorithms with several oracles: matroid intersection and submodular maximization
(Putterman–Khanna–Song, STOC 2027 submission #589, §1 "Applications", PDF p.5 (printed p.3))
The round model is the published `ExactParallelSampling.QuasiUniform.Protocol`, as in the base
mission's `QueryModel`: each batch of queries and the output are functions of the private random
tape and of the earlier batches with their answers only. -/
open ExactParallelSampling.QuasiUniform
/-! ## Round and query counts of a run, for an arbitrary oracle -/
/-- Every run of `P` against the oracle `ans` (every random tape) halts after at most `R` rounds. -/
def RunRoundsAtMost {Q A O : Type} (P : Protocol Q A O) (ans : Q → A) (R : ℝ) : Prop :=
∀ ω : Tape, ∃ r : ℕ, P.rounds ans ω = (r : ℕ∞) ∧ (r : ℝ) ≤ R
/-- Every round of every run of `P` against `ans` asks at most `K` queries. -/
def RunQueriesPerRoundAtMost {Q A O : Type} (P : Protocol Q A O) (ans : Q → A) (K : ℕ) : Prop :=
∀ (ω : Tape) (r : ℕ), (P.batchAt ans ω r).card ≤ K
/-- Every run of `P` against `ans` asks, over all its rounds together, at most `K` queries of the
kind selected by `sel`. (Batches after halting are empty, so summing over any number `R` of steps
counts all queries of the run.) -/
def RunTotalQueriesAtMost {Q A O : Type} (P : Protocol Q A O) (ans : Q → A) (sel : Q → Prop)
(K : ℕ) : Prop :=
∀ (ω : Tape) (R : ℕ),
∑ r ∈ Finset.range R, ((P.batchAt ans ω r).filter sel).card ≤ K
/-! ## Matroid intersection (PDF p.5) -/
/-- A query of a matroid-intersection algorithm: an independence query `(0, T)` to `M₁` or
`(1, T)` to `M₂`. -/
abbrev IntersectionQuery (n : ℕ) := Fin 2 × Finset (Fin n)
/-- The two independence oracles of `M₁` and `M₂` on the same ground set. -/
def pairOracle {n : ℕ} (M₁ M₂ : Matroid (Fin n)) : IntersectionQuery n → Bool :=
fun q => if q.1 = 0 then indOracle M₁ q.2 else indOracle M₂ q.2
/-- A parallel matroid-intersection algorithm: one protocol for every ground-set size `n`, asking
independence queries to the two matroids and outputting a subset of `Fin n`. -/
abbrev IntersectionAlgorithm :=
(n : ℕ) → Protocol (IntersectionQuery n) Bool (Finset (Fin n))
/-- `S` solves the matroid intersection problem for `M₁, M₂`: it is independent in both and at
least as large as every common independent set. -/
def IsMaxCommonIndep {n : ℕ} (M₁ M₂ : Matroid (Fin n)) (S : Finset (Fin n)) : Prop :=
M₁.Indep (↑S : Set (Fin n)) ∧ M₂.Indep (↑S : Set (Fin n)) ∧
∀ T : Finset (Fin n), M₁.Indep (↑T : Set (Fin n)) → M₂.Indep (↑T : Set (Fin n)) →
T.card ≤ S.card
/-- The probability, over the random tape, that `A` halts on `(M₁, M₂)` with a maximum common
independent set. -/
def intersectionSuccessProb (A : IntersectionAlgorithm) (n : ℕ) (M₁ M₂ : Matroid (Fin n)) :
ENNReal :=
tapeLaw {ω | ∃ S : Finset (Fin n), (A n).output (pairOracle M₁ M₂) ω = some S ∧
IsMaxCommonIndep M₁ M₂ S}
/-! ## Submodular maximization under a matroid constraint (PDF p.5) -/
/-- A query of a submodular-maximization algorithm: an independence query `inl T` to `M` or a
value query `inr T` to `f`. -/
abbrev SubmodQuery (n : ℕ) := Finset (Fin n) ⊕ Finset (Fin n)
/-- The combined oracle: `inl T ↦ inl (Ind(T))`, `inr T ↦ inr (f(T))` (exact real values). -/
def submodOracle {n : ℕ} (M : Matroid (Fin n)) (f : Finset (Fin n) → ℝ) :
SubmodQuery n → Bool ⊕ ℝ
| .inl T => .inl (indOracle M T)
| .inr T => .inr (f T)
/-- Independence queries. -/
def IsIndepQuery {n : ℕ} : SubmodQuery n → Prop
| .inl _ => True
| .inr _ => False
/-- Value queries. -/
def IsValueQuery {n : ℕ} : SubmodQuery n → Prop
| .inl _ => False
| .inr _ => True
/-- A parallel algorithm for submodular maximization under a matroid constraint: one protocol for
every ground-set size `n`, outputting a subset of `Fin n`. -/
abbrev SubmodAlgorithm := (n : ℕ) → Protocol (SubmodQuery n) (Bool ⊕ ℝ) (Finset (Fin n))
/-- `S` is a `(1/2 − ε)`-approximate solution: `S ∈ I` and `f(S) ≥ (1/2 − ε) f(T)` for every
`T ∈ I`, i.e. `f(S) ≥ (1/2 − ε) max_{T ∈ I} f(T)`. -/
def IsHalfApprox {n : ℕ} (M : Matroid (Fin n)) (f : Finset (Fin n) → ℝ) (ε : ℝ)
(S : Finset (Fin n)) : Prop :=
M.Indep (↑S : Set (Fin n)) ∧
∀ T : Finset (Fin n), M.Indep (↑T : Set (Fin n)) → (1 / 2 - ε) * f T ≤ f S
/-- The probability, over the random tape, that `A` halts on `(M, f)` with a
`(1/2 − ε)`-approximate solution. -/
def submodSuccessProb (A : SubmodAlgorithm) (n : ℕ) (M : Matroid (Fin n))
(f : Finset (Fin n) → ℝ) (ε : ℝ) : ENNReal :=
tapeLaw {ω | ∃ S : Finset (Fin n), (A n).output (submodOracle M f) ω = some S ∧
IsHalfApprox M f ε S}
end ParallelMatroidBasis.Main.Supplement