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