Search for: All records

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 \cite{aggarwal_how_2020}), and almost Chor-Goldreich (CG) sources as defined in \cite{doron_almost_2023}. We will think of these sources as a sequence of random variables $$\mathbf{X}=\mathbf{X}_1,\dots,\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)$$-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 \cite{doron_almost_2023}, where they explicitly construct a seedless condenser for a restricted subset of $$(g,\ell)$$-adversarial CG sources. The following are our main results concerning seedless condensers for each of these sources. \begin{enumerate} \item oNOSF sources \begin{enumerate} \item 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. \item 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 \emph{output-light two-source extractors}, that we introduce and prove the existence of. \end{enumerate} \item Adversarial CG sources \begin{enumerate} \item We observe that uniform adversarial CG sources are equivalent to uniform oNOSF sources and consequently inherit the same results. \item 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$$. \end{enumerate} \item NOSF sources \begin{enumerate} \item 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. \end{enumerate} \end{enumerate} 

In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Their result is based on a clever modification to the inverse Laplacian perspective of space-bounded derandomization, which was originally introduced by Ahmadinejad, Kelner, Murtagh, Peebles, Sidford and Vadhan (FOCS 2020). In this work, we give an alternative error reduction framework for regular ROBPs. Our new framework is based on a binary recursive formula from the work of Chattopadhyay and Liao (CCC 2020), that they used to construct weighted pseudorandom generators (WPRGs) for general ROBPs. Based on our new error reduction framework, we give alternative proofs to the following results for regular ROBPs of length n and width w, both of which were proved in the work of Chen et al. using their error reduction: - There is a WPRG with error ε that has seed length Õ(log(n)(√{log(1/ε)}+log(w))+log(1/ε)). - There is a (non-black-box) deterministic algorithm which estimates the expectation of any such program within error ±ε with space complexity Õ(log(nw)⋅log log(1/ε)). This was first proved in the work of Ahmadinejad et al., but the proof by Chen et al. is simpler. Because of the binary recursive nature of our new framework, both of our proofs are based on a straightforward induction that is arguably simpler than the Laplacian-based proof in the work of Chen et al. In fact, because of its simplicity, our proof of the second result directly gives a slightly stronger claim: our algorithm computes a ε-singular value approximation (a notion of approximation introduced in a recent work by Ahmadinejad, Peebles, Pyne, Sidford and Vadhan (FOCS 2023)) of the random walk matrix of the given ROBP in space Õ(log(nw)⋅log log(1/ε)). It is not clear how to get this stronger result from the previous proofs. 

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. 

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. 

The area of randomness extraction has seen interesting advances in recent years, with rapid progress on many longstanding open problems, along with the introduction of many new notions that played a key role in this development. We survey this progress and highlight new definitions and notions that have been the subject of intense study in recent work.