Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with pseudorandom generators:
TR01-020 | 20th February 2001
N. S. Narayanaswamy, C.E. Veni Madhavan

Lower Bounds for OBDDs and Nisan's pseudorandom generator

We present a new boolean function for which any Ordered Binary
Decision Diagram (OBDD) computing it has an exponential number
of nodes. This boolean function is obtained from Nisan's
pseudorandom generator to derandomize space bounded randomized
algorithms. Though the relation between hardness and randomness for
computational models is well ... more >>>

TR03-013 | 7th March 2003
Luca Trevisan

An epsilon-Biased Generator in NC0

Comments: 1

Cryan and Miltersen recently considered the question
of whether there can be a pseudorandom generator in
NC0, that is, a pseudorandom generator such that every
bit of the output depends on a constant number k of bits
of the seed. They show that for k=3 there ... more >>>

TR03-043 | 14th May 2003
Elchanan Mossel, Amir Shpilka, Luca Trevisan

On epsilon-Biased Generators in NC0

Cryan and Miltersen recently considered the question
of whether there can be a pseudorandom generator in
NC0, that is, a pseudorandom generator such that every
bit of the output depends on a constant number k of bits
of the seed. They show that for k=3 there is always a
distinguisher; ... more >>>

TR04-002 | 8th January 2004
Troy Lee, Dieter van Melkebeek, Harry Buhrman

Language Compression and Pseudorandom Generators

The language compression problem asks for succinct descriptions of
the strings in a language A such that the strings can be efficiently
recovered from their description when given a membership oracle for
A. We study randomized and nondeterministic decompression schemes
and investigate how close we can get to the information ... more >>>

TR04-019 | 15th January 2004
Christian Gla├čer, A. Pavan, Alan L. Selman, Samik Sengupta

Properties of NP-Complete Sets

We study several properties of sets that are complete for NP.
We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is many-one-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$
such ... more >>>

TR04-083 | 8th September 2004
Boaz Barak, Yehuda Lindell, Salil Vadhan

Lower Bounds for Non-Black-Box Zero Knowledge

We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:
<li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ... more >>>

TR05-012 | 17th January 2005
Luca Trevisan, Salil Vadhan, David Zuckerman

Compression of Samplable Sources

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n).

1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1).

Our next ... more >>>

TR05-092 | 23rd August 2005
Eyal Rozenman, Salil Vadhan

Derandomized Squaring of Graphs

We introduce a "derandomized" analogue of graph squaring. This
operation increases the connectivity of the graph (as measured by the
second eigenvalue) almost as well as squaring the graph does, yet only
increases the degree of the graph by a constant factor, instead of
squaring the degree.

One application of ... more >>>

TR05-114 | 9th October 2005
Boaz Barak, Shien Jin Ong, Salil Vadhan

Derandomization in Cryptography

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct:

A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any ... more >>>

TR05-135 | 19th November 2005
Iftach Haitner, Danny Harnik, Omer Reingold

On the Power of the Randomized Iterate

