New answers tagged machine-learning
13
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 ...
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.
Top 50 recent answers are included
