1
$\begingroup$

A boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ is symmetric if $f(x)$ depends only on the number of $1$s in $x$. It is known that every boolean function is in $\mathrm{NC}^1$, i.e. there is a circuit of depth $O(\log n)$ computing it.

What is known about the constant inside the $O()$ notation? Specifically, can one construct, for every $c$, a symmetric function requiring a circuit of depth at least $c \log n$? Or there is some constant $c_0$ such that every symmetric function has a circuit of depth at most $c_0\log n$?

$\endgroup$
1
$\begingroup$

We can treat the input $x$ as a boolean array. Using an $O(\log n)$ depth sorting network (such as the AKS network), we can sort $x$ in nonincreasing order. Calling the result $y$, using $O(1)$ more depth we can compute $z_i = y_i \land \lnot y_{i+1}$ (extended in the right way to the boundary). The vector $z_0,\ldots,z_n$ is the indicator vector of the Hamming weight of $x$. At this point you can compute any symmetric function using $O(\log n)$ more depth.

This shows that there is a universal constant $C$ such that all symmetric functions can be computed in depth $C\log n$ using constant fan-in circuits.

$\endgroup$
5
  • $\begingroup$ Thanks! Is the constant known? Is there an explicit symmetric function with a matching lower bound? $\endgroup$ – Larry a. Jan 23 at 16:32
  • $\begingroup$ Probably not. In complexity theory we typically don't care about constant factors. Lower bounds which are tight up to lower order factors are sometimes known (for example, formula complexity of parity), but this is uncommon. $\endgroup$ – Yuval Filmus Jan 23 at 16:34
  • $\begingroup$ For a different construction, see this paper. $\endgroup$ – Yuval Filmus Jan 23 at 16:35
  • $\begingroup$ Since this question is about bounded fan-in ($\mathrm{NC}^1$) circuits, the last step in your construction needs depth $\log n$ rather than $O(1)$. $\endgroup$ – Emil Jeřábek Jan 24 at 10:53
  • $\begingroup$ Right, thanks for the correction. $\endgroup$ – Yuval Filmus Jan 24 at 10:54
1
$\begingroup$

Fix a circuit of depth $c\log n$ computing the majority function $\def\M{\mathrm{Maj}}\M_{2n+1}\colon\{0,1\}^{2n+1}\to\{0,1\}$. (For example, the construction of Valiant gives $c<5{.}3$.) Then for any $k\le n+1$, the threshold function $$\theta^n_k(x_0,\dots,x_{n-1})=\begin{cases}1&\bigl|\{i<n:x_i=1\}\bigr|\ge k\\0&\text{otherwise}\end{cases}$$ can be defined by the circuit $$\M_{2n+1}(x_0,\dots,x_{n-1},\underbrace{0,\dots,0}_{k},\underbrace{1,\dots,1}_{n+1-k})$$ of depth $c\log n$, and an arbitrary symmetric function $f\colon\{0,1\}^n\to\{0,1\}$ can be written as $$f(\vec x)=\bigvee_{k\in I}\bigl(\theta^n_k(\vec x)\land\neg\theta^n_{k+1}(\vec x)\bigr)$$ for some $I\subseteq\{0,\dots,n\}$. Arranging the large $\bigvee$ as a balanced binary tree of disjunctions, this gives a circuit of depth at most $(c+1)\log n+2$. (E.g., using Valiant’s construction, every symmetric function has a circuit of depth $<6{.}3\log n$.)


Concerning lower bounds, the only applicable lower bound I am aware of is that formulas over the De Morgan basis $\{\land,\lor,\neg,0,1\}$ computing Parity need size $\Omega(n^2)$, which implies that any De Morgan circuit for Parity has depth $\ge2\log n$ up to an additive constant. (This bound is tight for Parity, but presumably not for all symmetric functions.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.