We study the tasks of deterministically condensing and extracting from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model of defective randomness where extraction is impossible in many parameter regimes [AORSV, EUROCRYPT'20]. A $(g,\ell)$-oNOSF source is a sequence of $\ell$ blocks where at least $g$ blocks are good (independent, with min-entropy) and the remaining bad blocks are controlled by an online adversary and can be arbitrarily correlated with prior blocks. Previously, [CGR, FOCS'24] proved impossibility of condensing beyond rate $1/2$ when $g\le 0.5 \ell$ and showed existence of condensers for when $g \ge 0.51\ell$ and $n$ is exponential in $\ell$. In this work, not only do we construct the first explicit condensers matching the existential results of [CGR, FOCS'24], but we make a doubly exponential improvement by handling the case when $g\ge 0.51\ell$ and $n$ is only polylogarithmic in $\ell$. We also obtain a much improved explicit construction for transforming low-entropy oNOSF sources into uniform oNOSF sources. Next, we essentially resolve the question of the existence of condensers for oNOSF sources by showing the existence of condensers even when $n$ is a large enough constant and $\ell$ is growing (provided $g \ge 0.51\ell$). We apply our condensers to collective coin flipping and collective sampling, widely studied problems in fault-tolerant distributed computing, and provide very simple protocols for them. Finally, we study the possibility of extraction from oNOSF sources. For lower bounds, we introduce the notion of online influence - extending the notion of influence of boolean functions - and establish tight bounds that imply extraction lower bounds. We also construct explicit extractors via leader election protocols that beat standard resilient functions [AL, Combinatorica'93].

Random selection is a fundamental task in fault-tolerant distributed computing where processors select a random outcome from some domain. Two special cases of this, leader election (where the processors designate a leader amongst themselves) and collective coin flipping (where the processors agree on a common random bit), have been especially widely studied. We study these problems in the full-information model, where processors communicate via a single broadcast channel, have access to private randomness, and face a computationally unbounded adversary that controls some of the processors. Despite decades of study, key gaps remain in our understanding of the trade-offs between round complexity, communication per player in each round, and adversarial resilience. We make progress by proving new lower bounds for coin flipping protocols and both new upper and lower bounds for leader election and random selection protocols.

While the existence of randomness extractors, both seeded and seedless, has been studied for many sources of randomness, currently, not much is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, online NOSF (oNOSF) sources (originally defined as SHELA sources in [1]), and almost Chor-Goldreich (CG) sources as defined in [2]. We will think of these sources as a sequence of random variables$\mathbf{X}=\mathbf{X}_{1}, \ldots,\mathbf{X}_{\ell}$on$\ell$symbols where at least$g$out of these$\ell$symbols are “good” (i.e., have some min-entropy requirement), denoted as a$(g, \ell)-\mathbf{source}$, and the remaining “bad”$\ell-g$symbols may adversarially depend on these$g$good blocks. The difference between each of these sources is realized by restrictions on the power of the adversary, with the adversary in NOSF sources having no restrictions. Prior to our work, the only known seedless condenser upper or lower bound in these settings is due to [2], where they explicitly construct a seedless condenser for a restricted subset of$(g,\ell)- \mathbf{adversarial}$CG sources. The following are our main results concerning seedless condensers for each of these sources. 1) oNOSF sources a) When$g\leq\ell/2$, we prove that condensing with error 0.99 above rate$\frac{1}{\lfloor\ell/g\rfloor}$is impossible. In fact, we show that this is tight. b) Quite surprisingly, for$g > \ell/2$, we show the existence of excellent condensers for uniform oNOSF sources. In addition, we show the existence of similar condensers for oNOSF sources with only logarithmic min-entropy. Our results are based on a new type of two-source extractors, called output-light two-source extractors, that we introduce and prove the existence of. 2) Adversarial CG sources a) We observe that uniform adversarial CG sources are equivalent to uniform oNOSF sources and consequently inherit the same results. b) We show that one cannot condense beyond the min-entropy gap of each block or condense low min-entropy CG sources above rate 1/2. 3) NOSF sources a) We show that condensing with constant error above rate$\frac{g}{\ell}$is impossible for uniform NOSF sources for any$g$and$\ell$, thus ruling out the possibility of any non-trivial condensing. This shows an interesting distinction between NOSF and oNOSF sources.

