Averaging NW reconstruction to fixed advice -- definitions

The advice choice retains precisely the outside seed assignment, later output tail, and independent candidate bit. Its predictor is then a deterministic Boolean function of the uniformly varying hard-function input.

@[reducible, inline]

abbrev Complexity.NWDesign.ReconstructionAdvice {outputLength inputLength seedLength : ℕ} (design : NWDesign outputLength inputLength seedLength) (current : Fin outputLength) : Type

Fixed data chosen by averaging after a hybrid coordinate has been selected.

Equations

• design.ReconstructionAdvice current = ((↥(design.outsideCoordinates current) → Bool) × (↥(Complexity.NWDesign.laterCoordinates current) → Bool) × Bool)

def Complexity.NWDesign.reconstructionAgreementProbability {outputLength inputLength seedLength : ℕ} (design : NWDesign outputLength inputLength seedLength) (hardFunction : (Fin inputLength → Bool) → Bool) (test : Finset (Fin outputLength → Bool)) (current : Fin outputLength) (advice : design.ReconstructionAdvice current) : ℚ

Agreement probability of one fixed reconstruction predictor with the hard function over a uniform challenge.

Equations

• One or more equations did not get rendered due to their size.

def Complexity.NWDesign.averageReconstructionAgreement {outputLength inputLength seedLength : ℕ} (design : NWDesign outputLength inputLength seedLength) (hardFunction : (Fin inputLength → Bool) → Bool) (test : Finset (Fin outputLength → Bool)) (current : Fin outputLength) : ℚ

Joint agreement probability before fixing the reconstruction advice.

Equations

• One or more equations did not get rendered due to their size.

def Complexity.NWDesign.goodReconstructionAdviceProbability {outputLength inputLength seedLength : ℕ} (design : NWDesign outputLength inputLength seedLength) (hardFunction : (Fin inputLength → Bool) → Bool) (test : Finset (Fin outputLength → Bool)) (current : Fin outputLength) (agreementThreshold : ℚ) : ℚ

Probability that a uniformly sampled advice choice attains a requested agreement threshold.

Equations

• One or more equations did not get rendered due to their size.