Proof of `Håstad inapproximability for bounded-error randomized algorithms` (1st statement)
groundedproofs/Lax323828Proofs/RandomizedCliqueHardness.lean · lax-323828
What this proof establishes
- thm✓
Lax323828.Amplification - thm✓
Lax323828.CenteredProjection - thm✓
Lax323828.EncodedReduction - thm✓
Lax323828.FAFComposition - thm✓
Lax323828.FAFLocalTests - thm✓
Lax323828.FAFPatterns - thm✓
Lax323828.FiniteProbability - thm✓
Lax323828.FreshBitSampling - thm✓
Lax323828.GraphEncoding - thm✓
Lax323828.MajorityAmplification - thm✓
Lax323828.ProjectionEncoding - thm✓
Lax323828.RandomizedReduction - thm✓
Lax323828.SamplingParameters - thm✓
Lax323828.TestRepetition - thm✓
Lax323828.TestSampling
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Reuse the uniform PCP-to-clique gap reduction. Amplify the randomized estimator's comparison, combine independent reduction and estimator tapes, and accept only if two independent combined trials accept. The finite-tape compiler realizes the resulting bounded-error test in the registered BPP model.