Fix a family of $m$ sets $A_1,\dots,A_m\subseteq \{0,1\}^n$. For some integer parameter $t$, consider the class $\mathcal{S}$ of sets of the form $S(i_1,\dots,i_t):=\bigcap_{j=1}^{t}A_{i_j}$, for indices $i_j\in\{1,\dots,m\}$. There are at most $m^t$ sets in $\mathcal{S}$.

My question is the following:

For a parameter $\ell<n$, does there exist a family of $r=O(m^\ell)$ sets $B_1,\dots,B_r$ satisfying $|B_i|\geq 2^{n-\ell}$ for all $i$ and such that, for every set $S\in\mathcal{S}$ satisfying $|S|\geq 2^{n-\ell}$, there exist disjoint sets $B_{i'_1},\dots,B_{i'_s}$, for some $s\leq r$, such that

$$\left|S\triangle \bigcup_j B_{i'_j}\right|\leq 2^{n-\ell},$$

where $\triangle$ denotes symmetric difference? Intuitively, this means that we can "approximately" partition the sets in $\mathcal{S}$ using only the sets $B_i$.

I am looking for either an answer, or references to other problems that may be connected to this question. If it makes it easier, you may assume that $m=2^{\text{poly}(n)}$ and $t=\text{poly}(n)>\ell$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.