<p>Edit: Oops, my intuition was wrong here! You can even get a deterministic algorithm from Emil's argument, by following Lemma 6.1 from Chen, Jin and myself (STOC 2020). That is, given any set P and N you can construct a circuit of size O(n log n) as desired in deterministic polynomial time.</p>

CC BY-SA 4.0
2021-01-01T21:43:10.453Z
2021-01-03T12:16:56.030Z
2021-01-03T12:16:56.030Z
Ryan Williams
<p>Yes, any such pair can be separated by a formula of size <span class="math-container">$O(n)$</span>. More generally, any disjoint pair <span class="math-container">$P,N\subseteq\{0,1\}^n$</span> of size <span class="math-container">$s=|P|+|N|$</span> can be separated by a <em>decision tree</em> of size <span class="math-container">$O(s)$</span>, which can be implemented as an <span class="math-container">$O(s)$</span>-size formula by replacing each query node with <span class="math-container">$(p\land\cdots)\lor(\neg p\land\cdots)$</span>.</p>
<p>It suffices to observe that there exists a decision tree such that every path to a leaf is consistent with exactly one element of <span class="math-container">$P\cup N$</span> (which means that it has <span class="math-container">$s$</span> leaves and <span class="math-container">$s-1$</span> inner nodes). One way to show this is to consider the full binary tree of height <span class="math-container">$n$</span> that queries all variables along every path, take its subtree consisting of the union of paths to leaves in <span class="math-container">$P\cup N$</span>, and eliminate inner nodes that do not branch.</p>
<p>Another way is to build it inductively. Start with the trivial one-element decision tree, and repeat: pick a leaf <span class="math-container">$x$</span> that is consistent with <span class="math-container">$\ge2$</span> elements of <span class="math-container">$P\cup N$</span>, and make <span class="math-container">$x$</span> into a query node for some variable <span class="math-container">$p$</span> such that each of the <span class="math-container">$p$</span> and <span class="math-container">$\neg p$</span> branches is still consistent with an element of <span class="math-container">$P\cup N$</span>. Notice that this actually gives a polynomial-time algorithm to construct the decision tree, given <span class="math-container">$P$</span> and <span class="math-container">$N$</span>.</p>
<p>[The first version of this answer presented a different construction, using a linear hash function <span class="math-container">$h\colon\mathbb F_2^n\to\mathbb F_2^{O(\log s)}$</span> such that <span class="math-container">$h(P)\cap h(N)=\varnothing$</span>. This only gives a separating circuit of size <span class="math-container">$O(n\log n)$</span>, or <span class="math-container">$O((n+s_0)\log s)$</span> in the general case, where <span class="math-container">$s_0=\min\{|P|,|N|\}$</span>.]</p>
<p>For <span class="math-container">$s\le n$</span>, the <span class="math-container">$O(s)$</span> bound is optimal up to a multiplicative constant: it is easy to see that any circuit separating <span class="math-container">$P=\{0^n\}$</span> from <span class="math-container">$N=\{0^i10^{n-1-i}:i&lt;s-1\}$</span> must
include all of the first <span class="math-container">$s-1$</span> variables, and as such it has size at least <span class="math-container">$s$</span>.</p>
<p>For larger <span class="math-container">$s$</span>, an optimal bound is given by Theorem 1.1 of Andreev, Clementi, and Rolim [1] (with <span class="math-container">$\varepsilon=1/2$</span>): the maximum circuit size required to separate <span class="math-container">$P,N\subseteq\{0,1\}^n$</span> with <span class="math-container">$|P|+|N|=s$</span> is
<span class="math-container">$$\Theta\left(\frac s{\log s}\right)+O(n).$$</span>
They do not seem to particularly care about the case of small <span class="math-container">$s$</span>, but combined with the discussion above, we obtain the following complete characterization:</p>
<blockquote>
<p><strong>Theorem:</strong> The maximum circuit size required to separate disjoint pairs <span class="math-container">$P,N\subseteq\{0,1\}^n$</span> with <span class="math-container">$|P|+|N|=s$</span> is
<span class="math-container">$$\begin{cases}\Theta\left(\frac s{\log s}\right)&amp;\text{if }n\log n\le s,\\
\Theta(n)&amp;\text{if }n\le s\le n\log n,\\
\Theta(s)&amp;\text{if }s\le n.\end{cases}$$</span></p>
</blockquote>
<p>And while it does not yield improvement on any of the above, let me mention the following fun fact: for every nonempty <span class="math-container">$X\subseteq\{0,1\}^n$</span> of size <span class="math-container">$s=|X|$</span>, there exists <span class="math-container">$I\subseteq[n]$</span> of size <span class="math-container">$|I|&lt;s$</span> such that the restrictions <span class="math-container">$x\restriction I\in\{0,1\}^I$</span> of the elements <span class="math-container">$x\in X$</span> are pairwise distinct. To see this, fix <span class="math-container">$I$</span> of minimal size with this separation property. For each <span class="math-container">$i\in I$</span>, the minimality of <span class="math-container">$I$</span> implies that there exist <span class="math-container">$x_i,y_i\in X$</span> such that <span class="math-container">$x_i\restriction I$</span> and <span class="math-container">$y_i\restriction I$</span> differ only at the <span class="math-container">$i$</span>-th position. Put <span class="math-container">$E=\{\{x_i,y_i\}:i\in I\}$</span>. Then <span class="math-container">$(X,E)$</span> is a graph with <span class="math-container">$s$</span> vertices and <span class="math-container">$|I|$</span> edges, and it is <em>acyclic</em> (if we start from a <span class="math-container">$\{0,1\}$</span> vector, and flip a sequence of distinct bits, we cannot arrive where we started from). Thus, <span class="math-container">$s&gt;|I|$</span>.</p>
<p><strong>Reference:</strong></p>
<p>[1] Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim: <em>Optimal bounds for the approximation of boolean functions and some applications</em>, Theoretical Computer Science 180 (1997), no. 1–2, pp. 243–268, doi: <a href="https://doi.org/10.1016/S0304-3975(96)00217-4" rel="noreferrer">10.1016/S0304-3975(96)00217-4</a>.</p>

