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 nonmalleable extractors, two source extractors, (bipartite) Ramsey graphs, privacy amplification protocols with an active adversary, nonmalleable 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 nonmalleable extractors, which in turn give two source extractors for asymptotically optimal minentropy 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 nonmalleable extractors and affine nonmalleable extractors for some linear minentropy with exponentially small error, which in turn give the first explicit construction of nonmalleable 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 minentropy 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^{nO(\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^{nO(\log^2 n)}$.
more »
« less
Extractors for Images of Varieties
We construct explicit deterministic extractors for polynomial images
of varieties, that is, distributions sampled by applying a lowdegree
polynomial map π to an element sampled uniformly
at random from a πdimensional variety π. This class of
sources generalizes both polynomial sources, studied by Dvir, Gabizon and Wigderson (FOCS 2007, Comput. Complex. 2009), and variety sources, studied by Dvir (CCC 2009, Comput. Complex. 2012).
Assuming certain natural nondegeneracy conditions on the
map π and the variety π , which in particular ensure that the source
has enough minentropy, we extract almost all the minentropy
of the distribution. Unlike the DvirβGabizonβWigderson and Dvir
results, our construction works over large enough finite fields of
arbitrary characteristic. One key part of our construction is an
improved deterministic rank extractor for varieties. As a byproduct,
we obtain explicit Noether normalization lemmas for affine varieties
and affine algebras.
Additionally, we generalize a construction of affine extractors
with exponentially small error due to Bourgain, Dvir and Leeman
(Comput. Complex. 2016) by extending it to all finite prime fields
of quasipolynomial size.
more »
« less
 NSFPAR ID:
 10484417
 Publisher / Repository:
 ACM
 Date Published:
 Journal Name:
 Conference proceedings of the annual ACM Symposium on Theory of Computing
 ISSN:
 07349025
 ISBN:
 9781450399135
 Page Range / eLocation ID:
 46 to 59
 Format(s):
 Medium: X
 Location:
 Orlando FL USA
 Sponsoring Org:
 National Science Foundation
More Like this


TaShma, Amnon (Ed.)In a recent work, Gryaznov, PudlΓ‘k and Talebanfard (CCC '22) introduced a linear variant of readonce branching programs, with motivations from circuit and proof complexity. Such a readonce linear branching program is a branching program where each node is allowed to make 𝔽βlinear queries, and is readonce in the sense that the queries on each path is linearly independent. As their main result, they constructed an explicit function with averagecase complexity 2^{n/3o(n)} against a slightly restricted model, which they call strongly readonce linear branching programs. The main tool in their lower bound result is a new type of extractor, called directional affine extractors, that they introduced. Our main result is an explicit function with 2^{no(n)} averagecase complexity against the strongly readonce linear branching program model, which is almost optimal. This result is based on a new connection from this problem to sumset extractors, which is a randomness extractor model introduced by Chattopadhyay and Li (STOC '16) as a generalization of many other wellstudied models including twosource extractors, affine extractors and smallspace extractors. With this new connection, our lower bound naturally follows from a recent construction of sumset extractors by Chattopadhyay and Liao (STOC '22). In addition, we show that directional affine extractors imply sumset extractors in a restricted setting. We observe that such restricted sumset sources are enough to derive lower bounds, and obtain an arguably more modular proof of the lower bound by Gryaznov, PudlΓ‘k and Talebanfard. We also initiate a study of pseudorandomness against linear branching programs. Our main result here is a hitting set generator construction against regular linear branching programs with constant width. We derive this result based on a connection to Kakeya sets over finite fields.more » « less

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 boundedwidth 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 blackbox reduction of this form. In particular, new techniques are needed. In our main result, we seek to answer whether lowdegree polynomials (over π½β) hold potential for breaking this barrier. We answer this question in the positive, and fully characterize the power of lowdegree polynomials as extractors for local sources. More precisely, we show that a random degree r polynomial is a lowerror extractor for nbit local sources with minentropy Ξ©(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 nonoblivious bitfixing 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 "lowweight" ChevalleyWarning theorem.more » « less

We explicitly construct an extractor for two independent sources on π bits, each with minentropy 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 minentropy .499π. A key ingredient in our construction is an explicit construction of a monotone, almostbalanced 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 nonoblivious bitfixing 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 twosource 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

We explicitly construct an extractor for two independent sources on n bits, each with minentropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{\Omega(1)}. The best previous extractor, by Bourgain, required each source to have minentropy .499n. A key ingredient in our construction is an explicit construction of a monotone, almostbalanced boolean function on n bits that is resilient to coalitions of size n^{1delta}, for any delta>0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of nonoblivious bitfixing sources on n bits, where some unknown nq bits are chosen almost polylog(n)wise independently, and the remaining q=n^{1\delta} bits are chosen by an adversary as an arbitrary function of the nq bits. The best previous construction, by Viola, achieved q=n^{1/2  \delta}. Our explicit twosource extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.more » « less