Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAffine extractors over large fields with exponential error
184
0
0.0
(
0
)
Added by
Zeev Dvir
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.
rate research
Read More
We study the problem of extracting random bits from weak sources that are sampled by algorithms with limited memory. This model of small-space sources was introduced by Kamp, Rao, Vadhan and Zuckerman (STOC06), and falls into a line of research initiated by Trevisan and Vadhan (FOCS00) on extracting randomness from weak sources that are sampled by computationally bounded algorithms. Our main results are the following. 1. We obtain near-optimal extractors for small-space sources in the polynomial error regime. For space $s$ sources over $n$ bits, our extractors require just $kgeq scdot$polylog$(n)$ entropy. This is an exponential improvement over the previous best result, which required $kgeq s^{1.1}cdot2^{log^{0.51} n}$ (Chattopadhyay and Li, STOC16). 2. We obtain improved extractors for small-space sources in the negligible error regime. For space $s$ sources over $n$ bits, our extractors require entropy $kgeq n^{1/2+delta}cdot s^{1/2-delta}$, whereas the previous best result required $kgeq n^{2/3+delta}cdot s^{1/3-delta}$ (Chattopadhyay, Goodman, Goyal and Li, STOC20). To obtain our first result, the key ingredient is a new reduction from small-space sources to affine sources, allowing us to simply apply a good affine extractor. To obtain our second result, we must develop some new machinery, since we do not have low-error affine extractors that work for low entropy. Our main tool is a significantly improved extractor for adversarial sources, which is built via a simple framework that makes novel use of a certain kind of leakage-resilient extractors (known as cylinder intersection extractors), by combining them with a general type of extremal designs. Our key ingredient is the first derandomization of these designs, which we obtain using new connections to coding theory and additive combinatorics.
In this paper, we prove some extensions of recent results given by Shkredov and Shparlinski on multiple character sums for some general families of polynomials over prime fields. The energies of polynomials in two and three variables are our main ingredients.
We give a definition of Cox rings and Cox sheaves for varieties over nonclosed fields that is compatible with torsors under quasitori, including universal torsors. We study their existence and classification, we make the relation to torsors precise, and we present arithmetic applications.
In this paper we construct a noncommutative space of ``pointed Drinfeld modules that generalizes to the case of function fields the noncommutative spaces of commensurability classes of Q-lattices. It extends the usual moduli spaces of Drinfeld modules to possibly degenerate level structures. In the second part of the paper we develop some notions of quantum statistical mechanics in positive characteristic and we show that, in the case of Drinfeld modules of rank one, there is a natural time evolution on the associated noncommutative space, which is closely related to the positive characteristic L-functions introduced by Goss. The points of the usual moduli space of Drinfeld modules define KMS functionals for this time evolution. We also show that the scaling action on the dual system is induced by a Frobenius action, up to a Wick rotation to imaginary time.
The notion of semi-random sources, also known as Santha-Vazirani (SV) sources, stands for a sequence of n bits, where the dependence of the ith bit on the previous i-1 bits is limited for every $iin[n]$. If the dependence of the ith bit on the remaining n-1 bits is limited, then this is a strong SV-source. Even the strong SV-sources are known not to admit (universal) deterministic extractors, but they have seeded extractors, as their min-entropy is $Omega(n)$. It is intuitively obvious that strong SV-sources are more than just high-min-entropy sources, and this work explores the intuition. Deterministic condensers are known not to exist for general high-min-entropy sources, and we construct for any constants $epsilon, delta in (0,1)$ a deterministic condenser that maps n bits coming from a strong SV-source with bias at most $delta$ to $Omega(n)$ bits of min-entropy rate at least $1-epsilon$. In conclusion we observe that deterministic condensers are closely related to very strong extractors - a proposed strengthening of the notion of strong (seeded) extractors: in particular, our constructions can be viewed as very strong extractors for the family of strong Santha-Vazirani distributions. The notion of very strong extractors requires that the output remains unpredictable even to someone who knows not only the seed value (as in the case of strong extractors), but also the extractors outputs corresponding to the same input value with each of the preceding seed values (say, under the lexicographic ordering). Very strong extractors closely resemble the original notion of SV-sources, except that the bits must satisfy the unpredictability requirement only on average.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
