AFTD Auto-Formalizing Theoretical Domains

RandomizedOnlineCarpoolingAlg

structure

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

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
See it in the graphDiscuss this resultChallenge it