More Like this

1. Explicit two-source extractors and resilient functions

   https://doi.org/10.4007/annals.2019.189.3.1  

   Chattopadhyay, Eshan; Zuckerman, David (May 2020, Annals of mathematics)

   We explicitly construct an extractor for two independent sources on 𝑛 bits, each with min-entropy at least log𝐶𝑛 for a large enough constant 𝐶. Our extractor outputs one bit and has error 𝑛−Ω(1). The best previous extractor, by Bourgain, required each source to have min-entropy .499𝑛. A key ingredient in our construction is an explicit construction of a monotone, almost-balanced Boolean function on 𝑛 bits that is resilient to coalitions of size 𝑛1−𝛿 for any 𝛿>0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on 𝑛 bits, where some unknown 𝑛−𝑞 bits are chosen almost polylog(𝑛)-wise independently, and the remaining 𝑞=𝑛1−𝛿 bits are chosen by an adversary as an arbitrary function of the 𝑛−𝑞 bits. The best previous construction, by Viola, achieved 𝑞=𝑛1/2–𝛿. Our explicit two-source extractor directly implies an explicit construction of a 2(loglog𝑁)𝑂(1)-Ramsey graph over 𝑁 vertices, improving bounds obtained by Barak et al. and matching an independent work by Cohen. 

   more » « less
