claimroutine
Random replacements match few on slices
Random replacements match the target on few points of every allowed slice
bounds the agreement added by randomization
Claim·§5.4 Obtaining many useful row fibers·inside lemGood row advice is common and gives short answer sets
Statement (paper)
For all sufficiently large , the random replacements at the entries of can be chosen so that, for every simultaneous row and column slice with at most row specifications and at most column specifications, and for every target , the randomized matches contribute less than of the size of the slice, i.e.\ fewer than matches.
In plain English
For all sufficiently large , the random replacements at the entries of can be chosen so that every simultaneous row and column slice with at most row specifications and at most column specifications, and every target , has fewer than randomized matches, where is the slice size.
Why it's here
This is a union-bound or concentration step showing that the random values placed in almost never agree with the target on any allowed slice. That caps the agreement the replacements can add, so the modified function has agreement below on every allowed slice, which the next claim uses to force a contradiction and a large good set. The slices have at most row and column specifications, so they are few enough for the random choices to be controlled simultaneously.
Classified routine:
A standard probabilistic argument: a Chernoff bound for each slice and target, followed by a union bound over the boundedly many slices with at most r row and r column specifications. This is the usual random-replacement step from Grassmann/subspace agreement-testing proofs (as in the 2-to-2 Games line of work).
Uses
Nothing else in the paper
Used by
Sources
PaperOpen
- Section
- §5.4 Obtaining many useful row fibers
- Page
- —
- Label
—- Line
sections/04-matrix.tex:367
Leannot aligned
Phase 2 aligns this node to a Lean declaration.