TIFR CSE 2013 | Part B | Question: 10

Question

Let $m, n$ be positive integers with $m$ a power of $2$. Let $s= 100 n^{2} \log m$. Suppose $S_{1}, S_{2},\dots ,S_{m}$ are subsets of ${1, 2, \dots, s}$ such that $ \mid S_{i} \mid= 10 n \log m$ and $ \mid S_{i} \cap S_{j} \mid \leq \log m$ for all $1 \leq i \lt j \leq m$. Such a collection of sets $S_{1},\dots ,S_{m}$ is an example of a so-called Nisan-Wigderson design. We now consider the set membership problem, where we have to store an arbitrary subset $T \subseteq \left\{1, 2,....,m\right\}, \mid T \mid = n$ as an array $A$ of $s$ bits so that given any integer $x, 1 \leq x \leq m$, we can discover whether $x \in T$  by reading only one bit of $A$. Consider the following strategy to solve this problem. Array $A$ is initialized to all zeroes. Given the set $T$ to be stored, we put a one in all the locations of $A$ indexed by the union $\cup_{t \in T}S_{t}$. Now, given the integer $x$, we read a random location in $A$ from $S_{x}$ and declare that $x \in T$ if the bit in that location is one. This strategy gives the correct answer with probability

• A. $1$ if $x \in T$ and at most $0.1$ if $x ∉ T$.
• B. At least $0.9$ if $x \in T$ and at most $0.1$ if $x ∉ T$.
• C. At least $0.9$ if $x \in T$ and at least $0.9$ if $x ∉ T$.
• D. $1$ if $x \in T$ and at least $0.9$ if $x ∉ T$.
• E. At least $0.9$ if $x \in T$ and $1$ if $x ∉ T$. 

Answer 1

Option D is correct

Let $m=4(2^{2}) , n=2$ then $ s=100 \times 4 \times 2=800 \: numbers $

Let $S_1,S_2,S_3,S_4$ be subsets to $S,$ each having $(10 \times 2 \times 2=40) \: elements$.

Special condition is $ \mid S_i \cap S_j \mid \leq 2 \: (i.e \: \log m)$

Let

$ S_1= \{ 1,2, \ldots ,37,38,39,40 \} \\ S_2 = \{ 121,122, \ldots ,160 \} \\ S_3 = \{ 37,38,41,42, \dots ,78 \} \quad here \: \mid S_1 \cap S_2 \mid = 2 \\ S_4 =  \{39,40,81,82, \ldots ,118 \}  \quad \text{here also same}$.

and $A$ is an array of $800$ locations, initially $0$.

and $T  \subseteq (S_1,S_2,S_3,S_4) \: and \: \mid T \mid = 2 \: \text{( i.e n)}$

$\text{Case 1: Let T } = (S_3, S_4)$

then $A$ is like this $$\begin{array}{c|cccccccccccccccc}  & 1 & 2 & 3 & \ldots & 36 & 37 & 38 & 39 & 40 & 41 & 42 & \ldots & 78 & \ldots & 118 &  \dots & 800 \\  \hline & 0 & 0 & 0 & \ldots & 0 & 1 & 1 & 1 & 1 & 1 & 1 & \dots & 1 & \ldots & 1 & \dots & 0  \end{array}$$ $Case \: \mathrm{a} \: $: $\begin{align}& \\   & \text{If input is $3$ (i.e. $S_3$) belongs to $T$ } \\ & \text{it went to one of the $40$ locations $\{ 37 \ldots 78 \}$} \\ & \text{cmp bit.} \\ & \text{$P$ ($S_3$ present) = $\dfrac{40}{40 }= 1$ }  \end{align} $

$Case \: \mathrm{b} \: : \begin{align}& \\ & \text{If input is $1$ (i.e. $S_1$) belongs to $T$ } \\ & \text{it went to one of the $40$ locations $\{ 1 \ldots 40 \}$} \\ & \text{cmp bit} \\ & \text{$P$ ($S_1$ present) = $\dfrac{4}{40 }= \dfrac{1}{10} \: \mathsf{(wrong \: says)} $} \\ & \text{$P$ ($S_1$ not present) = $\dfrac{36}{40} = \dfrac{9}{10} = 0.9 \: \mathtt{(correct \: says)}$}  \end{align}$