Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > WORST CASE:
Reports tagged with worst case:
TR16-158 | 9th October 2016
We study the following computational problem: for which values of $k$, the majority of $n$ bits $\text{MAJ}_n$ can be computed with a depth two formula whose each gate computes a majority function of at most $k$ bits? The corresponding computational model is denoted by $\text{MAJ}_k \circ \text{MAJ}_k$. We observe that ... more >>>