Keeping polynomial corrections fixed while summing assignments
At a chosen evaluation point t, a replacement P(t+z) need not obey the separation design that works at t. Write Delta P(z)=P(t+z)-P(t); every entry of this polynomial row is divisible by z. Replace each input by P(t) dot x + Delta P(z) dot X, where dot means the weighted sum of row coefficients times inputs, with one separate auxiliary variable X_i per original variable, and call the product of the transformed factors G_x(X,z). Setting X=x gives the original summand at t+z. Instead, fixing X to one chosen Boolean vector makes the correction independent of the assignment x being summed, preserving separation at t. Every appearance of X brings a factor z, so [z^j]G_x has total X-degree at most j.
0
1
Tags
Math
Related
Recovering a bounded-degree polynomial from exact values
Removing unwanted dependencies at selected evaluation points
Why the shared-measurement algorithm includes each contribution once
A worked weighted sum using shared measurements
When the shared-measurement enumeration can be small
Restricting the measurement sum to assignments with selected bits equal to one
Splitting the constructed measurements into independent group contributions
Related
Recovering a bounded-degree polynomial from exact values
Removing unwanted dependencies at selected evaluation points
Why the shared-measurement algorithm includes each contribution once
A worked weighted sum using shared measurements
When the shared-measurement enumeration can be small
Restricting the measurement sum to assignments with selected bits equal to one
Splitting the constructed measurements into independent group contributions