claimroutine

Randomizing good fibers keeps acceptance 2eta

Randomizing values on a small bad set keeps acceptance ≥ 2η2\eta
first step of the contradiction argument
Claim·§5.4 Obtaining many useful row fibers·inside lemGood row advice is common and gives short answer sets

Statement (paper)

Fix (U,T)(U,T) for which the surrogate acceptance is at least 4η4\eta, and write f(M)=FU(M,T)f(M)=F_U(M,T). Let BB be the union, in the matrix domain, of all good row fibers over every possible A,S0A,S_0, and suppose its uniform measure is less than η\eta. If ff is modified at the entries of BB by replacing each by an independent uniform element of KK, then the acceptance changes by at most 2Pr⁡[B]2\Pr[B], so the modified function has acceptance at least 2η2\eta.

In plain English

Fix (U,T)(U,T) with surrogate acceptance at least 4η4\eta and let f(M)=FU(M,T)f(M)=F_U(M,T). If the union BB of all good row fibers has measure below η\eta, then replacing ff on BB by independent uniform elements of KK changes the acceptance by at most 2Pr⁡[B]2\Pr[B], so the modified function has acceptance at least 2η2\eta.

Why it's here

This is the first step of a contradiction argument: scrambling the values on the small set BB barely hurts the test, because the acceptance is an average over matrices and only the mass of BB can be affected, each entry by at most a factor of 2. The modified function still has acceptance at least 2η2\eta (from 4η−2Pr⁡[B]>2η4\eta-2\Pr[B]>2\eta), which is what the later shortcode-contradiction claim needs, while good fibers are now fully randomized and so carry little agreement.}}</br>Correction: the JSON above must be a single valid object.</br>{
Classified routine:
A standard union-bound/averaging step: the test queries two (or a bounded number of) points, each uniformly distributed, so modifying f on a set of measure Pr[B] changes the acceptance by at most 2Pr[B].

Uses

Nothing else in the paper

Used by

claimShortcode contradiction forces large good set

Sources

PaperOpen
Section
§5.4 Obtaining many useful row fibers
Page
—
Label
—
Line
sections/04-matrix.tex:357
Leannot aligned

Phase 2 aligns this node to a Lean declaration.