We continue the study of pseudorandom generators (PRG) $G:\{0,1\}^n \rightarrow \{0,1\}^m$ in NC0. While it is known that such generators are likely to exist for the case of small sub-linear stretch $m=n+n^{1-\epsilon}$, it remains unclear whether achieving larger stretch such as $m=2n$ or even $m=n+n^2$ is possible. The existence of ... more >>>

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: they can be described by a sparse input-output dependency graph and a small predicate that is applied at each output. Following the works of Cryan and Miltersen ... more >>>

We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs) $H:\{0,1\}^n \rightarrow \{0,1\}^m$. A construction with constant \emph{output locality}, where every bit of the output depends only on a constant number of bits of the input, was established by [Applebaum, Ishai, and Kushilevitz, SICOMP 2006]. However, this ... more >>>

A proof system for a language $L$ is a function $f$ such that Range$(f)$ is exactly $L$. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by ... more >>>

Constant parallel-time cryptography allows to perform complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions that each of their output bits depend on a constant number of input bits. A natural way to obtain local cryptographic constructions is to use \emph{random local functions} in which each ... more >>>

A one-way function is $d$-local if each of its outputs depends on at most $d$ input bits. In (Applebaum, Ishai, and Kushilevitz, FOCS 2004) it was shown that, under relatively mild assumptions, there exist $4$-local one-way functions (OWFs). This result is not far from optimal as it is not hard ... more >>>

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 regime of $m=n^s$, $s>1$, the only known solution, ... more >>>

Contemplating the recently announced 1-local expanders of Viola and Wigderson (ECCC, TR16-129, 2016), one may observe that weaker constructs are well know. For example, one may easily obtain a 4-regular $N$-vertex graph with spectral gap that is $\Omega(1/\log^2 N)$, and similarly a $O(1)$-regular $N$-vertex graph with spectral gap $1/\tildeO(\log N)$.
more >>>

We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let $f\colon\{0,1\}^m\to\{0,1\}^n$ be a Boolean function where each output bit of $f$ depends only on $O(1)$ input bits. Assume the output distribution of $f$ on uniform input bits is close to a uniform distribution $\mathcal D$ with ... more >>>

We characterize the symmetric distributions that can be (approximately) generated by shallow Boolean circuits. More precisely, let $f\colon \{0,1\}^m \to \{0,1\}^n$ be a Boolean function where each output bit depends on at most $d$ input bits. Suppose the output distribution of $f$ evaluated on uniformly random input bits is close ... more >>>