Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Promise Majority:
TR19-133 | 2nd October 2019
Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi

More on $AC^0[\oplus]$ and Variants of the Majority Function

Revisions: 1

In this paper we prove two results about $AC^0[\oplus]$ circuits.

We show that for $d(N) = o(\sqrt{\log N/\log \log N})$ and $N \leq s(N) \leq 2^{dN^{1/d^2}}$ there is an explicit family of functions $\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$ such that
$f_N$ has uniform $AC^0$ formulas of depth $d$ and size at ... more >>>

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