Deterministic extractors for affine sources over large fields

Let \(\mathbb F\) be a finite field, and \(X\) be a random variable on \(\mathbb F^n\). \(X\) is a \((n, k)\)-affine source if it is uniformly distributed over a \(k\)-dimensional affine subspace of \(\mathbb F^n\). The authors show how to use \(X\) in order to generate distributions that are very close to the uniform one on the spaces of \(\mathbb F^{k-1}\) or even \(\mathbb F\). Two distributions \(P\) and \(Q\), on a finite probability space \(\Omega\), are \(\varepsilon\)-close if the statistical distance \(| P-Q| =\sum_{w \in \Omega}| \text{Pr}_P(w)-\text{Pr}_Q(w)| /2\) is less than \(\varepsilon\). A function \(D:\mathbb F_q^n \rightarrow \Omega\) is a deterministic \(k, \varepsilon\)-affine source extractor if for every \((n, k)_q\)-affine source \(X\) the distribution \(D(X)\) is \(\varepsilon\)-close to uniform. With this the authors have Theorem 1. There exists a constant \(q_0\) such that for any field \(\mathbb F_q\) and integers \(n, k\) with \(q > \max [q_0, n^{20}]\), there is an explicit deterministic \((k, \rho)\)-affine source extractor \(D:\mathbb F_q^n \rightarrow \mathbb F_q^{k-1}\), with \(\rho \leq q^{-1/21}\). Theorem 2. For any field \(\mathbb F_q\), integer \(n\) and \(\epsilon >0\), there is an explicit deterministic \((1, \varepsilon)\)-affine source extractor \(D:\mathbb F_q^n \rightarrow \{0, 1\}^d\), with \(d=\left\lfloor \log_2q-2\log_2(n/\varepsilon)-2\log_2\log_2q -4 \right\rfloor\). Two immediate applications are mentioned: (i) One can get \((1-\delta)\) fraction of randomness out of an affine source, where \(\delta >0\) arbitrary, provided that \(q >n^c\), where \(c\) depend on \(\delta\). (ii) With \(q \geq n^2\log_2^3n\) and \(\varepsilon =1/4\) the generator gives an explicit two-coloring of \(\mathbb F_q\) such that no line is monochromatic. The proofs rely on \textit{A. Weil}'s theorems [Proc. Natl. Acad. Sci. USA 34, 204--207 (1948; Zbl 0032.26102)], and the Xor lemma of Vazirani, see e.g. \textit{A. Elbaz} [Improved constructions for extracting quasi-random bits from sources of weak randomness. MSc Thesis, Weizmann Institute (2003)].

Recommendations

Cites work

Cited in

(34)

This page was built for publication: Deterministic extractors for affine sources over large fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2390150)