RandomizedOnlineCarpoolingAlg
A randomized online carpooling algorithm consists of a function num_coins : ℕ → ℕ → ℕ specifying the number of boolean coins for vertex count n and horizon T, and an online orientation function orient : (n : ℕ) → (T : ℕ) → List (Fin n × Fin n) → (Fin (num_coins n T) → Bool) → Bool that determines the orientation bit of the arriving edge given the edge history and the random coins.
Statement
structure RandomizedOnlineCarpoolingAlg- Defined in
- arXiv:2611.00388 Sec 1.1, 3.1, Online carpooling against an oblivious adversary
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Used by 1
- PolyTimeRandomizedOnlineCarpoolingAlgA polynomial-time randomized online carpooling algorithm extends RandomizedOnlineCarpoolingAlg with a step time complexity function…
Read back from the Lean
A structure RandomizedOnlineCarpoolingAlg containing two fields:
1. num_coins : ℕ → ℕ → ℕ, a function mapping two natural numbers (presumably $n$ and $T$) to a natural number.
2. orient : (n : ℕ) → (T : ℕ) → List (Fin n × Fin n) → (Fin (num_coins n T) → Bool) → Bool, a function that, for any natural numbers $n$ and $T$, any list of pairs in Fin n × Fin n, and any function from Fin (num_coins n T) to Bool, outputs a Bool.
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
/-- A randomized online carpooling algorithm family parameterized by vertex count and horizon. -/ structure RandomizedOnlineCarpoolingAlg where num_coins : ℕ → ℕ → ℕ orient : (n : ℕ) → (T : ℕ) → List (Fin n × Fin n) → (Fin (num_coins n T) → Bool) → Bool