Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JOSHUA COOK:
All reports by Author Joshua Cook:

TR20-122 | 8th August 2020
Joshua Cook

Size Bounds on Low Depth Circuits for Promise Majority

Revisions: 2

We give two results on the size of AC0 circuits computing promise majority. $\epsilon$-promise majority is majority promised that either at most an $\epsilon$ fraction of the input bits are 1, or at most $\epsilon$ are 0.

First, we show super quadratic lower bounds on both monotone and general depth ... more >>>




ISSN 1433-8092 | Imprint