In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is a branching program where each node is allowed to make 𝔽₂-linear queries, and is read-once in the sense that the queries on each path is linearly independent. As their main result, they constructed an explicit function with average-case complexity 2^{n/3-o(n)} against a slightly restricted model, which they call strongly read-once 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^{n-o(n)} average-case complexity against the strongly read-once 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 well-studied models including two-source extractors, affine extractors and small-space 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.

Recently, there has been exciting progress in understanding the complexity of distributions. Here, the goal is to quantify the resources required to generate (or sample) a distribution. Proving lower bounds in this new setting is more challenging than in the classical setting, and has yielded interesting new techniques and surprising applications. In this work, we initiate a study of the complexity of sampling with limited memory, and obtain the first nontrivial sampling lower bounds against oblivious read-once branching programs (ROBPs). In our first main result, we show that any distribution sampled by an ROBP of width 2^{Ω(n)} has statistical distance 1-2^{-Ω(n)} from any distribution that is uniform over a good code. More generally, we obtain sampling lower bounds for any list decodable code, which are nearly tight. Previously, such a result was only known for sampling in AC⁰ (Lovett and Viola, CCC'11; Beck, Impagliazzo and Lovett, FOCS'12). As an application of our result, a known connection implies new data structure lower bounds for storing codewords. In our second main result, we prove a direct product theorem for sampling with ROBPs. Previously, no direct product theorems were known for the task of sampling, for any computational model. A key ingredient in our proof is a simple new lemma about amplifying statistical distance between sequences of somewhat-dependent random variables. Using this lemma, we also obtain a simple new proof of a known lower bound for sampling disjoint sets using two-party communication protocols (Göös and Watson, RANDOM'19).

We consider the problem of extracting randomness from sumset sources, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An (n,k,C)-sumset source X is a distribution on {0,1}n of the form X1 + X2 + … + XC, where Xi’s are independent sources on n bits with min-entropy at least k. Prior extractors either required the number of sources C to be a large constant or the min-entropy k to be at least 0.51 n.

We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [Chattopadhyay et al., 2019; Eshan Chattopadhyay et al., 2019] that exploit L₁ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the k-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with k. This interpolates previous works, which either require Fourier bounds on all levels [Chattopadhyay et al., 2019], or have polynomial dependence on the error parameter in the seed length [Eshan Chattopadhyay et al., 2019], and thus answers an open question in [Eshan Chattopadhyay et al., 2019]. As an example, we show that for polynomial error, Fourier bounds on the first O(log n) levels is sufficient to recover the seed length in [Chattopadhyay et al., 2019], which requires bounds on the entire tail. We obtain our results by an alternate analysis of fractional PRGs using Taylor’s theorem and bounding the degree-k Lagrange remainder term using multilinearity and random restrictions. Interestingly, our analysis relies only on the level-k unsigned Fourier sum, which is potentially a much smaller quantity than the L₁ notion in previous works. By generalizing a connection established in [Chattopadhyay et al., 2020], we give a new reduction from constructing PRGs to proving correlation bounds. Finally, using these improvements we show how to obtain a PRG for 𝔽₂ polynomials with seed length close to the state-of-the-art construction due to Viola [Emanuele Viola, 2009].

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 (STOC'06), and falls into a line of research initiated by Trevisan and Vadhan (FOCS'00) 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$k\geq s. \text{polylog} (n)$entropy. This is an exponential improvement over the previous best result, which required entropy$k\geq s^{1,1}\cdot 2^{\log^{0.51}n}$(Chattopadhyay and Li, STOC'16). 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$k > n^{1/2+\delta}\cdot s^{1/2-\delta}$, whereas the previous best result required$k > n^{2/3+\delta}\cdot s^{1/3-\delta}$(Chattopadhyay, Goodman, Goyal and Li, STOC'20). 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.

We give an explicit construction of an affine extractor (over$\mathbb{F}_{2}$) that works for affine sources on$n$bits with min-entropy$k\geq\log n\cdot(\log\log n)^{1+o(1)}$. This improves prior work of Li (FOCS'16) that requires min-entropy at least$\text{poly} (\log n)$. Our construction is based on the framework of using correlation breakers and resilient functions, a paradigm that was also used by Li. On a high level, the key sources of our improvement are based on the following new ingredients: (i) A new construction of an affine somewhere random extractor, that we use in a crucial step instead of a linear seeded extractor (for which optimal constructions are not known) that was used by Li. (ii) A near optimal construction of a correlation breaker for linearly correlated sources. The construction of our correlation breaker takes inspiration from an exciting line of recent work that constructs two-source extractors for near logarithmic min-entropy.

In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs). BCPs are multiparty communication protocols in which N parties, holding n bits each, attempt to compute some joint function of their inputs, f:({0,1}n)N→{0,1}. In each round, p parties (the collusion bound) work together to write a single bit on a public blackboard, and the protocol continues until every party knows the value of f. BCPs are a natural generalization of the well-studied number-in-hand (NIH) and number-on-forehead (NOF) models, which are just endpoints on this rich spectrum of protocols (corresponding to p=1 and p=N-1, respectively). In this work, we investigate BCPs more thoroughly, and answer questions about them in the context of communication complexity, randomness extractors, and secret sharing. 1.First, we provide explicit lower bounds against BCPs. Our lower bounds offer a tradeoff between collusion and complexity, and are of the form nΩ(1)when p=0.99N parties collude. This bound is independent of the relationship between N, n, whereas all previous bounds became trivial when . 2.Second, we provide explicit leakage-resilient extractors against BCPs. Also known as cylinder-intersection extractors, these objects are multi-source extractors of the form Ext: ({0,1}n)N→{0,1}, whose output looks uniform even conditioned on the bits produced (“leaked”) by a BCP executed over the inputs of the extractor. Our extractors work for sources with min-entropy k ≥ polylog(n) against BCPs with collusion p ≤ N-2. Previously, all such extractors required min-entropy k ≥ 0.99n even when p ≤ O(1). 3.Third, we provide efficient leakage-resilient secret sharing schemes against BCPs. These cryptographic primitives are standard t-out-of- N secret sharing schemes, equipped with an additional guarantee that the secret remains hidden even if the individuals participate in a BCP using their shares. Our schemes can handle collusion up to p ≤ O(t/logt), whereas the previous best scheme required p ≤ O(logN). Along the way, we also construct objects that are more general than those listed above (i.e., compilers), objects that are more specialized (and stronger) than those listed above, and resolve open questions posed by Goyal and Kumar (STOC 2018) and Kumar, Meka, and Sahai (FOCS 2019).

Randomness extraction is a fundamental problem that has been studied for over three decades. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples with no entropy at all or with unwanted dependence. Motivated by this and applications from cryptography, we initiate a systematic study of randomness extraction for the class of adversarial sources defined as follows.

A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over F2. We introduce a new technique to prove such correlation bounds with F2 polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In fact, we prove a more general XOR lemma that extends to arbitrary resilient functions. We conjecture that the technique generalizes to higher degree polynomials as well.

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper-resilient cryptography. These are seeded nonmalleable extractors, introduced by Dodis and Wichs (STOC 2009); seedless nonmalleable extractors, introduced by Cheraghchi and Guruswami (TCC 2014); and nonmalleable codes, introduced by Dziembowski, Pietrzak, and Wichs ( J. ACM, 2018). Besides being interesting on their own, they also have important applications in cryptography, e.g., privacy amplification with an active adversary, explicit nonmalleable codes, etc., and often have unexpected connections to their nontampered analogues. However, the known constructions are far behind their nontampered counterparts. Indeed, the best known seeded nonmalleable extractor requires min-entropy rate at least 0.49 [X. Li, in Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012, pp. 688--697], while explicit construction of nonmalleable two-source extractors was not known even if both sources have full min-entropy and was left as an open problem in [M. Cheraghchi and V. Guruswami, J. Cryptology, 30 (2017), pp. 191--241]. In this paper we make progress towards solving the above problems and other related generalizations. Our contributions are as follows: (i) We construct an explicit seeded nonmalleable extractor for min-entropy $k \geq \log^2 n$. This dramatically improves all previous results and gives a simpler two-round privacy amplification protocol with optimal entropy loss, matching the best known result in [X. Li, in Theory of Cryptography (TCC 2015), Springer, 2015, pp. 502--531]. In fact, we construct more general seeded nonmalleable extractors (that can handle multiple adversaries) which were used in the recent construction of explicit two-source extractors for polylogarithmic min-entropy [E. Chattopadhyay and D. Zuckerman, Ann. of Math. (2), 189 (2019), pp. 653--705]. (ii) We construct the first explicit nonmalleable two-source extractor for min-entropy $k \geq n-n^{\Omega(1)}$, with output size $n^{\Omega(1)}$ and error $2^{-n^{\Omega(1)}}$, thus resolving the open question in [M. Cheraghchi and V. Guruswami, J. Cryptology, 30 (2017), pp. 191--241]. (iii) We motivate and initiate the study of two natural generalizations of seedless nonmalleable extractors and nonmalleable codes, where the sources or the codeword may be tampered many times. For this, we construct the first explicit nonmalleable two-source extractor with tampering degree $t$ up to $n^{\Omega(1)}$. By using the connection in [M. Cheraghchi and V. Guruswami, J. Cryptology, 30 (2017), pp. 191--241] and providing efficient sampling algorithms, we obtain the first explicit nonmalleable codes with tampering degree $t$ up to $n^{\Omega(1)}$. We call these stronger notions one-many and many-many nonmalleable codes. This provides a stronger information theoretic analogue of a primitive known as continuous nonmalleable codes. Our basic technique used in all of our constructions can be seen as inspired, in part, by the techniques previously used to construct cryptographic nonmalleable commitments.

We show that a very simple pseudorandom generator fools intersections of k linear threshold functions (LTFs) and arbitrary functions of k LTFs over n-dimensional Gaussian space. The two analyses of our PRG (for intersections versus arbitrary functions of LTFs) are quite different from each other and from previous analyses of PRGs for functions of halfspaces. Our analysis for arbitrary functions of LTFs establishes bounds on the Wasserstein distance between Gaussian random vectors with similar covariance matrices, and combines these bounds with a conversion from Wasserstein distance to "union-of-orthants" distance from [Xi Chen et al., 2014]. Our analysis for intersections of LTFs uses extensions of the classical Sudakov-Fernique type inequalities, which give bounds on the difference between the expectations of the maxima of two Gaussian random vectors with similar covariance matrices. For all values of k, our generator has seed length O(log n) + poly(k) for arbitrary functions of k LTFs and O(log n) + poly(log k) for intersections of k LTFs. The best previous result, due to [Gopalan et al., 2010], only gave such PRGs for arbitrary functions of k LTFs when k=O(log log n) and for intersections of k LTFs when k=O((log n)/(log log n)). Thus our PRG achieves an O(log n) seed length for values of k that are exponentially larger than previous work could achieve. By combining our PRG over Gaussian space with an invariance principle for arbitrary functions of LTFs and with a regularity lemma, we obtain a deterministic algorithm that approximately counts satisfying assignments of arbitrary functions of k general LTFs over {0,1}^n in time poly(n) * 2^{poly(k,1/epsilon)} for all values of k. This algorithm has a poly(n) runtime for k =(log n)^c for some absolute constant c>0, while the previous best poly(n)-time algorithms could only handle k = O(log log n). For intersections of LTFs, by combining these tools with a recent PRG due to [R. O'Donnell et al., 2018], we obtain a deterministic algorithm that can approximately count satisfying assignments of intersections of k general LTFs over {0,1}^n in time poly(n) * 2^{poly(log k, 1/epsilon)}. This algorithm has a poly(n) runtime for k =2^{(log n)^c} for some absolute constant c>0, while the previous best poly(n)-time algorithms for intersections of k LTFs, due to [Gopalan et al., 2010], could only handle k=O((log n)/(log log n)).

A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design an alternative pseudorandom generator that only requires bounds on the second level of the Fourier tails. It is based on a derandomization of the work of Raz and Tal (ECCC 2018) who used the above framework to obtain an oracle separation between BQP and PH. As an application, we give a concrete conjecture for bounds on the second level of the Fourier tails for low degree polynomials over the finite field F_2. If true, it would imply an efficient pseudorandom generator for AC^0[oplus], a well-known open problem in complexity theory. As a stepping stone towards resolving this conjecture, we prove such bounds for the first level of the Fourier tails.

We propose a new framework for constructing pseudorandom generators for n-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in [-1,1]^n. Next, we use a fractional pseudorandom generator as steps of a random walk in [-1,1]^n that converges to {-1,1}^n. We prove that this random walk converges fast (in time logarithmic in n) due to polarization. As an application, we construct pseudorandom generators for Boolean functions with bounded Fourier tails. We use this to obtain a pseudorandom generator for functions with sensitivity s, whose seed length is polynomial in s. Other examples include functions computed by branching programs of various sorts or by bounded depth circuits.

We present an explicit pseudorandom generator with seed length Õ((logn)w+1) for read-once, oblivious, width w branching programs that can read their input bits in any order. This improves upon the work of Impagliazzo, Meka and Zuckerman (FOCS’12) where they required seed length n1/2+o(1).

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs as an elegant relaxation of error correcting codes, where the motivation is to handle more general forms of tampering while still providing meaningful guarantees. This has led to many elegant constructions and applications in cryptography. However, most works so far only studied tampering in the split-state model where different parts of the codeword are tampered independently, and thus do not apply to many other natural classes of tampering functions. The only exceptions are the work of Agrawal et al. which studied non-malleable codes against bit permutation composed with bit-wise tampering, and the works of Faust et al. and Ball et al., which studied non-malleable codes against local functions. However, in both cases each tampered bit only depends on a subset of input bits.

We study how to extract randomness from a C-interleaved source, that is, a source comprised of C independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields: (1) For some delta>0, c>0, explicit extractors for 2-interleaved sources on {0,1}^{2n} when one source has min-entropy at least (1-delta)*n and the other has min-entropy at least c*log(n). The best previous construction, by Raz and Yehudayoff, worked only when both sources had entropy rate 1-delta. (2) For some c>0 and any large enough prime p, explicit extractors for 2-interleaved sources on [p]^{2n} when one source has min-entropy rate at least .51 and the other source has min-entropy rate at least (c*log(n))/n. We use these to obtain the following applications: (a) We introduce the class of any-order-small-space sources, generalizing the class of small-space sources studied by Kamp et al.. We construct extractors for such sources with min-entropy rate close to 1/2. Using the Raz-Yehudayoff construction would require entropy rate close to 1. (b) For any large enough prime p, we exhibit an explicit function f:[p]^{2n} -> {0,1} such that the randomized best-partition communication complexity of f with error 1/2-2^{-Omega(n)} is at least .24*n*log(p). Previously this was known only for a tiny constant instead of .24, for p=2 by by Raz and Yehudayoff. We introduce non-malleable extractors in the interleaved model. For any large enough prime p, we give an explicit construction of a weak-seeded non-malleable extractor for sources over [p]^n with min-entropy rate .51. Nothing was known previously, even for almost full min-entropy.

We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors, 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter, 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic). For the first two problems, the best known non-malleable extractors by Chattopadhyay, Goyal and Li, and by Cohen all require seed length and min-entropy with quadratic loss in parameters. As a result, the best known explicit privacy amplification protocols with an active adversary, which achieve two rounds of communication and optimal entropy loss was sub-optimal in the min-entropy of the source. In this paper we give an explicit non-malleable extractor that works for nearly optimal seed length and min-entropy, and yields a two-round privacy amplification protocol with optimal entropy loss for almost all ranges of the security parameter. For the third problem, we improve upon a very recent result by Cohen and Schulman and give an explicit extractor that uses an absolute constant number of sources, each with almost logarithmic min-entropy. The key ingredient in all our constructions is a generalized, and much more efficient version of the independence preserving merger introduced by Cohen, which we call non-malleable independence preserving merger. Our construction of the merger also simplifies that of Cohen and Schulman, and may be of independent interest.

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-malleable extractors, introduced by Dodis and Wichs; seedless non-malleable extractors, introduced by Cheraghchi and Guruswami; and non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs. Besides being interesting on their own, they also have important applications in cryptography, e.g, privacy amplification with an active adversary, explicit non-malleable codes etc, and often have unexpected connections to their non-tampered analogues.

We propose a new model of weak random sources which we call sumset sources. A sumset source X is the sum of C independent sources, with each source on n bits source having min-entropy k. We show that extractors for this class of sources can be used to give extractors for most classes of weak sources that have been studied previously, including independent sources, affine sources (which generalizes oblivious bit-fixing sources), small space sources, total entropy independent sources, and interleaved sources. This provides a unified approach for randomness extraction.

We explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least $\mathrm{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 min-entropy $.499n$. M A key ingredient in our construction is an explicit construction of a monotone, almost-balanced Boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$ for any $\delta>0$. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown $n-q$ bits are chosen almost $\mathrm{polylog}(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola, achieved $q=n^{1/2-\delta}$. Our explicit two-source extractor directly implies an explicit construction of a $2^{(\mathrm{log}\ \mathrm{log}\ N)^{O(1)}}$-Ramsey graph over $N$ vertices, improving bounds obtained by Barak et al. and matching an independent work by Cohen.

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs [1] as an elegant generalization of the classical notions of error detection, where the corruption of a codeword is viewed as a tampering function acting on it. Informally, a non-malleable code with respect to a family of tampering functions F consists of a randomized encoding function Enc and a deterministic decoding function Dec such that for any m, Dec(Enc(m)) = m. Further, for any tampering function f ∈ F and any message m, Dec(f(Enc(m))) is either m or is ∈-close to a distribution Dfindependent of m, where ∈ is called the error. Of particular importance are non-malleable codes in the C-split-state model. In this model, the codeword is partitioned into C equal sized blocks and the tampering function family consists of functions (f1, . . . , fC) such that fi acts on the ith block. For C = 1 there cannot exist non-malleable codes. For C = 2, the best known explicit construction is by Aggarwal, Dodis and Lovett [2] who achieve rate = Ω(n-6/7) and error = 2-Ω(n-1/7), where n is the block length of the code. In our main result, we construct efficient non-malleable codes in the C-split-state model for C = 10 that achieve constant rate and error = 2-Ω(n). These are the first explicit codes of constant rate in the C-split-state model for any C = o(n), that do not rely on any unproven assumptions. We also improve the error in the explicit nonmalleable codes constructed in the bit tampering model by Cheraghchi and Guruswami [3]. Our constructions use an elegant connection found between seedless non-malleable extractors and non-malleable codes by Cheraghchi and Guruswami [3]. We explicitly construct such seedless non-malleable extractors for 10 independent sources and deduce our results on non-malleable codes based on this connection. Our constructions of extractors use encodings and a new variant of the sumproduct theorem.