CC BY-SA 4.0
2021-01-09T18:33:44.777Z
This sounds like a circuit of size O(s), but not a formula.
mic
CC BY-SA 4.0
2021-01-09T19:21:12.410Z
@mic What makes you say that? The decision tree is a *tree*, and the given translation to formulas preserves that.
Emil Jeřábek
CC BY-SA 4.0
2021-01-09T20:36:15.987Z
Note that I’m *not* translating the decision tree by a disjunction of accepting paths (that would indeed either require a circuit, or blow up the size by a factor of $n$).
Emil Jeřábek
CC BY-SA 4.0
2021-01-02T09:54:56.353Z
2021-01-03T14:59:02.790Z
2021-01-03T14:59:02.790Z
Emil Jeřábek
<p>We say that a pair <span class="math-container">$(P,N)$</span> of subsets of strings from <span class="math-container">$\{0,1\}^n$</span> is an <span class="math-container">$n$</span>-pair if <span class="math-container">$|P|=|N|=n$</span>. Intuitively, sucha a pair consists of a set <span class="math-container">$P$</span> with <span class="math-container">$n$</span> positive <span class="math-container">$n$</span>-bit strings, and a set <span class="math-container">$N$</span> with <span class="math-container">$n$</span> negative <span class="math-container">$n$</span>-bit strings. We say that a circuit <span class="math-container">$C$</span> separates <span class="math-container">$(P,N)$</span> if <span class="math-container">$C$</span> accepts all strings in <span class="math-container">$P$</span> and rejects all strings in <span class="math-container">$N$</span>.</p>
<p>I'm looking for any non-trivial lower bound for the size of circuits/formulas separating <span class="math-container">$n$</span>-pairs.</p>
<ul>
<li><strong>Question:</strong> Is it the case that every <span class="math-container">$n$</span>-pair <span class="math-container">$(P,N)$</span> can be separated by a circuit/formula with <span class="math-container">$O(n)$</span> gates?</li>
</ul>
<p>Note that each such pair can be trivially separated by a circuit/formula with <span class="math-container">$O(n^2)$</span> gates: given an input <span class="math-container">$w\in \{0,1\}^n$</span>, the circuit/formula simply runs through each string <span class="math-container">$u$</span> in <span class="math-container">$P$</span> and tests whether <span class="math-container">$w$</span> is equal to <span class="math-container">$u$</span>. It accepts if and only if it finds a <span class="math-container">$u$</span> that is equal to <span class="math-container">$w$</span>.</p>
<p>On the other hand, I could not find an argument that implies that a super-linear number of gates is necessary.</p>
<p>Since this type of question seems to be well studied in by the machine learning community I was wondering if anyone could point me to some reference about lower bounds for separation problems as above?</p>

