One stage of the oracle construction
DefinitionAvgPHETH_Supplement_OracleData_stageaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
Stage of the oracle construction consists of three steps:
- a restriction round on every group with , after which the cumulative assignment is ;
- the assignment of all valid -queries with , in increasing order of ;
- the completion of the groups with .
This definition maps the state before the stage (partial assignment and table of -answers) and the seeds of the round to the state after the stage.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_OracleData_complete
import Definitions.Def_AvgPHETH_Supplement_restrictRound
import Definitions.Def_AvgPHETH_Supplement_aFill
namespace AvgPHETH.Supplement
/-- One stage `i` of the oracle construction, applied to the state `st = (ρ, tab)` left by the earlier
stages, where `ρ` is the partial assignment to the construction variables and `tab` the table of
`A`-answers (Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), §8.1, "In stage `i = 1, 2, …`", pp.40–41 (PDF 42–43)):
1. a restriction round on every group `(k, n)` with `D(k, n) ≥ i`, giving `ρ_i`;
2. the `A`-queries with `i(T) = i` are assigned, in increasing order of `T`;
3. the groups with `D(k, n) = i` are completed.
**Formalization Note** `u` are the seeds of this stage's restriction round (`restrictRound`). After
step 2 the entry of the table for a query with time parameter `T` is the one written when `T` was
processed, `aFill … (T + 1)`. -/
noncomputable def OracleData.stage (D : OracleData) (u : CVar → ℕ → ℝ) (i : ℕ)
(st : (CVar → Option (List Bool)) × (ℕ → ℕ → List Bool → ℕ → Option Bool)) :
(CVar → Option (List Bool)) × (ℕ → ℕ → List Bool → ℕ → Option Bool) :=
(D.complete i (restrictRound D.eps u (fun k n => i ≤ D.compStage k n) st.1)
(fun j d w T =>
aFill D.eps D.mach (restrictRound D.eps u (fun k n => i ≤ D.compStage k n) st.1) i st.2
(T + 1) j d w T),
fun j d w T =>
aFill D.eps D.mach (restrictRound D.eps u (fun k n => i ≤ D.compStage k n) st.1) i st.2
(T + 1) j d w T)
end AvgPHETH.Supplement
Source
Hirahara–Juvekar–Nanashima, Average-Case Hardness of PH from ETH-Type Hypotheses, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), §8.1, pp.40–41 (PDF 42–43)