claimroutineinferred_dep

Conditional expectations are efficiently computable

Claim·§4.4 Choosing the variable and factor groups·inside lemDeterministic balanced incidence labeling

Statement (paper)

The conditional expectations of Φ\Phi and Ξ\Xi, given any partial fixing of the choices ava_v and dfd_f, can be computed exactly, as rational numbers with O(log⁡(2D)+log⁡(2M)+log⁡(2n)+log⁡(2Q)+log⁡(2+b+w))O(\log(2D)+\log(2M)+\log(2n)+\log(2Q)+\log(2+b+w)) bits in numerators and denominators, in poly⁡(n,M,∣F∣,D,Q,r,b,w)\poly(n,M,|\mathcal F|,D,Q,r,b,w) bit operations. Consequently the entire derandomized construction, which fixes at most n+∣F∣n+|\mathcal F| choices each with K=rQK=r^Q candidate values, takes poly⁡(n,M,∣F∣,D,Q,r,b,w)\poly(n,M,|\mathcal F|,D,Q,r,b,w) bit operations.

In plain English

The conditional expectations of the potentials Φ\Phi and Ξ\Xi given any partial fixing of the labels ava_v and dfd_f can be computed exactly as small rational numbers in time polynomial in n,M,∣F∣,D,Q,r,b,wn,M,|\mathcal F|,D,Q,r,b,w. Hence the whole derandomized label construction runs in that polynomial time.

Why it's here

This makes the method of conditional expectations from the previous claim an actual deterministic algorithm, which gives the polynomial running time stated in the lemma. Exact evaluation with bounded bit length is possible because there are at most n+∣F∣n+|\mathcal F| choices, each with K=rQK=r^Q candidate values, so only polynomially many conditional expectations are needed.
Classified routine:
Standard efficiency bookkeeping for the method of conditional expectations (Erdős–Selfridge / Raghavan-style derandomization): each potential term's conditional expectation is a sum of explicitly computable probabilities, and there are polynomially many choices to fix.

Uses

claimConditional expectations yield balanced labels

Used by

Nothing in the paper

Sources

PaperOpen
Section
§4.4 Choosing the variable and factor groups
Page
—
Label
—
Line
main_full_version.tex:2512
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Exact polynomial-time conditional expectation computation" rests on claim-lem-incidence-labels-2