claimroutineinferred_dep

Small-bias shifts exist and can be found

Claim·§6.1 Initial tests that exclude small violation sets·inside lemSparse parity checks force large supports

Statement (paper)

There exist shifts

s_1,\ldots,s_{d_G}\in\{0,1\}^{\ell_G}

such that holds, i.e.

\bigl|\sum_{j=1}^{d_G}(-1)^{b\cdot s_j}\bigr|\le\varepsilon d_G

for every

b\in\{0,1\}^{\ell_G}\setminus\{\vec{0}\}

, where

\varepsilon=1/(200B\mu)

. Moreover, such a tuple of shifts can be found deterministically by exhaustively enumerating shift tuples and checking , in

\exp(O(d_G\log(m+2)))

time.

In plain English

There are shifts

s_1,\ldots,s_{d_G}\in\{0,1\}^{\ell_G}

such that every nonzero

b

has

|\sum_{j=1}^{d_G}(-1)^{b\cdot s_j}|\le\varepsilon d_G

with

\varepsilon=1/(200B\mu)

, and a deterministic exhaustive search over shift tuples finds such a tuple in

\exp(O(d_G\log(m+2)))

time.

Why it's here

This picks the shifts of the Cayley graph from the previous claim so that all nonzero Fourier (Walsh) coefficients of the shift multiset are small, which is the hypothesis for the expander mixing bound used next. Existence gives the good graph, and the brute-force search makes the construction deterministic within the stated time budget.

Classified routine:

This is the standard existence of small-bias (epsilon-biased) sets via a random choice plus a Chernoff and union bound (Alon–Goldreich–Håstad–Peralta 1992 style), combined with brute-force search. It is applied here to the shifts of the Cayley graph from the previous claim.

Uses

claimBipartite Cayley graph on shifts

Used by

claimExpander mixing bound from small bias

Sources

PaperOpen

Section: §6.1 Initial tests that exclude small violation sets
Page: —
Label: —
Line: main_full_version.tex:3301

Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

info
inferred_dep
outline: "Existence and search of epsilon-biased shifts" rests on claim-lem-sparse-checks-1