Andreev's function reads a bit from a truth table at an address given by the parities of blocks of input bits. Kane and Williams used it for the first superlinear gate lower bounds against depth-two threshold circuits and asked for tight bounds. We improve the bounds by showing
(1) an ... more >>>