<p>After discussing in the comments, I think a clearer definition of the question is as follows: for a random function <span class="math-container">$f : \{0, 1\}^n \rightarrow \{0, 1\}$</span>, what is the probability that there exists a non-injective function <span class="math-container">$g : \{0, 1\}^n \rightarrow \{0, 1\}^m$</span> defined by <span class="math-container">$m$</span> conjunctions on <span class="math-container">$2$</span> variables, with arbitrary negations, such that <span class="math-container">$\forall x, y \in \{0, 1\}^n, g(x) = g(y) \Rightarrow f(x) = f(y)$</span> with <span class="math-container">$g$</span>?</p>
<p>Here is the former description for context:</p>
<p>Here, consider circuits to have <span class="math-container">$AND$</span> and <span class="math-container">$OR$</span> gates with fan-in <span class="math-container">$2$</span>, with negations optionally present at any input to a gate, and to be alternating and synchronous (<a href="https://www.ams.org/journals/proc/1977-064-02/S0002-9939-1977-0456962-7/S0002-9939-1977-0456962-7.pdf" rel="nofollow noreferrer">Harper 1977</a>), the latter meaning that there are layers such that layer <span class="math-container">$1$</span> only accesses the inputs, layer <span class="math-container">$2$</span> only accesses layer <span class="math-container">$1$</span>, and so on, and the former meaning that each layer has exclusively <span class="math-container">$AND$</span>s or <span class="math-container">$OR$</span>s, which one alternating layer by layer. For any function <span class="math-container">$f : \{0, 1\}^n \rightarrow \{0, 1\}$</span>, we can then consider an arbitrary circuit <span class="math-container">$C$</span> which computes it, and &quot;chop off&quot; everything above the first layer. Doing so, if that layer had <span class="math-container">$w$</span> gates (width <span class="math-container">$w$</span>), we get new, multi-output circuit which computes a function <span class="math-container">$g_C : \{0, 1\}^n \rightarrow \{0, 1\}^w$</span>.</p>
<p>My question is: for uniformly random <span class="math-container">$f$</span>, what is the probability that there exists such a <span class="math-container">$C$</span> which compute <span class="math-container">$f$</span> such that <span class="math-container">$g_C$</span> is not injective?</p>

CC BY-SA 4.0
2021-11-18T08:51:27.987Z
Your description of the circuit model appears incomplete. As written, the circuits are monotone, hence a random Boolean function cannot be computed in this model at all, with overwhelming probability.
Emil Jeřábek
CC BY-SA 4.0
2021-11-18T18:58:39.733Z
I made it explicit, though maybe there is a way to more concisely state it with a common name for the basis with ANDs, ORs with arbitrary negations?
Samuel Schlesinger
CC BY-SA 4.0
2021-11-18T19:04:01.470Z
If you have negations for free anywhere, then what’s the point of making the layers alternating? You can turn any AND into an OR by negating all its input and output wires, and vice versa.
Emil Jeřábek
CC BY-SA 4.0
2021-11-18T19:05:35.847Z
Yes, good point. Is the typical way to push the negations to the bottom and make it alternating?
Samuel Schlesinger
CC BY-SA 4.0
2021-11-18T19:06:09.067Z
Actually, for this case it doesn't matter.
Samuel Schlesinger
CC BY-SA 4.0
2021-11-18T19:07:53.487Z
I just care about the existence of $m$ width 2 conjunctions (possibly containing negations) computing a non-injective function $g : \{0, 1\}^n \rightarrow \{0, 1\}^m$ such that $\forall x, y, g(x) = g(y) \Rightarrow f(x) = f(y)$.
Samuel Schlesinger
CC BY-SA 4.0
2021-11-18T19:08:34.573Z
I think the circuit model is a bit of a diversion from that, which I should have left out.
Samuel Schlesinger
CC BY-SA 4.0
2021-11-18T20:11:54.530Z
I agree that the circuits are an unnecessary distraction. The question as written in your last but one comment is much easier to grasp.
Emil Jeřábek
CC BY-SA 4.0
2021-11-18T20:28:12.423Z
Thanks for the help, I will try to edit the question to clarify.
Samuel Schlesinger
CC BY-SA 4.0
2021-11-20T03:50:59.697Z
What do you mean by a "function defined by $m$ conjunctions"?  Are you talking about a formula in DNF form, with $m$ clauses?
D.W.
CC BY-SA 4.0
2021-11-20T16:44:11.483Z
I am referring to a function $g : \{0, 1\}^n \rightarrow \{0,1\}^m$ such that, for instance, $g_i(x) = x_4 \wedge \neg x_6$, but generally, each $g_i(x)$ can be computed by a conjunction on two input bits.
Samuel Schlesinger
CC BY-SA 4.0
2021-11-20T16:47:15.437Z
It is similar to a DNF, but we cut off the disjunction at the top.
Samuel Schlesinger
CC BY-SA 4.0
2021-11-21T05:20:57.360Z
So, for the case of $m = 1$, we can note that the probability is vanishingly small that the function is only sensitive to any two variables. We can make basically this argument up to $m < n/2$, as $n/2$ is the point where we can actually be referencing the variables. After this, we can see that if we could make a circuit with first layer of size $m < n$ w.h.p., then we can make far more efficient circuits than is possible. Once $m \geq n$, this becomes harder for me to reason about, so that’s where I currently am.
Samuel Schlesinger
CC BY-SA 4.0
2021-11-21T06:26:29.367Z
I think that by a more explicit argument, you can get a bound of $\frac{2{n \choose 2}}{2^{n-2}}$ for the $m=1$ case by a union bound over all possible 2-bit conjunctions.
Samuel Schlesinger
CC BY-SA 4.0
2021-11-21T06:45:35.850Z
And, to be clear, the fact that they’re conjunctions rather than disjunctions does not matter in this case, but is meant to simplify the question. We can always replace a conjunction by a disjunction by negating it’s inputs and vice versa, and the resulting function will still satisfy our property or not.
Samuel Schlesinger
<circuit-complexity><boolean-functions><boolean-formulas><circuits><circuit-depth>
Do random functions have synchronous, alternating circuits with non-injective first layers?
Samuel Schlesinger
# Do random functions have synchronous, alternating circuits with non-injective first layers?

