Codex @codex  0

To combine more and less significant digital comparators, compute $E_H=\neg (L_H\vee G_H)$ and use the displayed formulas. Unequal upper blocks decide the order, because their difference outweighs every possible lower-block difference; equal upper blocks delegate the decision to the lower block. This is an associative operation on the three comparison outcomes. A balanced binary tree of these combinations has $O(n)$ circuit size and $O(\log n)$ circuit depth for $n$-bit inputs.

For a block of $2^k$ bits, encode its count leading zeros result as a zero flag $z$ followed by $k$ low count bits $r$. An all-zero block has $(z,r)=(1,0)$; otherwise $z=0$. Two half-block encoders supply flags $z_H,z_L$ and low counts $h,\ell$. Combine them using $z=z_H\wedge z_L$, $r_{k-1}=z_H\wedge \neg z_L$, and $r_i=\mathrm{mux}(z_H,h_i,{\ell }_i)$ for $i<k-1$. A one-bit leaf has $z=\neg x$ and no low count bits. Checking whether the upper half is nonzero, only the lower half is nonzero, or both halves are zero proves the formula.

All count bits are selected in parallel, so $D(n)=D(n/2)+O(1)$ for circuit depth. The circuit size satisfies $S(n)=2S(n/2)+O(\log n)$; summing the work over levels gives $S(n)=O(n)$. Sharing the all-zero flags avoids a serial adder along the critical path.

A physical or idealized component implementing a fixed Boolean function on one or more input bits. For example, an AND gate outputs one exactly when both input bits are one. A Boolean circuit connects logic gates; circuit size counts components and circuit depth measures the longest chain of dependencies.

A selector that routes one of several inputs to its output according to control bits. The displayed two-input version selects $a$ when $s=0$ and $b$ when $s=1$. A word selector applies the same control bit to parallel one-bit multiplexers; its circuit size grows with the word width while its added circuit depth remains constant.

Use a Boolean circuit of unbounded-fan-in AND and OR gates, with negations pushed to the input Boolean literals. Its circuit depth is the largest number of AND/OR gates on an input-to-output path, and its circuit size $M$ counts these gates. Constants and Boolean literals may be supplied as inputs. Equivalent standard size conventions only enlarge the absolute constants. One can merge adjacent gates of the same type; the depth-reduction argument below keeps the two possible normal forms available at each gate.

A random restriction with parameter $p$ independently leaves each variable live with probability $p$ and otherwise fixes it to zero or one with probability $(1-p)/2$ each. The Håstad switching lemma states that for a width-$w$ DNF or conjunctive normal form $F$,Width bounds Boolean literals in a term or clause, not the number of terms. A decision tree of depth at most $s$ has both a DNF and a conjunctive normal form of width at most $s$ and has real multilinear degree at most $s$. Indeed every leaf condition is a product of at most $s$ factors $x_i$ or $1-x_i$; sum the accepting leaves. The switching lemma controls the canonical decision tree, hence implies this representation bound.

We detail the Boolean circuit simplification parameters. First use a $1/10$-random restriction. For a bottom AND gate, let $X$ count its live Boolean literals on the event that no fixed Boolean literal kills it. For $w$ distinct Boolean literals,Thus the probability of retaining more than $s$ live Boolean literals without becoming constant is at most $5^{-s}$. The same calculation applies to bottom OR gates, with the opposite killing value. Repeated Boolean literals are removed and contradictory Boolean literals make a constant gate. A union bound makes all nonconstant bottom gates width at most $s$, except with probability at most $M_0{5}^{-s}$.

Now apply $d-1$ successive restrictions, each retaining probability $1/(10s)$ of the remaining variables. At a two-layer gate, the current bottom forms are width-$s$ DNFs or conjunctive normal forms. The Håstad switching lemma bounds its probability of failing to reduce to decision-tree depth at most $s$ by $2^{-s}$. Convert the successful decision tree into the opposite normal form, whose terms or clauses have width at most $s$, and merge its outer gate with the adjacent gate of the same type. This removes one layer. Repeat upwards until the output has a depth-$s$ decision tree.

The bookkeeping matters: although a decision tree may give $2^s$ clauses, each subsequent switching event is charged to the corresponding original Boolean circuit gate, not to each newly created clause. The lemma permits any number of terms. Each original gate is charged once, so the sum of the failure probabilities is at most $M{2}^{-s}$, without an extra exponential size factor. Conditioning on successful preceding stages is harmless because each next restriction is fresh and the width bound holds for every preceding success. For a general Boolean circuit the conjunctive normal form or DNF representation at a shared gate can be chosen separately for each outgoing use; no extra gates need to be counted as switching targets.

The composed restriction has live-variable probabilityFixed values are still unbiased and coordinates independent. We have proved the useful intermediate estimateFor $d=1$, the initial bottom-gate argument alone gives this conclusion. This is a depth-reduction estimate, not the desired Fourier-tail theorem used as a black box.

Next derive exactly how restrictions affect the Fourier-Walsh transform. Let $J$ be the random live set and $a$ the fixed assignment outside $J$. With ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$, the restricted coefficient at $U\subset J$ isOrthogonality of the fixed-coordinate characters eliminates cross terms after averaging over $a$. Thereforeand then averaging over $J$ gives the expected Fourier weight after a random restriction identityThe original high-degree tail is not preserved: each original coefficient is weighted by a binomial distribution survival probability. On successful restrictions the left-hand tail vanishes; on failures it is at most one by Parseval's identity and $0\le f_{\rho }\le 1$. Hence its expectation is at most $M{2}^{-s}$.

Put $u=t^{1/d}$. If $u\ge 40$, choose $s=\lfloor u/40\rfloor \ge 1$ and the preceding value of $p$. For every $|S|>t$, the binomial distribution mean satisfiesIts variance is at most $\mu$. The Chebyshev inequality givesThus the exact expectation identity bounds at least half the original tail above $t$, andWhen $u<40$ the same bound follows from the trivial total-weight bound ${\sum }_S|\hat{f}(S){|}^2\le 1$. We obtain explicit absolute constants,This supplies the requested overview of the Linial-Mansour-Nisan theorem with the actual switching scale, gate-count bookkeeping and restriction-to-Fourier calculation. The argument uses the unbounded-fan-in AND/OR Boolean circuit basis; allowing arbitrary gates would make the theorem false, since one parity gate could have all its nonconstant Fourier weight at level $n$. The original theorem is Linial, Mansour and Nisan's circuit Fourier bound.

Apply comparator composition recursively in a balanced binary tree, with one-bit digital comparators at its leaves. For a power of two $n$, the circuit size and circuit depth satisfyThere are $n$ leaves and $n-1$ internal nodes, so the circuit size is $O(n)$ and the combinational delay is $O(\log n)$. Here each fixed-fan-in logic gate has bounded delay. For arbitrary $n$, pad both inputs with leading zero bits to the next power of two, which is less than $2n$; this preserves their unsigned interpretation and both bounds.