Revision #2 Authors: Matt DeVos, Ariel Gabizon

Accepted on: 5th August 2009 07:27

Downloads: 1892

Keywords:

Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$

such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased

bit when $x$ is chosen uniformly from $X$.

Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets smaller and easier

as $k$ gets larger. This is reflected in previous results:

When $q$ is `large enough', specifically $q= \Omega(n^2)$, Gabizon and Raz \cite{GR05} construct affine extractors for any $k\geq 1$.

In the `hardest case', i.e. when $q=2$, Bourgain \cite{Bour05} constructs affine extractors for $k\geq \delta n$ for any constant (and even slightly sub-constant)

$\delta>0$.

Our main result is the following: Fix any $k\geq 2$ and let $d = 5n/k$. Then whenever $q>2\cdot d^2$ and $p=char(\F)>d$,

we give an explicit \afsext{n}{k}.

For example, when $k=\delta n$ for constant $\delta>0$, we get an extractor for a field of constant size $\Omega(\left(\frac{1}{\delta}\right)^2)$.

Thus our result may be viewed as a `field-size/dimension' tradeoff for affine extractors.

Although for large $k$ we are not able to improve (or even match) the previous result of \cite{Bour05}, our construction and proof have the advantage of being very simple:

Assume $n$ is prime and $d$ is odd, and fix any non-trivial linear map $T:\F^n\mapsto \F$.

Define $QR:\F\mapsto \B$ by $QR(x)=1$ if and only if $x$ is a quadratic residue. Then, the function $D:\F^n\mapsto \B$ defined by $D(x)\triangleq QR(T(x^d))$ is an \afsext{n}{k}.

Our proof uses a result of Heur, Leung and Xiang \cite{HLX02} giving a lower bound on the dimension of products of subspaces.

Proof in preliminaries section corrected. Remark Corrected

Revision #1 Authors: Matt DeVos, Ariel Gabizon

Accepted on: 1st August 2009 06:06

Downloads: 1528

Keywords:

Let $\F$ be the field of $q$ elements. An (n,k)-affine extractor is a mapping $D:\F^n\ar\B$

such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased

bit when $x$ is chosen uniformly from $X$.

Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets smaller and easier

as $k$ gets larger. This is reflected in previous results:

When $q$ is `large enough', specifically $q= \Omega(n^2)$, Gabizon and Raz \cite{GR05} construct affine extractors for any $k\geq 1$.

In the `hardest case', i.e. when $q=2$, Bourgain \cite{Bour05} constructs affine extractors for $k\geq \delta n$ for any constant (and even slightly sub-constant)

$\delta>0$.

Our main result is the following: Fix any $k\geq 2$ and let $d = 5n/k$. Then whenever $q>2\cdot d^2$ and $p=char(\F)>d$,

we give an explicit \afsext{n}{k}.

For example, when $k=\delta n$ for constant $\delta>0$, we get an extractor for a field of constant size $\Omega(\left(\frac{1}{\delta}\right)^2)$.

Thus our result may be viewed as a `field-size/dimension' tradeoff for affine extractors.

Although for large $k$ we are not able to improve (or even match) the previous result of \cite{Bour05}, our construction and proof have the advantage of being very simple:

Assume $n$ is prime and $d$ is odd, and fix any non-trivial linear map $T:\F^n\mapsto \F$.

Define $QR:\F\mapsto \B$ by $QR(x)=1$ if and only if $x$ is a quadratic residue. Then, the function $D:\F^n\mapsto \B$ defined by $D(x)\triangleq QR(T(x^d))$ is an (n,k)-affine extractor.

Our proof uses a result of Heur, Leung and Xiang \cite{HLX02} giving a lower bound on the dimension of products of subspaces.

Abstract made more readable. Small correction in definition in preliminaries section

TR09-063 Authors: Matt DeVos, Ariel Gabizon

Publication: 1st August 2009 04:37

Downloads: 1687

Keywords:

Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$

such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased

bit when $x$ is chosen uniformly from $X$.

Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets smaller and easier

as $k$ gets larger. This is reflected in previous results:

When $q$ is `large enough', specifically $q= \Omega(n^2)$, Gabizon and Raz \cite{GR05} construct affine extractors for any $k\geq 1$.

In the `hardest case', i.e. when $q=2$, Bourgain \cite{Bour05} constructs affine extractors for $k\geq \delta n$ for any constant (and even slightly sub-constant)

$\delta>0$.

Our main result is the following: Fix any $k\geq 2$ and let $d = 5n/k$. Then whenever $q>2\cdot d^2$ and $p=char(\F)>d$,

we give an explicit \afsext{n}{k}.

For example, when $k=\delta n$ for constant $\delta>0$, we get an extractor for a field of constant size $\Omega(\left(\frac{1}{\delta}\right)^2)$.

Thus our result may be viewed as a `field-size/dimension' tradeoff for affine extractors.

Although for large $k$ we are not able to improve (or even match) the previous result of \cite{Bour05}, our construction and proof have the advantage of being very simple:

Assume $n$ is prime and $d$ is odd, and fix any non-trivial linear map $T:\F^n\mapsto \F$.

Define $QR:\F\mapsto \B$ by $QR(x)=1$ if and only if $x$ is a quadratic residue. Then, the function $D:\F^n\mapsto \B$ defined by $D(x)\triangleq QR(T(x^d))$ is an \afsext{n}{k}.

Our proof uses a result of Heur, Leung and Xiang \cite{HLX02} giving a lower bound on the dimension of products of subspaces.