Grouping tests and variables before indexing incidence subsets
Put lambda=ceil(log2 n), nu=ceil(log2 lambda), and J=ceil(n^(1/4)). Partition the remaining tests and the free variables separately into J groups with sizes differing by at most one; empty groups are allowed. Let N_gh count distinct incidences from test group g to variable group h, and N=sum N_gh. A test scope has polylogarithmic size and each free variable has polylogarithmic incidence after branching. Each group contains O_c(n^(3/4)) objects, so its total incident coordinates are at most n^(3/4) lambda^{O_(k,c)(1)}. Grouping is not yet an assignment of bits to variables.
0
1
Tags
Math
Related
Why retained incidence monomials have only linearly many selected coordinates
Extracting a multilinear incidence coefficient in the truncated residue ring
The manuscript parameter recipe for a sparse measurement layout
Counting the auxiliary substitution and restriction pairs
Why operation counts need bounds on integer bit lengths
Bounding coefficients produced by the parity-lift construction
The quantitative contract for the initial sparse checks
The stated fast-contraction theorem and its input requirements
Choosing enough residue-field elements for interpolation
Related
Why retained incidence monomials have only linearly many selected coordinates
Extracting a multilinear incidence coefficient in the truncated residue ring
The manuscript parameter recipe for a sparse measurement layout
Counting the auxiliary substitution and restriction pairs
Why operation counts need bounds on integer bit lengths
Bounding coefficients produced by the parity-lift construction
The quantitative contract for the initial sparse checks
The stated fast-contraction theorem and its input requirements
Choosing enough residue-field elements for interpolation