2
$\begingroup$

I'd like a construction of the following description. Let $V$ be a set of $n$ elements. I'd like a collection $X$ of subsets of $V$ such that for any pair $(P,Q)$ of disjoint subsets of $V$, there is an element $S \in X$ such that $|S \cap P|$ and $|S \cap Q|$ are both odd.

Probabilistic arguments indicate that there exists solutions with $|X|=O(n)$, but I'd like an explicit design. I'd also like to know the best possible constant factor in the size $|X|$.

It sounded basic enough that I thought it should be solved, or easily attackable, but I'm drawing a blank. Any pointers?

$\endgroup$
2
  • 1
    $\begingroup$ I suppose $P$ and $Q$ should be nonempty? $\endgroup$ Dec 16 '20 at 13:42
  • $\begingroup$ Right, both are nonempty. $\endgroup$ Dec 22 '20 at 9:39
4
$\begingroup$

Recall that a distribution $Y$ over $\{0, 1\}^n$ is called $\epsilon$-biased if for every nonempty set $P \subseteq [n]$, we have $$ \left|\mathbb{E}[\oplus_{i \in P} Y_i] - \frac{1}{2}\right| \leq \frac{\epsilon}{2}. $$ In other words, an $\epsilon$-biased distribution is a primitive kind of pseudorandom generator: it fools parity functions with error $\epsilon/2$. I claim that an $\epsilon$-biased distribution automatically also fools functions of the form $\mathsf{AND} \circ \mathsf{PARITY}$. That is:

Claim: Let $f \colon \{0, 1\}^n \to \{0, 1\}$ be of the form $f(x) = \wedge_{i = 1}^m \bigoplus_{j \in P_i} x_j$, where $P_1, \dots, P_m \subseteq [n]$. Let $Y$ be $\epsilon$-biased and let $U$ be uniform random over $\{0, 1\}^n$. Then $$ \left|\mathbb{E}[f(Y)] - \mathbb{E}[f(U)]\right| \leq \epsilon. $$

Proof: We can use the Fourier expansion of the AND function: $$ f(x) = \sum_{T \subseteq [m]} \frac{(-1)^{|T|}}{2^m} \cdot \prod_{i \in T} (-1)^{\oplus_{j \in P_i} x_j} = \sum_{T \subseteq [m]} \frac{(-1)^{|T|}}{2^m} \cdot (-1)^{\bigoplus_{i \in T, j \in P_i} x_j} $$ For a fixed $T \subseteq [m]$, we have $$ |\mathbb{E}[(-1)^{\oplus_{i \in T, j \in P_i} Y_j}] - \mathbb{E}[(-1)^{\oplus_{i \in T, j \in P_i} U_j}]| \leq 2 \cdot |\mathbb{E}[\oplus_{i \in T, j \in P_i} Y_j] - \mathbb{E}[\oplus_{i \in T, j \in P_i} U_j]| \leq \epsilon. $$ Therefore, by the triangle inequality, $$ |\mathbb{E}[f(Y)] - \mathbb{E}[f(U)]| \leq \sum_{T \subseteq [m]} \frac{\epsilon}{2^m} = \epsilon. \qquad \square $$ Your condition, that $|S \cap P|$ and $|S \cap Q|$ are both odd, can be rephrased as a function $f$ as in the claim by considering the indicator vectors of all the sets under consideration. Under the uniform distribution, the condition is satisfied with probability $1/4$. Therefore, it suffices to take $X$ to be the support of an $\epsilon$-biased distribution with $\epsilon < 1/4$. Plugging in known constructions of small-biased distributions gives an explicit construction with $|X| = O(n)$.

$\endgroup$
2
  • $\begingroup$ Thank you! I'll look closer at this. Do you also have an idea of whether it's possible to replicate the same constant factor as in the probabilistic construction? $\endgroup$ Dec 22 '20 at 11:46
  • $\begingroup$ I'm not sure, but I suspect that getting the right constant factor would be challenging. $\endgroup$ Dec 23 '20 at 20:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.