×

On the construction of affine extractors. (English) Zbl 1115.68108

Summary: We address the problem of explicit construction of so-called ‘affine extractors’ of \(\delta\)-entropy ratio, when \(\delta \leq 1/2\) (for \(\delta > 1/2\), there is a well-known and easy example based on the Hadamard function). We first give examples for \(\delta\) slightly below \(1/2\) and produce then a construction for arbitrary given \(\delta > 0\). All these examples are again of a simple algebraic nature. The mathematics involved includes recent developments in the sum-product theory in finite fields and certain new bounds on multilinear exponential sums.

MSC:

68R10 Graph theory (including graph drawing) in computer science
11L07 Estimates on exponential sums
60C05 Combinatorial probability
68W20 Randomized algorithms
Full Text: DOI