CC BY-SA 4.0
2021-01-02T19:02:47.047Z
@1.. Strings in P are dogs, strings in N are cats, and you want to compute the smallest circuit that always answers yes for dogs and no for cats. Obs: not talking about the ability of the circuit to predict the correct answer on new data. This will probably be very bad due to overfitting. This type of question is also studied in the field of learning automata (instead of circuits you want the finite automaton separating P and N). Just search for "learning from positive and negative data" and there will be plenty of entries.
verifying
<circuit-complexity><machine-learning>
Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings
verifying
# Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings

(Asked by: username_0 on 2021-01-01)

We say that a pair $(P,N)$ of subsets of strings from $\{0,1\}^n$ is an $n$-pair if $|P|=|N|=n$. Intuitively, sucha a pair consists of a set $P$ with $n$ positive $n$-bit strings, and a set $N$ with $n$ negative $n$-bit strings. We say that a circuit $C$ separates $(P,N)$ if $C$ accepts all strings in $P$ and rejects all strings in $N$.

I'm looking for any non-trivial lower bound for the size of circuits/formulas separating $n$-pairs.

* **Question:** Is it the case that every $n$-pair $(P,N)$ can be separated by a circuit/formula with $O(n)$ gates?

Note that each such pair can be trivially separated by a circuit/formula with $O(n^2)$ gates: given an input $w\in \{0,1\}^n$, the circuit/formula simply runs through each string $u$ in $P$ and tests whether $w$ is equal to $u$. It accepts if and only if it finds a $u$ that is equal to $w$.

On the other hand, I could not find an argument that implies that a super-linear number of gates is necessary.

Since this type of question seems to be well studied in by the machine learning community I was wondering if anyone could point me to some reference about lower bounds for separation problems as above?

**Tags:** circuit-complexity, machine-learning
> **Comments:**
> **username_0**: @1.. Strings in P are dogs, strings in N are cats, and you want to compute the smallest circuit that always answers yes for dogs and no for cats. Obs: not talking about the ability of the circuit to predict the correct answer on new data. This will probably be very bad due to overfitting. This type of question is also studied in the field of learning automata (instead of circuits you want the finite automaton separating P and N). Just search for "learning from positive and negative data" and there will be plenty of entries.  

---

## 2 answers

### Answer by username_2 on 2021-01-02. Score: 15 | Accepted answer

Yes, any such pair can be separated by a formula of size $O(n)$. More generally, any disjoint pair $P,N\subseteq\{0,1\}^n$ of size $s=|P|+|N|$ can be separated by a *decision tree* of size $O(s)$, which can be implemented as an $O(s)$-size formula by replacing each query node with $(p\land\cdots)\lor(\neg p\land\cdots)$.

It suffices to observe that there exists a decision tree such that every path to a leaf is consistent with exactly one element of $P\cup N$ (which means that it has $s$ leaves and $s-1$ inner nodes). One way to show this is to consider the full binary tree of height $n$ that queries all variables along every path, take its subtree consisting of the union of paths to leaves in $P\cup N$, and eliminate inner nodes that do not branch.

