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
Related Tags
machine-learning × 314lg.learning × 110
reference-request × 42
st.statistics × 28
ds.algorithms × 27
pac-learning × 26
cc.complexity-theory × 22
vc-dimension × 22
optimization × 20
ne.neural-evol × 20
ai.artificial-intel × 16
approximation-algorithms × 13
clustering × 13
graph-theory × 11
boolean-functions × 8
sample-complexity × 8
cg.comp-geom × 7
query-complexity × 7
graph-algorithms × 6
np-hardness × 6
pr.probability × 6
it.information-theory × 6
convex-optimization × 6
property-testing × 6
network-modeling × 6