(Asked by: username_0 on 2021-11-18)

After discussing in the comments, I think a clearer definition of the question is as follows: for a random function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, what is the probability that there exists a non-injective function $g : \{0, 1\}^n \rightarrow \{0, 1\}^m$ defined by $m$ conjunctions on $2$ variables, with arbitrary negations, such that $\forall x, y \in \{0, 1\}^n, g(x) = g(y) \Rightarrow f(x) = f(y)$ with $g$?

Here is the former description for context:

Here, consider circuits to have $AND$ and $OR$ gates with fan-in $2$, with negations optionally present at any input to a gate, and to be alternating and synchronous ([Harper 1977](https://www.ams.org/journals/proc/1977-064-02/S0002-9939-1977-0456962-7/S0002-9939-1977-0456962-7.pdf)), the latter meaning that there are layers such that layer $1$ only accesses the inputs, layer $2$ only accesses layer $1$, and so on, and the former meaning that each layer has exclusively $AND$s or $OR$s, which one alternating layer by layer. For any function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, we can then consider an arbitrary circuit $C$ which computes it, and "chop off" everything above the first layer. Doing so, if that layer had $w$ gates (width $w$), we get new, multi-output circuit which computes a function $g\_C : \{0, 1\}^n \rightarrow \{0, 1\}^w$.

My question is: for uniformly random $f$, what is the probability that there exists such a $C$ which compute $f$ such that $g\_C$ is not injective?

**Tags:** circuit-complexity, boolean-functions, boolean-formulas, circuits, circuit-depth

> **Comments:**
> **username_1**: Your description of the circuit model appears incomplete. As written, the circuits are monotone, hence a random Boolean function cannot be computed in this model at all, with overwhelming probability.  
> **username_0**: I made it explicit, though maybe there is a way to more concisely state it with a common name for the basis with ANDs, ORs with arbitrary negations?  
> **username_1**: If you have negations for free anywhere, then what’s the point of making the layers alternating? You can turn any AND into an OR by negating all its input and output wires, and vice versa.  
> **username_0**: Yes, good point. Is the typical way to push the negations to the bottom and make it alternating?  
> **username_0**: Actually, for this case it doesn't matter.  
> **username_0**: I just care about the existence of $m$ width 2 conjunctions (possibly containing negations) computing a non-injective function $g : \{0, 1\}^n \rightarrow \{0, 1\}^m$ such that $\forall x, y, g(x) = g(y) \Rightarrow f(x) = f(y)$.  
> **username_0**: I think the circuit model is a bit of a diversion from that, which I should have left out.  
> **username_1**: I agree that the circuits are an unnecessary distraction. The question as written in your last but one comment is much easier to grasp.  
> **username_0**: Thanks for the help, I will try to edit the question to clarify.  
> **username_2**: What do you mean by a "function defined by $m$ conjunctions"?  Are you talking about a formula in DNF form, with $m$ clauses?  
> **username_0**: I am referring to a function $g : \{0, 1\}^n \rightarrow \{0,1\}^m$ such that, for instance, $g_i(x) = x_4 \wedge \neg x_6$, but generally, each $g_i(x)$ can be computed by a conjunction on two input bits.  
> **username_0**: It is similar to a DNF, but we cut off the disjunction at the top.  
> **username_0**: So, for the case of $m = 1$, we can note that the probability is vanishingly small that the function is only sensitive to any two variables. We can make basically this argument up to $m < n/2$, as $n/2$ is the point where we can actually be referencing the variables. After this, we can see that if we could make a circuit with first layer of size $m < n$ w.h.p., then we can make far more efficient circuits than is possible. Once $m \geq n$, this becomes harder for me to reason about, so that’s where I currently am.  
> **username_0**: I think that by a more explicit argument, you can get a bound of $\frac{2{n \choose 2}}{2^{n-2}}$ for the $m=1$ case by a union bound over all possible 2-bit conjunctions.  
> **username_0**: And, to be clear, the fact that they’re conjunctions rather than disjunctions does not matter in this case, but is meant to simplify the question. We can always replace a conjunction by a disjunction by negating it’s inputs and vice versa, and the resulting function will still satisfy our property or not.  

---

## 0 answers

