# Tag Info

22

Consider a fanin 2 circuit of $C$ depth $O(\log n)$. Divide the layers of $C$ into $O(\log n/\log\log n)$ blocks each of $\log\log n$ consecutive layers. We now wish to replace each block by a depth 2 circuit. Namely, each gate in the last layer of a block depends on at most $2^{\log\log n} = \log n$ gates of the last layer in the block below. We can thus ...

14

There are some relatively recent papers by Emanuele Viola et al., which deal with the complexity of sampling distributions. They focus on restricted model of computations, like bounded depth decision trees or bounded depth circuits. Unfortunately they don't discuss reversible gates. On the contrary there is often loss in the output length. Nevertheless ...

12

Short answer. For quantum circuits, there is at least one non-limitation result: arbitrary bounded-depth quantum circuits are unlikely to be simulatable with small multiplicative error in the probability of the outcome, even for polynomial-depth classical circuits. This, of course, does not tell you what resctrictions $\mathsf{QNC^0}$ circuits will ...

12

I apologize; I was too glib when I wrote that. While I believe it's possible to prove an oracle separation between $BQP$ and $BPP^{BQNC}$ using current techniques, it hasn't been done (12 years after I first thought about the problem, then put it off!), and would certainly be worth a paper for whoever did it. Maybe your post will help motivate me to ...

9

Kaveh's answer provides an answer do the question as you have stated it (and this is the usual proof for showing that $\mathsf{TC}^0$ is contained in $\mathsf{NC}^1$). But I was thinking that you might actually have intended to ask a slightly a different question. Namely for an explicit polynomial size monotone formula for majority. Since majority is ...

9

Computing restricted threshold gate ($\sum_i x_i \geq k$) is essentially sorting input bits. If you can sort the bits then it is easy to compare the result to $k$ and compute restricted threshold. On the other hand, assume that we have an circuits to compute restricted threshold. We can do a parallel search to find the number of ones in the input and ...

8

A paper of Klawe, Paul, Pippenger, and Yannakakis gives an hierarchy theorem for constant depth monotone formulas: http://dl.acm.org/citation.cfm?id=808717 Specifically, for every $k$ it gives a function that can be computed by a formula of depth $k$ and size $n$ but requires formulas of depth $k-1$ of size $\exp(n^{1/k})$.

7

The proof (due to Miller and Preparata, 1975) that any symmetric function can be computed by circuits over {AND,OR,NOT} in logarithmic depth can be found, e.g., in Complexity of Boolean Functions by Ingo Wegener (Theorem 4.1, page 76). The corresponding circuit has linear size. And since the depth is logarithmic it can be turned to a formula of polynomial ...

7

Raz and McKenzie, in Separation of the monotone NC hierarchy, show that the monotone NC hierarchy is strict, and separate monotone NC from monotone P.

3

Let $f\colon \{0,1\}^n \to \{0,1\}$, and let $g\colon \{0,1\}^n \to \{0,1\}$ be chosen uniformly. Then $\Pr[f=g] \sim 2^{-n}\mathrm{Bin}(2^n,1/2)$, and so a Chernoff bound shows that $$\Pr_g[\Pr[f=g] \geq \tfrac{1}{2}+\epsilon] \leq e^{-2\epsilon^2 2^n}.$$ Now suppose that $f$ goes over all $2^{O(n^2s)}$ circuits of size $s$. The probability that one of ...

2

There's the Minsky-Papert function, which is a depth-two formula, OR composed with AND, where the OR is of size $n^{1/3}$ and the AND is of size $n^{2/3}$. I.e., it's $OR_{n^{1/3}}\circ AND_{n^{2/3}}$. Then there's the particular communication complexity problem studied in the papers you linked, which is now a function of 2 $n$-bit strings $x$ and $y$, ...

2

First of all: your definition of $WCS[C_{t,d}]$ does not match the usual one. The common definition asks for a satisfying assignment of Hamming weight exactly $k$, rather than at most $k$, and this can make an important difference. However, regardless of whether you want at most, or exactly, Hamming weight $k$, the weighted circuit-sat problem for constant-...

2

There are two way to see your question : Is unbounded fanout a reasonable approximation for realistic (quantum) circuits ? Is there a realistic quantum architecture which is effectively equivalent to the quantum circuit with unbounded fan-out ? Peter Shor essentially suggested the formulation 1. in his comment above, and I’ll let experimentalists answer ...

Only top voted, non community-wiki answers of a minimum length are eligible