Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Deterministic clock-free one-pass streaming algorithms and their space

Definition
PermutationStreams_Parity_Supplement_OnePass

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1pattern-avoidancepermutationsstreaming

Fix nnn. A deterministic one-pass streaming algorithm for inputs π1,…,πn\pi_1,\dots,\pi_nπ1​,…,πn​ with values in [n][n][n] consists of a finite set SSS of states, an initial state s0∈Ss_0\in Ss0​∈S, a transition map δ:S×[n]→S\delta:S\times[n]\to Sδ:S×[n]→S and an output map out:S→A\mathrm{out}:S\to Aout:S→A into an answer set AAA. On input π\piπ it computes

si=δ(si−1,πi)(1≤i≤n),answer=out(sn).s_i=\delta(s_{i-1},\pi_i)\quad(1\le i\le n),\qquad \text{answer}=\mathrm{out}(s_n).si​=δ(si−1​,πi​)(1≤i≤n),answer=out(sn​).

The transition sees only the current state and the current value; the position iii is not supplied, so any counter the algorithm needs is part of its state. The algorithm may depend arbitrarily on nnn. It uses sss bits when ∣S∣≤2s|S|\le 2^s∣S∣≤2s; its space is the least such sss, namely ⌈log⁡2∣S∣⌉\lceil\log_2|S|\rceil⌈log2​∣S∣⌉.

This is the model of the paper's pattern-detection results, whose space bounds are state counts (Lemma 6.3 counts states and takes the logarithm).

Formalization Note Values are Fin n (the value vvv stands for v+1v+1v+1); the state type is a parameter S, and finiteness is imposed as [Fintype S] wherever space is measured.

Definition code
import Mathlib

namespace PermutationStreams.Parity.Supplement

/-- Braverman–Zamir §1 p.1, §1.2 p.2 and §6.1 pp.13–14: a deterministic one-pass streaming
algorithm for inputs `π(0), …, π(n-1)` with values in `Fin n` (the value `v` stands for `v + 1`).
`S` is its state set, `init` the initial state, and `step s x` the next state when the current
state is `s` and the arriving value is `x`. The transition sees only the state and the current
value: no position or clock is supplied, so a counter, if needed, lives in the (charged) state.
`out` turns the final state into the answer. The algorithm may depend arbitrarily on `n`. -/
structure OnePassAlg (n : ℕ) (S α : Type) where
  init : S
  step : S → Fin n → S
  out : S → α

/-- The state after reading `π(0), …, π(n-1)` in order from `init`. -/
def OnePassAlg.finalState {n : ℕ} {S α : Type} (A : OnePassAlg n S α)
    (π : Equiv.Perm (Fin n)) : S :=
  (List.finRange n).foldl (fun s i => A.step s (π i)) A.init

/-- The answer of one pass on the input permutation `π`. -/
def OnePassAlg.run {n : ℕ} {S α : Type} (A : OnePassAlg n S α) (π : Equiv.Perm (Fin n)) : α :=
  A.out (A.finalState π)

/-- The algorithm uses `s` bits: it has at most `2^s` states. The space of an algorithm is the
least such `s`, i.e. `⌈log₂ |S|⌉`. -/
def OnePassAlg.UsesBits {n : ℕ} {S α : Type} [Fintype S] (_A : OnePassAlg n S α) (s : ℕ) :
    Prop :=
  Fintype.card S ≤ 2 ^ s

end PermutationStreams.Parity.Supplement
Source
Mark Braverman, Or Zamir, STOC 2027 submission #74 (October 2026), Parity and Pattern Detection in Permutation Streams, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/74.pdf (SHA-256 3f0b683e25232855e98d1caa358e35f2670633688d8a799e4d01a207aa5600ea), §1 p. 1, §1.2 p. 2, §5.2–5.3 pp. 10–12 (register algorithms), §6.1 pp. 13–14 (state counts)

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 paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me