11

This version of the answer incorporates feedback from Emil Jeřábek. As far as I can see, the main twist is that there is a language in $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ of exponential circuit complexity. In particular, fix a binary encoding of boolean circuits and define $L$ as the language defined by $L_n$ is not decided by any circuit of size $2^{n/2}$,...


10

I'd consider it unlikely that such a trick is easy to find and/or will give you significant gains, as it would give nontrivial satisfiability algorithms. Here's how: First of all, while ostensibly easier, your problem can actually solve the more general problem of, given a circuit $C$ and $N$ inputs $x_0, \ldots, x_{N-1}$, evaluate $C$ at all the inputs ...


8

The class of functions computable by formulas of polynomial size is equivalent to the (nonuniform) class $\mathsf{NC}^1$ of functions computable by (bounded fanin/fanout) circuits of logarithmic depth. Proving the two implications is a nice exercise. In one direction, you can recursively "untangle" each level of a circuit by creating copies of gates. This ...


7

As far as I know, three classes of layered circuits have been studied. In all of these definitions arcs are allowed only between two adjacent layers. A circuit is called synchronous (Harper 1977) if all gates are arranged into layers, and inputs must be at the layer 0. (An equivalent definition: for any gate $g$, all paths from the inputs to $g$ have the ...


7

As Sasho suggested, I am putting my comment as an answer. The separations between monotone versions of $\mathsf{NC}^1/\mathsf{poly}$ and $\mathsf{P/poly}$ versions of complexity are long known (Karchmer-Wigderson, Grigni-Sipser, etc), but in the non-monotone world almost nothing was known. Fortunately, Ben Rossman has recently found the first separation of ...


4

In the general case, your problem is NP-hard, if you are working over a finite field (say, the integers modulo $p$). It is easy to see that the language of such circuits that are not identically zero is in NP (if it isn't identically zero, there exists a witness: an input that makes its output non-zero). Also, we can reduce SAT to this problem. Consider a ...


4

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

I'm not sure if this is the generalization you have in mind, but a natural one is, if $p_x := \Pr[f(x) = 1]$, \begin{align} s(f,x) &= \sum_{y\in N(x)} D_{TV}(p_x,p_y) \\ &= \sum_{y\in N(x)} |p_x - p_y| \end{align} where $D_{TV}$ is total variation distance.


2

This should work fine inasmuch as if $f$ is now a random function, then you just get the expected sensitivity: $$\mathbb E s(f, x) = \sum_{y \in N(x)} \mathbb E I(f(x) \neq f(y)) = \sum_{y \in N(x)} \Pr(f(x) \neq f(y)).$$


2

In the same paper that shows the $n^{1.5}$ lower bound for depth-2 (Daniel Kane and me) we also show that a random function is extremely likely to have depth 2 threshold circuit complexity at least $$2^n/n^3$$. So the answer to question 2 is "yes" Since random functions need large threshold circuits, question 1 seems to be effectively asking "does $P \neq ...


2

Not really an answer, but would've been too long a comment. The result of Ben-Or and Cleve that arithmetic formulas can be simulated by branching programs of width 3, works over arbitrary non-commutative rings (in particular over the matrix ring $M_n(F)$). A nice consequence of this is that $\# NC^1$ circuits over $M_n(\mathbb{Z})$ captures ${\text{GapL}}$ ...


2

I believe this is generally done in MPC by converting the sharing of the field element to some sharing more amenable to comparison. See this (section 6.3), or chapter 9 in Secure Multiparty Computation and Secret Sharing by Cramer et al. Generically, comparisons are dependent on how you represent values in $\mathbb{F}_p$. For example, in $\mathbb{F}_3$ you ...


1

For 3 inputs it's not $2^3$ functions but $2^{2^3}$ functions. Circuit minimization is generally hard. You could try using the aiger package http://fmv.jku.at/aiger/, which will give you a circuit but not necessarily minimal.


1

I have found some hints on my question in Moshe Looks, Competent Program Evolution, p. 31: Most local perturbations of large random formulae have no effect – 96% of them for arity five, and 91% for arity ten (the drop is a corollary of the increase in the percentage of unique behaviors in a fixed size sample as the arity increase). This is a consequence of ...


1

Don't forget that even though the fan-in is unbounded, the number of gates is polynomially bounded in the number of variables $n$ (in the definition of $\mathsf{AC}$ for instance) .


1

Even though I agree that this is not the right place to ask this question, you might want to look into the following book that contains everything about branching programs that you every wanted to know: Ingo Wegener: Branching Programs and Binary Decision Diagrams. SIAM 2000, ISBN 0-89871-458-3


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