2. Extractors for Polynomial Sources over 𝔽₂

   https://doi.org/10.4230/LIPIcs.ITCS.2024.28  

   Chattopadhyay, Eshan; Goodman, Jesse; Gurumukhani, Mohit (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Guruswami, Venkatesan (Ed.)

   We explicitly construct the first nontrivial extractors for degree d ≥ 2 polynomial sources over 𝔽₂. Our extractor requires min-entropy k ≥ n - (√{log n})/((log log n / d)^{d/2}). Previously, no constructions were known, even for min-entropy k ≥ n-1. A key ingredient in our construction is an input reduction lemma, which allows us to assume that any polynomial source with min-entropy k can be generated by O(k) uniformly random bits. We also provide strong formal evidence that polynomial sources are unusually challenging to extract from, by showing that even our most powerful general purpose extractors cannot handle polynomial sources with min-entropy below k ≥ n-o(n). In more detail, we show that sumset extractors cannot even disperse from degree 2 polynomial sources with min-entropy k ≥ n-O(n/log log n). In fact, this impossibility result even holds for a more specialized family of sources that we introduce, called polynomial non-oblivious bit-fixing (NOBF) sources. Polynomial NOBF sources are a natural new family of algebraic sources that lie at the intersection of polynomial and variety sources, and thus our impossibility result applies to both of these classical settings. This is especially surprising, since we do have variety extractors that slightly beat this barrier - implying that sumset extractors are not a panacea in the world of seedless extraction. 

   more » « less
3. Low-Degree Polynomials Extract From Local Sources

   Alrabiah, Omar; Chattopadhyay, Eshan; Goodman, Jesse; Li, Xin; Ribeiro, Joao (January 2022, Leibniz international proceedings in informatics)

   Bojanczyk, Mikolaj; Merelli, Emanuela; Woodruff, David P. (Ed.)

   We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, this model was introduced by De and Watson (TOCT 2012) and Viola (SICOMP 2014), and is closely related to sources generated by AC⁰ circuits and bounded-width branching programs. In particular, extractors for local sources also work for sources generated by these classical computational models. Despite being introduced a decade ago, little progress has been made on improving the entropy requirement for extracting from local sources. The current best explicit extractors require entropy n^{1/2}, and follow via a reduction to affine extractors. To start, we prove a barrier showing that one cannot hope to improve this entropy requirement via a black-box reduction of this form. In particular, new techniques are needed. In our main result, we seek to answer whether low-degree polynomials (over 𝔽₂) hold potential for breaking this barrier. We answer this question in the positive, and fully characterize the power of low-degree polynomials as extractors for local sources. More precisely, we show that a random degree r polynomial is a low-error extractor for n-bit local sources with min-entropy Ω(r(nlog n)^{1/r}), and we show that this is tight. Our result leverages several new ingredients, which may be of independent interest. Our existential result relies on a new reduction from local sources to a more structured family, known as local non-oblivious bit-fixing sources. To show its tightness, we prove a "local version" of a structural result by Cohen and Tal (RANDOM 2015), which relies on a new "low-weight" Chevalley-Warning theorem. 

   more » « less
4. Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More

   https://doi.org/10.1109/FOCS57990.2023.00075  

   Li, Xin (November 2023, IEEE)

   A long line of work in the past two decades or so established close connections between several different pseudorandom objects and applications, including seeded or seedless non-malleable extractors, two source extractors, (bipartite) Ramsey graphs, privacy amplification protocols with an active adversary, non-malleable codes and many more. These connections essentially show that an asymptotically optimal construction of one central object will lead to asymptotically optimal solutions to all the others. However, despite considerable effort, previous works can get close but still lack one final step to achieve truly asymptotically optimal constructions. In this paper we provide the last missing link, thus simultaneously achieving explicit, asymptotically optimal constructions and solutions for various well studied extractors and applications, that have been the subjects of long lines of research. Our results include: 1. Asymptotically optimal seeded non-malleable extractors, which in turn give two source extractors for asymptotically optimal min-entropy of $$O(\log n)$$, explicit constructions of $$K$$-Ramsey graphs on $$N$$ vertices with $$K=\log^{O(1)} N$$, and truly optimal privacy amplification protocols with an active adversary. 2. Two source non-malleable extractors and affine non-malleable extractors for some linear min-entropy with exponentially small error, which in turn give the first explicit construction of non-malleable codes against $$2$$-split state tampering and affine tampering with constant rate and \emph{exponentially} small error. 3. Explicit extractors for affine sources, sumset sources, interleaved sources, and small space sources that achieve asymptotically optimal min-entropy of $$O(\log n)$ or $$2s+O(\log n)$$ (for space $$s$$ sources). 4. An explicit function that requires strongly linear read once branching programs of size $$2^{n-O(\log n)}$$, which is optimal up to the constant in $$O(\cdot)$$. Previously, even for standard read once branching programs, the best known size lower bound for an explicit function is $$2^{n-O(\log^2 n)}$$. 

   more » « less
5. Two-Source and Affine Non-Malleable Extractors for Small Entropy

   https://doi.org/10.4230/lipics.icalp.2024.108  

   Li, Xin; Zhong, Yan (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)

   Non-malleable extractors are generalizations and strengthening of standard randomness extractors, that are resilient to adversarial tampering. Such extractors have wide applications in cryptography and have become important cornerstones in recent breakthroughs of explicit constructions of two-source extractors and affine extractors for small entropy. However, explicit constructions of non-malleable extractors appear to be much harder than standard extractors. Indeed, in the well-studied models of two-source and affine non-malleable extractors, the previous best constructions only work for entropy rate > 2/3 and 1-γ for some small constant γ > 0 respectively by Li (FOCS' 23). In this paper, we present explicit constructions of two-source and affine non-malleable extractors that match the state-of-the-art constructions of standard ones for small entropy. Our main results include: - Two-source and affine non-malleable extractors (over 𝖥₂) for sources on n bits with min-entropy k ≥ log^C n and polynomially small error, matching the parameters of standard extractors by Chattopadhyay and Zuckerman (STOC' 16, Annals of Mathematics' 19) and Li (FOCS' 16). - Two-source and affine non-malleable extractors (over 𝖥₂) for sources on n bits with min-entropy k = O(log n) and constant error, matching the parameters of standard extractors by Li (FOCS' 23). Our constructions significantly improve previous results, and the parameters (entropy requirement and error) are the best possible without first improving the constructions of standard extractors. In addition, our improved affine non-malleable extractors give strong lower bounds for a certain kind of read-once linear branching programs, recently introduced by Gryaznov, Pudlák, and Talebanfard (CCC' 22) as a generalization of several well studied computational models. These bounds match the previously best-known average-case hardness results given by Chattopadhyay and Liao (CCC' 23) and Li (FOCS' 23), where the branching program size lower bounds are close to optimal, but the explicit functions we use here are different. Our results also suggest a possible deeper connection between non-malleable extractors and standard ones. 

   more » « less