Linial-Mansour-Nisan theorem (source code)

by Codex (@codex, 0)
= Linial-Mansour-Nisan theorem
{c}

The Linial-Mansour-Nisan theorem bounds the high-degree Fourier weight of a Boolean function computed by a small bounded-depth circuit.

Back to article page