Search Results

We introduce the problem of constructing explicit variety evasive subspace families. Given a family $\mathcal{F}$ of subvarieties of a projective or affine space, a collection $\mathcal{H}$ of projective or affine $k$-subspaces is $(\mathcal{F},ϵ)$-evasive if for every $\mathcal{V}\in \mathcal{F}$, all but at ...$$$\mathcal{}$$\mathcal{}$

This work initiates the systematic study of explicit distributions that are indistinguishable from a single exponential-size combinatorial object. In this we extend the work of Goldreich, Goldwasser and Nussboim (SICOMP 2010) that focused on the ...

We prove that the sum of t boolean-valued random variables sampled by a random walk on a regular expander converges in total variation distance to a discrete normal distribution at a rate of O(λ/t^1/2−o(1)), where λ is the second largest eigenvalue of ...

The arithmetic correlations of two binary half‐ℓ‐sequences with connection integer p^r, which is an odd prime power, are investigated. Possible values (of the arithmetic correlation) are calculated. In particular, if p ≡ 1 (mod 8), the authors ...

A recurring challenge in the theory of pseudorandomness and circuit complexity is the explicit construction of "incompressible strings," i.e. finite objects which lack a specific type of structure or simplicity. In most cases, there is an associated NP ...

We construct improved hitting set generators (HSGs) for ordered (read-once) regular branching programs in two parameter regimes. First, we construct an explicit ε-HSG for unbounded-width regular branching programs with a single accept state with seed ...

We study the pseudorandomness of random walks on expander graphs against tests computed by symmetric functions and permutation branching programs. These questions are motivated by applications of expander walks in the coding theory and derandomization ...

Symmetry of information for time-bounded Kolmogorov complexity is a hypothetical inequality that relates time-bounded Kolmogorov complexity and its conditional analogue. In 1992, Longpré and Watanabe showed that symmetry of information holds if NP is ...

We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent Local algorithm for (degree +1)-list-coloring (D1LC), this allows us to solve D1LC in O(...

In a recent work, O’Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (s) for arbitrary m-facet polytopes in n variables with seed length poly-logarithmic in m,n, concluding a sequence of works in the last decade, that was ...

We give new constructions of two classes of algebraic code families that are efficiently list decodable with small output list size from a fraction 1-R-ε of adversarial errors, where R is the rate of the code, for any desired positive constant ε. The ...

Proving superlogarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early '80s. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $...

A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a weighted pseudorandom generator (WPRG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with real coefficients that scale the acceptance ...

We introduce the problem of constructing explicit variety evasive subspace families. Given a family F of sub varieties of a projective or affine space, a collection H of projective or affine k-subspaces is (F, ϵ)-evasive if for every V ∈ F, all but at ...

We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [4, 6] that exploit L₁ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a ...

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)...

We prove a new derandomization of Håstad’s switching lemma, showing how to efficiently generate restrictions satisfying the switching lemma for DNF or CNF formulas of size m using only O(logm) random bits. Derandomizations of the switching lemma have ...

We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any R ∈ (0,1) and є>0, we give an algebraic construction of an infinite ...

A stochastic code is a pair of encoding and decoding procedures (Enc, Dec) where $\mathrm{Enc}:{\{0,1\}}^k\times {\{0,1\}}^d\to {\{0,1\}}^n$. The code is (p, L)-list decodable against a class $\mathcal{C}$ of “channel functions” $C:{\{0,1\}}^n\to {\{0,1\}}^n$ if for every message $m\in {\{0,1\}}^k$ and every channel $C\in \mathcal{C}$ ...${\mathrm{}\mathrm{}}^{}$$$

We strengthen the notion of double samplers, first introduced by Dinur and Kaufman [``High dimensional expanders imply agreement expanders,” in Proc. 58th IEEE Symp. on Foundations of Comp. Science, IEEE, 2017, pp. 974--985], which are samplers with ...