definitionnovel

Measurement design separating clause dependence

Definition·def:overview-measurement-structure·§2.4 Separating the sum by fixing measurements

Statement (paper)

For the given coefficient vectors P⃗e,v(t)\vec{P}_{e,v}(t), an \emph{(r,τ,D)(r,\tau,D)-design at tt} consists of groups SgS_g, clause assignments σe(t)\sigma_e(t), and measurement matrices CgC_g satisfying the following four conditions: \begin{enumerate} \item Small groups. Partition the variables into disjoint groups [n]=S1⊔⋯⊔Sr[n]=S_1\sqcup\cdots\sqcup S_r, with ∣Sg∣⩽2n/r|S_g|\le2n/r. \item One assigned group per clause. Assign each clause ee to one group σe(t)∈[r]\sigma_e(t)\in[r]. Condition 4 must hold with this same group for every replacement linear form of clause ee. \item Few bounded measurements. Each group gg has an integer matrix CgC_g with columns indexed by SgS_g and cgc_g rows. Each row specifies one linear measurement of the variables in SgS_g. There are at most 2τn2\tau n rows in total, and the sum of absolute values of the coefficients in each row is at most DD. For an assignment xx, write xg=x∣Sg,yg=Cgxg,y⃗=(y1,…,yr). x_g=x|_{S_g},\qquad y_g=C_gx_g,\qquad \vec{y}=(y_1,\ldots,y_r). \item Dependence on other groups only through measurements. Suppose clause ee is assigned to group g=σe(t)g=\sigma_e(t). Each replacement linear form of this clause may depend freely on the variables in SgS_g. Its dependence on any other group ShS_h must be a linear combination of that group's measurements yhy_h. Precisely, for every v∈Iev\in I_e, there must be coefficient vectors λ⃗e,v,h∈Qch\vec{\lambda}_{e,v,h}\in\mathbb Q^{c_h}, for h≠gh\ne g, such that, for every x∈Qnx\in\mathbb Q^n, ⟨P⃗e,v(t),x⟩=⟨P⃗e,v(t)∣Sg,xg⟩+∑h≠g⟨λ⃗e,v,h,yh⟩. \langle\vec{P}_{e,v}(t),x\rangle =\langle\vec{P}_{e,v}(t)|_{S_g},x_g\rangle +\sum_{h\ne g}\langle\vec{\lambda}_{e,v,h},y_h\rangle. Equivalently, P⃗e,v(t)∣Sh\vec{P}_{e,v}(t)|_{S_h} lies in the row space of ChC_h for every h≠gh\ne g. \end{enumerate}

In plain English

An (r,τ,D)(r,\tau,D)-design at tt splits the variables into rr groups of size at most 2n/r2n/r, assigns each clause ee to one group σe(t)\sigma_e(t), and gives each group an integer measurement matrix CgC_g with at most 2τn2\tau n rows in total and row coefficient sums at most DD. Each clause's replacement linear forms depend freely only on its own group, and on every other group ShS_h only through the measurements yh=Chxhy_h=C_hx_h.

Why it's here

This definition packages the structure needed to separate the sum by fixing measurements: once the measurement values y⃗\vec{y} are fixed, each clause's linear forms depend on only one group's variables plus known constants. The groups and clause assignment decide where each clause's free dependence lives, while the bounds on the number and size of the measurements limit how many measurement outcomes need to be enumerated.
Classified novel:
This measurement-design structure, a partition of the variables into groups with low-weight integer measurements so that each clause's replacement linear forms depend on other groups only through those measurements, is the paper's own device for separating the sum. It is what lets the claimed subexponential Max-k-SAT algorithm enumerate measurement outcomes, and no prior result is known to provide such a structure.

Uses

Nothing else in the paper

Used by

Nothing in the paper

Sources

PaperOpen
Section
§2.4 Separating the sum by fixing measurements
Page
—
Label
def:overview-measurement-structure
Line
main_full_version.tex:690
Leannot aligned

Phase 2 aligns this node to a Lean declaration.