Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-018 | 8th March 2009 00:00

$GF(2^n)$-Linear Tests versus $GF(2)$-Linear Tests


Authors: Yoav Tzur
Publication: 8th March 2009 22:24
Downloads: 1507


A small-biased distribution of bit sequences is defined as one withstanding $GF(2)$-linear tests for randomness, which are linear combinations of the bits themselves. We consider linear combinations over larger fields, specifically, $GF(2^n)$ for $n$ that divides the length of the bit sequence. Indeed, this means that we partition the bits to blocks of length $n$ and treat each block as the representation of a field element. Various properties of the resulting field element can then be tested. We show that the latter $GF(2^n)$-linear tests are at least as powerful as the $GF(2)$-linear tests. This holds even for a very limited final test of the resulting field element (e.g., checking only the first bit). This is shown constructively in the sense that we show for each linear combination over $GF(2)$, an explicit linear combination over $GF(2^n)$ whose first bit (for instance) has the same bias.

One corollary of the above is that the generator producing a random geometric series over $GF(2^n)$, namely $(a,b) \mapsto (a^i \cdot b)_{i=0}^\ell$, is $\frac{\ell}{2^n}$-biased.


Comment #1 to TR09-018 | 29th September 2009 23:03

Using more variables in the geometric generator

Comment #1
Authors: Yoav Tzur
Accepted on: 29th September 2009 23:03
Downloads: 1011


We present an explicit construction of an $\eps$-bias generator that outputs $m$ bits using a seed shorter than $\frac{k}{k-1} \log m + k \log (1/\eps) + k \log (k-1)$ bits, for any integer $k \geq 2$. This generator is a generalization of the geometric generator considered in [ECCC, TR09-018], which can be obtained as the special case $k=2$.

Setting $k = \left\lceil \sqrt{\frac{\log m}{\log (1/\eps)}} + 1 \right\rceil$ yields a seed of length at most $\log m + 2\sqrt{\log m \cdot \log(1/\eps)} + 2 \log(1/\eps) + \tilde O(\sqrt{\log m})$. Specifically, if $\eps \geq 2^{-\poly\log\log m}$ (e.g., if $1/\eps$ is polylogarithmic in $m$, or even constant), the seed length is $\log m + \tilde O(\sqrt{\log m})$.

ISSN 1433-8092 | Imprint