Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SIGN-COHERENT THRESHOLD CIRCUITS:
Reports tagged with sign-coherent threshold circuits:
TR26-330 | 20th November 2026
Christian Reitwießner

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

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 >>>




ISSN 1433-8092 | Imprint