online_carpool_orientations
For an instance on vertex set Fin n and a random tape r of K boolean coins, given an orientation function orient that takes an edge history in List (Fin n × Fin n) and the coins in Fin K → Bool to an orientation bit in Bool, online_carpool_orientations n orient edges r is the list of boolean orientations for the edges in edges, where the i-th edge is oriented using orient applied to the prefix edges.take (i + 1) and r.
Statement
def online_carpool_orientations (n : ℕ) {K : ℕ}
(orient : List (Fin n × Fin n) → (Fin K → Bool) → Bool)
(edges : List (Fin n × Fin n)) (r : Fin K → Bool) : List Bool- Defined in
- arXiv:2611.00388 Sec 1.1, Online carpooling against an oblivious adversary
- Verified
- 06 Nov 2026
- Axioms
- none listed
Read back from the Lean
Given a natural number n, an implicit natural number K, an orientation rule orient : List (Fin n × Fin n) → (Fin K → Bool) → Bool, a list of edges edges : List (Fin n × Fin n), and a function r : Fin K → Bool, online_carpool_orientations n orient edges r is defined as the List Bool of length edges.length whose i-th element (for index i : Fin edges.length) is orient (edges.take (i.val + 1)) r (that is, the result of evaluating orient on the prefix of edges of length i + 1 together with r).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The list of boolean orientations produced by an online carpooling algorithm given edge history on Fin n and random coins. -/ def online_carpool_orientations (n : ℕ) {K : ℕ} (orient : List (Fin n × Fin n) → (Fin K → Bool) → Bool) (edges : List (Fin n × Fin n)) (r : Fin K → Bool) : List Bool := List.ofFn (fun i : Fin edges.length => orient (edges.take (i.val + 1)) r)