Search for: All records

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree 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 non-degeneracy conditions on the map 𝑓 and the variety 𝑉 , which in particular ensure that the source has enough min-entropy, we extract almost all the min-entropy 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 by-product, 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. 

A Chor–Goldreich (CG) source is a sequence of random variables X = X1 ∘ … ∘ Xt, where each Xi ∼ {0,1}d and Xi has δ d min-entropy conditioned on any fixing of X1 ∘ … ∘ Xi−1. The parameter 0<δ≤ 1 is the entropy rate of the source. We typically think of d as constant and t as growing. We extend this notion in several ways, defining almost CG sources. Most notably, we allow each Xi to only have conditional Shannon entropy δ d. We achieve pseudorandomness results for almost CG sources which were not known to hold even for standard CG sources, and even for the weaker model of Santha–Vazirani sources: We construct a deterministic condenser that on input X, outputs a distribution which is close to having constant entropy gap, namely a distribution Z ∼ {0,1}m for m ≈ δ dt with min-entropy m−O(1). Therefore, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a “one-shot” simulation is needed. Moreover, our construction works in an online manner, since it is based on random walks on expanders. Our main technical contribution is a novel analysis of random walks, which should be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders), starting from a fixed vertex and walking according to X1∘ … ∘ Xt, accumulate most of the entropy in X. 

We initiate the study of generalized AC⁰ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight ≥ k (up to negations of the input bits), which we denote GC⁰(k). The gate set of this class includes biased LTFs like the k-OR (outputs 1 iff ≥ k bits are 1) and k-AND (outputs 0 iff ≥ k bits are 0), and thus can be seen as an interpolation between AC⁰ and TC⁰. We establish a tight multi-switching lemma for GC⁰(k) circuits, which bounds the probability that several depth-2 GC⁰(k) circuits do not simultaneously simplify under a random restriction. We also establish a new depth reduction lemma such that coupled with our multi-switching lemma, we can show many results obtained from the multi-switching lemma for depth-d size-s AC⁰ circuits lifts to depth-d size-s^{.99} GC⁰(.01 log s) circuits with no loss in parameters (other than hidden constants). Our result has the following applications: - Size-2^Ω(n^{1/d}) depth-d GC⁰(Ω(n^{1/d})) circuits do not correlate with parity (extending a result of Håstad (SICOMP, 2014)). - Size-n^Ω(log n) GC⁰(Ω(log² n)) circuits with n^{.249} arbitrary threshold gates or n^{.499} arbitrary symmetric gates exhibit exponentially small correlation against an explicit function (extending a result of Tan and Servedio (RANDOM, 2019)). - There is a seed length O((log m)^{d-1}log(m/ε)log log(m)) pseudorandom generator against size-m depth-d GC⁰(log m) circuits, matching the AC⁰ lower bound of Håstad up to a log log m factor (extending a result of Lyu (CCC, 2022)). - Size-m GC⁰(log m) circuits have exponentially small Fourier tails (extending a result of Tal (CCC, 2017)). 

Existing proofs that deduce BPP = P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown . Specifically, assuming exponential lower bounds against randomized NP ∩ coNP circuits, formally known as randomized SVN circuits, we convert any randomized algorithm over inputs of length n running in time t ≥ n into a deterministic one running in time t 2+α for an arbitrarily small constant α > 0. Such a slowdown is nearly optimal for t close to n , since under standard complexity-theoretic assumptions, there are problems with an inherent quadratic derandomization slowdown. We also convert any randomized algorithm that errs rarely into a deterministic algorithm having a similar running time (with pre-processing). The latter derandomization result holds under weaker assumptions, of exponential lower bounds against deterministic SVN circuits. Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size s with seed length (1+α)log s , under the assumption that there exists a function f ∈ E that requires randomized SVN circuits of size at least 2 (1-α′) n , where α = O (α)′. The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.