Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR09-063 | 5th August 2009 07:27

Simple Affine Extractors using Dimension Expansion

RSS-Feed




Revision #2
Authors: Matt DeVos, Ariel Gabizon
Accepted on: 5th August 2009 07:27
Downloads: 3462
Keywords: 


Abstract:

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.



Changes to previous version:

Proof in preliminaries section corrected. Remark Corrected


Revision #1 to TR09-063 | 1st August 2009 06:06

Simple Affine Extractors using Dimension Expansion





Revision #1
Authors: Matt DeVos, Ariel Gabizon
Accepted on: 1st August 2009 06:06
Downloads: 3025
Keywords: 


Abstract:

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.



Changes to previous version:

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


Paper:

TR09-063 | 29th July 2009 18:57

Simple Affine Extractors using Dimension Expansion





TR09-063
Authors: Matt DeVos, Ariel Gabizon
Publication: 1st August 2009 04:37
Downloads: 3188
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint