# Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings

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?

• @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. Jan 2 at 19:02

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  (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:

 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.

• This sounds like a circuit of size O(s), but not a formula.
– mic
Jan 9 at 18:33
• @mic What makes you say that? The decision tree is a tree, and the given translation to formulas preserves that. Jan 9 at 19:21
• 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$). Jan 9 at 20:36

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.