A linear code is termed as an $\epsilon -$balanced code if all the codewords are having fractional hamming weight $\in (1/2-\epsilon,1/2+\epsilon)$. I want to show that for every $\epsilon\in (0,1/2)$, $\exists$ a linear $\epsilon -$balanced code $E:\{0,1\}^n\mapsto \{0,1\}^{poly(n/\epsilon)}$, with efficient encoding decoding algorithm.

If we ignore the efficient encoding decoding and polynomial stretch, then any $A_{n\times k}$ matrix over $\mathbb{F}_2$, where $2^n\geq k>2^{n-1}$, gives such a code, as any non zero vector in $\{0,1\}^n$, is orthogonal to exactly half of the total number of vectors in $\{0,1\}^n$. So, if we choose a random $A_{n\times k}$, then $Ax$, $x\in\{0,1\}^n$ has fractional hamming weight, $\in (1/2-\epsilon,1/2+\epsilon)$.$\epsilon$ depends on $k$ and for $k=2^n$, $\epsilon=0$.

I also found in wikipedia that, if all the rows of $A$ are $\epsilon-$biased, then the corresponding code is $\epsilon-$ balanced. I am not quite sure what $\epsilon-$ biased code means and their ways of construction. Can anyone suggest me a simple way to construct these sets?

By the efficient encoding-decoding requirement, one method also comes in mind to use concatenation of Walsh Hadamard Code and Reed Solemon Code. These meets the encoding-decoding requirement and strech requirement, but whether it can be made $\epsilon-$balanced is unclear to me.

Can anyone answer this?

  • $\begingroup$ The Wikipedia page mentioning $\epsilon$-biased should also define this term, or at least give a relevant link. Usually this term means that the average value of a Fourier character on a random element of the set (in this case, subspace) is at most $\epsilon$ in magnitude. $\endgroup$ – Yuval Filmus Dec 12 '20 at 15:15
  • $\begingroup$ Yes, I followed links in Wikipedia, but the ways described are complicated. I am trying to find more simple idea. Can't concatenated codes come of any use here? If we try to do some parameter fixing, I think concatenation of Reed Solemon and walsh hadamard should do.. I want an easy way to proceed with this problem. Means I want to avoid the use of epsilon bias concepts.. that is why I presented some more ideas in the question $\endgroup$ – roydiptajit Dec 12 '20 at 15:32
  • 1
    $\begingroup$ Why don't you try it out, then? What's stopping you? $\endgroup$ – Yuval Filmus Dec 12 '20 at 15:35
  • $\begingroup$ $1/2+\epsilon$ part I am not getting. $1/2-\epsilon$ comes from some parameter fixing. $\endgroup$ – roydiptajit Dec 12 '20 at 16:02

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.