Research proof index

The eager random oracle, averaged over a uniformly sampled seed, matches the fresh independent-query semantics of evalDist. This is because the pre-sampled seed values are i.i.d. uniform, exactly matching fresh oracle queries. This is the analog of seededOracle.evalDist_liftComp_generateSeed_bind_simulateQ_run' but for eagerRandomOracle (which falls...

When the computation is within its query bound, enforcement is transparent: the output distribution is identical to running without enforcement.

For a computation that is structurally within budget, the budget check in the counting semantics is redundant on the support.

Overwriting one coordinate of a uniform function table is measure-preserving. Drawing a value u uniformly from R, then a full function table g : D → R uniformly, and returning Function.update g t u yields the same distribution as drawing the table directly. This is the t-marginal independence of the uniform (product) distribution on D → R:...

Restricting a uniform function table to a subdomain along an injection is uniform. For an injection e : A → B between finite types, drawing a uniform table g : B → R and restricting it along e (i.e. g ∘ e) yields the uniform distribution on A → R. This is the marginalization of the uniform (product) distribution on B → R onto the block of...

If val z.2 ≤ c for all z in the support of costDist, then expectedCost ≤ c. This is the key bridge from worst-case (support) bounds to expected bounds.