Version history

Submission versions

  1. lax-323828current version

    Håstad’s inapproximability of Max Clique

  2. lax-253009viewing

    Håstad’s inapproximability of Max Clique

    GitHub sourceShown on this page

Proof of `Håstad inapproximability for bounded-error randomized algorithms` (1st statement)

groundedproofs/Lax253009Proofs/RandomizedCliqueHardness.lean · lax-253009

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.