Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROMISE MAJORITY:
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 >>>

ISSN 1433-8092 | Imprint