Gaussian elimination to equations with errors I am reading 
this document and wondering the following part on page 13: 
"Consider applying Gaussian elimination to the noisy samples
to find the first bit" 

If we take, for example, $n = 3$, $s = (1,0,1)$, $x_1 = (1,1,0)$, $x_2=(1,1,1)$ and $ x_3=(0,1,0)$, what will $q$ and $S⊂[q]$ be?
Also, how to confirm the probability will be $1/2+2^{-Θ(3)}$?

I would be grateful for your help in advance.
$q$ is the number of samples and $S$ is the set of indices such that $\sum_{i\in S}x_i = (1,0,...,0)$. In your example, we have $q=3$ and $S=\{1,3\}$. The first bit of the secret $s$ is equals to $\sum_{i\in S}b_i \mod 2$, but with probability $1/2+2^{-\Theta(n)}$ not $1$, because the noises are also considered in this summation. So we need to repeat this procedure $2^{\Theta(n)}$ times to reduce the error probability.