Due to the fact that classical computers cannot efficiently obtain random numbers, it is common practice to design cryptosystems in terms of real random numbers and then replace them with cryptographically secure pseudorandom ones for concrete ...

We give PRG for depth-d, size-m AC⁰ circuits with seed length O(log^d−1 (m) log(m/ε) log log(m)). Our PRG improves on previous work [27, 25, 18] from various aspects. It has optimal dependence on 1/ε and is only one "log log(m)" away from the lower bound ...

Following the paper of Alekhnovich, Ben-Sasson, Razborov, Wigderson [2] we call a pseudorandom generator F: (0, 1}ⁿ → (0, 1}^m hard for a propositional proof system P if P cannot efficiently prove the (properly encoded) statement b ∉ Im(F) for any string ...

NIST SP800-22 (2010) proposed the state of the art statistical testing techniques for testing the quality of (pseudo) random generators. However, it is easy to construct natural functions that are considered as GOOD pseudorandom generators by the ...

We give a pseudorandom generator that fools m-facet polytopes over {0, 1}ⁿ with seed length polylog(m) · log n. The previous best seed length had superlinear dependence on m.

We give a randomness-efficient Massively Parallel Computation (MPC) algorithm for deciding whether an undirected graph is connected. For Connectivity on n-vertex, m-edge graphs whose components have diameter at most D = 2o(log n/ log log n), our ...

Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [5], are a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered, rather than a probability mass. Braverman et al. constructed ...

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 ...

We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of BPTIME: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows.

In a recent breakthrough, [C. Murray and R. R. Williams, STOC 2018, ACM, New York, 2018, pp. 890--901] proved that ${NQP} = {NTIME}[n^{{polylog}(n)}]$ cannot be computed by polynomial-size ${ACC}^0$ circuits (constant-depth circuits consisting of ${AND}$/...

Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. We prove under a precise version of this ...

There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The "iterated restrictions" approach, pioneered by Ajtai and Wigderson [2], has provided PRGs with seed length polylog n or even Õ(log n) for several ...

We study the Fourier spectrum of functions f: {0, 1}^mk → { -1, 0, 1} which can be written as a product of k Boolean functions f_i on disjoint m-bit inputs. We prove that for every positive integer d,

[EQUATION]

Our upper bounds are tight up to a constant ...

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 ...

We give an explicit pseudorandom generator (PRG) for read-once AC⁰, i.e., constant-depth read-once formulas over the basis [EQUATION] with unbounded fan-in. The seed length of our PRG is Õ(log(n/ε)). Previously, PRGs with near-optimal seed length were ...

We give a pseudorandom generator that fools m-facet polytopes over {0,1}ⁿ with seed length polylog(m) · log(n). The previous best seed length had superlinear dependence on m. An immediate consequence is a deterministic quasipolynomial time algorithm for ...

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]ⁿ. ...

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 ...

Let $D$ be a $b$-wise independent distribution over $\{0,1\}^m$. Let $E$ be the “noise” distribution over $\{0,1\}^m$ where the bits are independent and each bit is 1 with probability $\eta/2$. We study which tests $f \colon \{0,1\}^m \to [-1,1]$ are $\...

Suppose that you have $n$ truly random bits $x=(x_1,\ldots,x_n)$ and you wish to use them to generate $m\gg n$ pseudorandom bits $y=(y_1,\ldots, y_m)$ using a local mapping, i.e., each $y_i$ should depend on at most $d=O(1)$ bits of $x$. In the polynomial ...