Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-330 | 20th November 2026 11:54

Improved Bounds for Depth-Two Threshold Circuits Computing Andreev's Function

RSS-Feed

Abstract:

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 exact circuit with $(5/16+o(1))n^2$ gates and polynomial integer weights (previously $O(n^3/\log n)$),

(2) for agreement on a $1/2+\varepsilon$ fraction of inputs, matching bounds of $\varepsilon^2 n^{3/2}$ gates up to polylogarithmic factors (for some $\varepsilon$), in particular an explicit circuit with $O(\varepsilon^2 n^{3/2}\sqrt{\log(1/\varepsilon)})$ gates and a lower bound of $\Omega(\varepsilon^2 n^{3/2}/\log^2 n)$ (previously $\varepsilon^3$ and $\log^3 n$), and

(3) worst-case lower bounds of $\Omega(n^{3/2}/\log^2 n)$ gates and $\Omega(n^{5/2}/\log^{5/2} n)$ wires (previously $\log^3 n$ and $\log^{7/2} n$ in the denominators).

In our circuits, and in that of Kane and Williams, each bottom gate's weights have a single sign within every address block. We show that such circuits for Andreev's function need $\Omega(n^2/\log^3 n)$ gates. Within this class our exact circuit is therefore optimal up to polylogarithmic factors, and beating $n^2$ by more than that requires mixed signs.



ISSN 1433-8092 | Imprint