# Epsilon balanced Code

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.

• 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. – Yuval Filmus Dec 12 '20 at 15:15
• $1/2+\epsilon$ part I am not getting. $1/2-\epsilon$ comes from some parameter fixing. – roydiptajit Dec 12 '20 at 16:02