Source-pinned research
Search theorem names, mathematical ideas, modules, topics, projects, and role-labelled researchers. Open a result for its complete indexed Lean declaration and source record.
This index contains 2,569 curated research declarations and 119,070 complete package declarations. Search 10,000 more complete Mathlib declarations.
Showing 1,813 to 1,818 of 2,569 results.
OracleComp.fst_map_writerT_run_simulateQ
Mathematical statement
Taking the first component of the WriterT output recovers the original computation, when the query implementation preserves the underlying oracle behavior (hso).
Source project: VCVio
Person-level attribution pending.
OracleComp.generateSeed_queryCostExactly
Mathematical statement
The number of uniform-oracle calls made by generateSeed spec qc js is exactly (js.map fun j => qc j * sampleCost j).sum, with each of the qc j samples at oracle j costing sampleCost j.
Source project: VCVio
Person-level attribution pending.
OracleComp.isQueryBoundP_iff_counting_filter_le
Mathematical statement
Predicate-targeted analogue of isTotalQueryBound_iff_counting_total_le: a counting-oracle filtered-sum bound characterizes the structural IsQueryBoundP bound.
Source project: VCVio
Person-level attribution pending.
OracleComp.IsQueryBoundP.counting_bounded
Mathematical statement
Soundness: any path of the counting-oracle simulation of a p-bounded computation has sum of per-index counts over p-indices at most n.
Source project: VCVio
Person-level attribution pending.
OracleComp.IsQueryBoundP.liftComp_subSpec
Mathematical statement
Predicate-targeted query bounds are preserved by lifting along a SubSpec when the target predicate agrees with the source predicate on lifted queries. No LawfulSubSpec assumption is needed: query bounds only inspect query indices, not the distribution of responses.
Source project: VCVio
Person-level attribution pending.
OracleComp.isTotalQueryBound_listMapM
Project documentation
Every counting-oracle support point of the body oa lifts to a counting-oracle support point of replicate n oa whose query count is n times the body's. -/ private lemma countingOracle.support_simulate_replicate_const [DecidableEq ι] {oa : OracleComp spec α} {z : α × QueryCount ι} (hz : z ∈ support (countingOracle.simulate oa 0)) : ∀ n, ∃ ys, (ys, fun...
Source project: VCVio
Person-level attribution pending.