Another way is to build it inductively. Start with the trivial one-element decision tree, and repeat: pick a leaf $x$ that is consistent with $\ge2$ elements of $P\cup N$, and make $x$ into a query node for some variable $p$ such that each of the $p$ and $\neg p$ branches is still consistent with an element of $P\cup N$. Notice that this actually gives a polynomial-time algorithm to construct the decision tree, given $P$ and $N$.

[The first version of this answer presented a different construction, using a linear hash function $h\colon\mathbb F\_2^n\to\mathbb F\_2^{O(\log s)}$ such that $h(P)\cap h(N)=\varnothing$. This only gives a separating circuit of size $O(n\log n)$, or $O((n+s\_0)\log s)$ in the general case, where $s\_0=\min\{|P|,|N|\}$.]

For $s\le n$, the $O(s)$ bound is optimal up to a multiplicative constant: it is easy to see that any circuit separating $P=\{0^n\}$ from $N=\{0^i10^{n-1-i}:i must
include all of the first $s-1$ variables, and as such it has size at least $s$.

For larger $s$, an optimal bound is given by Theorem 1.1 of Andreev, Clementi, and Rolim [1] (with $\varepsilon=1/2$): the maximum circuit size required to separate $P,N\subseteq\{0,1\}^n$ with $|P|+|N|=s$ is
$$\Theta\left(\frac s{\log s}\right)+O(n).$$
They do not seem to particularly care about the case of small $s$, but combined with the discussion above, we obtain the following complete characterization:

> **Theorem:** The maximum circuit size required to separate disjoint pairs $P,N\subseteq\{0,1\}^n$ with $|P|+|N|=s$ is
> $$\begin{cases}\Theta\left(\frac s{\log s}\right)&\text{if }n\log n\le s,\\
> \Theta(n)&\text{if }n\le s\le n\log n,\\
> \Theta(s)&\text{if }s\le n.\end{cases}$$

And while it does not yield improvement on any of the above, let me mention the following fun fact: for every nonempty $X\subseteq\{0,1\}^n$ of size $s=|X|$, there exists $I\subseteq[n]$ of size $|I| such that the restrictions $x\restriction I\in\{0,1\}^I$ of the elements $x\in X$ are pairwise distinct. To see this, fix $I$ of minimal size with this separation property. For each $i\in I$, the minimality of $I$ implies that there exist $x\_i,y\_i\in X$ such that $x\_i\restriction I$ and $y\_i\restriction I$ differ only at the $i$-th position. Put $E=\{\{x\_i,y\_i\}:i\in I\}$. Then $(X,E)$ is a graph with $s$ vertices and $|I|$ edges, and it is *acyclic* (if we start from a $\{0,1\}$ vector, and flip a sequence of distinct bits, we cannot arrive where we started from). Thus, $s>|I|$.

**Reference:**

[1] Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim: *Optimal bounds for the approximation of boolean functions and some applications*, Theoretical Computer Science 180 (1997), no. 1–2, pp. 243–268, doi: [10.1016/S0304-3975(96)00217-4](https://doi.org/10.1016/S0304-3975(96)00217-4).

> **Comments:**
> **username_3**: This sounds like a circuit of size O(s), but not a formula.  
> **username_2**: @mic What makes you say that? The decision tree is a *tree*, and the given translation to formulas preserves that.  
> **username_2**: Note that I’m *not* translating the decision tree by a disjunction of accepting paths (that would indeed either require a circuit, or blow up the size by a factor of $n$).  

---

### Answer by username_1 on 2021-01-01. Score: 3

Edit: Oops, my intuition was wrong here! You can even get a deterministic algorithm from Emil's argument, by following Lemma 6.1 from Chen, Jin and myself (STOC 2020). That is, given any set P and N you can construct a circuit of size O(n log n) as desired in deterministic polynomial time.


---

