Proof of `Håstad inapproximability for bounded-error randomized algorithms` (1st statement)
groundedproofs/Lax253009Proofs/RandomizedCliqueHardness.lean · lax-253009
What this proof establishes
- thm✓
Lax253009.Amplification - thm✓
Lax253009.CenteredProjection - thm✓
Lax253009.EncodedReduction - thm✓
Lax253009.FAFComposition - thm✓
Lax253009.FAFLocalTests - thm✓
Lax253009.FAFPatterns - thm✓
Lax253009.FiniteProbability - thm✓
Lax253009.FreshBitSampling - thm✓
Lax253009.GraphEncoding - thm✓
Lax253009.MajorityAmplification - thm✓
Lax253009.ProjectionEncoding - thm✓
Lax253009.RandomizedReduction - thm✓
Lax253009.SamplingParameters - thm✓
Lax253009.TestRepetition - thm✓
Lax253009.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.