We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad et. al. [HILL99], is that pseudorandom generators can be constructed from any one-way function. The second due to Yao [Yao82] states that the existence of weak one-way functions (i.e. functions on which every efficient algorithm ... more >>>

TR06-003 | 8th January 2006
Joshua Buresh-Oppenheim, Rahul Santhanam

Making Hard Problems Harder

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

TR07-075 | 9th August 2007
Shachar Lovett

Unconditional pseudorandom generators for low degree polynomials

We give an explicit construction of pseudorandom
generators against low degree polynomials over finite fields. We
show that the sum of $2^d$ small-biased generators with error
$\epsilon^{2^{O(d)}}$ is a pseudorandom generator against degree $d$
polynomials with error $\epsilon$. This gives a generator with seed
length $2^{O(d)} \log{(n/\epsilon)}$. Our construction follows ... more >>>

TR08-007 | 6th February 2008
Dan Gutfreund, Salil Vadhan

Limitations of Hardness vs. Randomness under Uniform Reductions

We consider (uniform) reductions from computing a function f to the task of distinguishing the output of some pseudorandom generator G from uniform. Impagliazzo and Wigderson (FOCS `98, JCSS `01) and Trevisan and Vadhan (CCC `02, CC `07) exhibited such reductions for every function f in PSPACE. Moreover, their reductions ... more >>>

TR09-144 | 24th December 2009
Prahladh Harsha, Adam Klivans, Raghu Meka

An Invariance Principle for Polytopes

Let $X$ be randomly chosen from $\{-1,1\}^n$, and let $Y$ be randomly
chosen from the standard spherical Gaussian on $\R^n$. For any (possibly unbounded) polytope $P$
formed by the intersection of $k$ halfspaces, we prove that
$$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k ... more >>>

TR10-113 | 16th July 2010
Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak

Pseudorandom Generators for Group Products

We prove that the pseudorandom generator introduced in Impagliazzo et al. (1994) fools group products of a given finite group. The seed length is $O(\log n \log 1 / \epsilon)$, where $n$ is the length of the word and $\epsilon$ is the error. The result is equivalent to the statement ... more >>>

TR10-129 | 16th August 2010
Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of "typically-correct" deterministic simulations, which are allowed to err on few inputs. In this paper we further the study of typically-correct derandomization in two ways.

First, we ... more >>>

TR10-176 | 15th November 2010
Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

Pseudorandom Generators for Combinatorial Shapes

Revisions: 1

We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, small-bias spaces, 0/1 halfspaces, and 0/1 modular sums. A function $f:[m]^n \rightarrow \{0,1\}^n$ is an $(m,n)$-combinatorial shape if there exist sets $A_1,\ldots,A_n \subseteq [m]$ and a symmetric function $h:\{0,1\}^n \rightarrow \{0,1\}$ such that $f(x_1,\ldots,x_n) = h(1_{A_1} (x_1),\ldots,1_{A_n}(x_n))$. Our ... more >>>

TR12-080 | 18th June 2012
Baris Aydinlioglu, Dieter van Melkebeek

Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games

In several settings derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in *any* way implies ... more >>>

TR12-123 | 28th September 2012
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

Better pseudorandom generators from milder pseudorandom restrictions

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near optimal seed-length even in ... more >>>

TR13-143 | 19th October 2013
Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman

Robust Pseudorandom Generators

Revisions: 1

Let $G:\{0,1\}^n\to\{0,1\}^m$ be a pseudorandom generator. We say that a circuit implementation of $G$ is $(k,q)$-robust if for every set $S$ of at most $k$ wires anywhere in the circuit, there is a set $T$ of at most $q|S|$ outputs, such that conditioned on the values of $S$ and $T$ ... more >>>

TR13-155 | 10th November 2013
Gil Cohen, Amnon Ta-Shma

Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

Revisions: 2

Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a pseudorandom generator for degree d polynomials in n variables, over any prime field. The seed length used is $O(d \log{n} + d 2^d)$, ... more >>>

TR13-175 | 6th December 2013
Venkatesan Guruswami, Chaoping Xing

Hitting Sets for Low-Degree Polynomials with Optimal Density

Revisions: 1

We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding $n$-variate degree-$d$ polynomials over ${\mathbb F}_q$ with $q \ge \Omega(d/\delta)$, we present an explicit (multi)-set $S \subseteq {\mathbb F}_q^n$ of size $N=\mathrm{poly}(n^d/\delta)$ such that every nonzero polynomial vanishes on at most ... more >>>

TR15-027 | 25th February 2015
Benny Applebaum

Cryptographic Hardness of Random Local Functions -- Survey

Revisions: 1

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

TR15-051 | 5th April 2015
Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterminsitic Reductions

Revisions: 2

A circuit $C$ \emph{compresses} a function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ if given an input $x\in \{0,1\}^n$ the circuit $C$ can shrink $x$ to a shorter $\ell$-bit string $x'$ such that later, a computationally-unbounded solver $D$ will be able to compute $f(x)$ based on $x'$. In this paper we study the existence of ... more >>>

TR15-193 | 26th November 2015
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket

On the hardness of learning sparse parities

This work investigates the hardness of computing sparse solutions to systems of linear equations over $\mathbb{F}_2$. Consider the $k$-EvenSet problem: given a homogeneous system of linear equations over $\mathbb{F}_2$ on $n$ variables, decide if there exists a nonzero solution of Hamming weight at most $k$ (i.e. a $k$-sparse solution). While ... more >>>

TR16-037 | 15th March 2016
Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

Pseudorandomness when the odds are against you

Impagliazzo and Wigderson showed that if $\text{E}=\text{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits, then
every time $T$ constant-error randomized algorithm can be simulated deterministically in time $\poly(T)$. However, such polynomial slowdown is a deal breaker when $T=2^{\alpha \cdot n}$, for a constant $\alpha>0$, as is the case for some randomized algorithms for ... more >>>

TR16-134 | 29th August 2016
Ronen Shaltiel, Jad Silbak

Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels

A stochastic code is a pair of encoding and decoding procedures $(Enc,Dec)$ where $Enc:\{0,1\}^k \times \{0,1\}^d \to \{0,1\}^n$, and a message $m \in \{0,1\}^k$ is encoded by $Enc(m,S)$ where $S \from \{0,1\}^d$ is chosen uniformly by the encoder. The code is $(p,L)$-list-decodable against a class $\mathcal{C}$ of ``channel functions'' $C:\{0,1\}^n ... more >>>

TR17-060 | 9th April 2017
Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari

Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

Revisions: 1

We prove that for every function $G\colon\{0,1\}^n \rightarrow \mathbb{R}^m$, if every output of $G$ is a polynomial (over $\mathbb{R}$) of degree at most $d$ of at most $s$ monomials and $m > \widetilde{O}(sn^{\lceil d/2 \rceil})$, then there is a polynomial time algorithm that can distinguish a vector of the form ... more >>>

TR17-161 | 30th October 2017
Mark Braverman, Gil Cohen, Sumegha Garg

Hitting Sets with Near-Optimal Error for Read-Once Branching Programs

Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$, width $n$ read-once branching programs (ROBPs) with error $\varepsilon$ and seed length $O(\log^2{n} + \log{n} \cdot \log(1/\varepsilon))$. A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal $O(\log{n}+\log(1/\varepsilon))$, or to construct improved hitting sets, as ... more >>>

TR17-171 | 6th November 2017
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

Revisions: 1

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{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 Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work ... more >>>

TR18-015 | 25th January 2018
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

Pseudorandom Generators from Polarizing Random Walks

Revisions: 1 , Comments: 1

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]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that ... more >>>

TR18-115 | 11th June 2018
Valentine Kabanets, Zhenjian Lu

Satisfiability and Derandomization for Small Polynomial Threshold Circuits

A polynomial threshold function (PTF) is defined as the sign of a polynomial $p\colon\bool^n\to\mathbb{R}$. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth.

Satisfiability (#SAT). We give the first zero-error randomized algorithm ... more >>>

ISSN 1433-8092 | Imprint