Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PSEUDORANDOM GENERATORS:
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:
<ol>
<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 Revisions: 1 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 Revisions: 1 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 >>> TR18-145 | 13th August 2018 Ryan O'Donnell, Rocco Servedio, Li-Yang Tan #### Fooling Polytopes We give a pseudorandom generator that fools m-facet polytopes over \{0,1\}^n with seed length \mathrm{polylog}(m) \cdot \log n. The previous best seed length had superlinear dependence on m. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any \{0,1\}-integer program. more >>> TR18-147 | 19th August 2018 Michael Forbes, Zander Kelley #### Pseudorandom Generators for Read-Once Branching Programs, in any Order A central question in derandomization is whether randomized logspace (RL) equals deterministic logspace (L). To show that RL=L, it suffices to construct explicit pseudorandom generators (PRGs) that fool polynomial-size read-once (oblivious) branching programs (roBPs). Starting with the work of Nisan, pseudorandom generators with seed-length O(\log^2 n) were constructed. Unfortunately, ... more >>> TR19-017 | 6th February 2019 Chin Ho Lee #### Fourier bounds and pseudorandom generators for product tests We study the Fourier spectrum of functions f\colon \{0,1\}^{mk} \to \{-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, $\sum_{S \subseteq [mk]: |S|=d} |\hat{f_S}| = O(m)^d .$ Our upper bound ... more >>> TR19-099 | 29th July 2019 Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman #### Nearly Optimal Pseudorandomness From Hardness Revisions: 3 Existing proofs that deduce \mathbf{BPP}=\mathbf{P} from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length n running in ... more >>> TR19-155 | 6th November 2019 Rahul Santhanam #### Pseudorandomness and the Minimum Circuit Size Problem We explore the possibility of basing one-way functions on the average-case hardness of the fundamental Minimum Circuit Size Problem (MCSP[s]), which asks whether a Boolean function on n bits specified by its truth table has circuits of size s(n). 1. (Pseudorandomness from Zero-Error Average-Case Hardness) We show that for ... more >>> TR20-103 | 9th July 2020 Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida #### One-Tape Turing Machine and Branching Program Lower Bounds for MCSP Revisions: 1 For a size parameter s\colon\mathbb{N}\to\mathbb{N}, the Minimum Circuit Size Problem (denoted by {\rm MCSP}[s(n)]) is the problem of deciding whether the minimum circuit size of a given function f \colon \{0,1\}^n \to \{0,1\} (represented by a string of length N := 2^n) is at most a threshold s(n). A ... more >>> TR21-009 | 1st February 2021 Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich #### One-way Functions and Partial MCSP Revisions: 3 , Comments: 1 One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence ... more >>> TR21-018 | 20th February 2021 Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan #### Monotone Branching Programs: Pseudorandomness and Circuit Complexity Revisions: 1 We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state. We prove that constant-width monotone branching programs of ... more >>> TR21-039 | 15th March 2021 Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam #### Pseudodeterministic Algorithms and the Structure of Probabilistic Time 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. 1. A new pseudorandom generator and its consequences: We build on techniques developed to ... more >>> TR21-076 | 4th June 2021 Dmitry Sokolov #### Pseudorandom Generators, Resolution and Heavy Width Revisions: 1 Following the paper of Alekhnovich, Ben-Sasson, Razborov, Wigderson \cite{ABRW04} we call a pseudorandom generator \mathrm{PRG}\colon \{0, 1\}^n \to \{0, 1\}^m hard for for a propositional proof system \mathrm{P} if \mathrm{P} cannot efficiently prove the (properly encoded) statement b \notin \mathrm{Im}(\mathrm{PRG}) for any string b \in \{0, 1\}^m. In \cite{ABRW04} authors ... more >>> TR21-087 | 22nd June 2021 Uma Girish, Ran Raz #### Eliminating Intermediate Measurements using Pseudorandom Generators Revisions: 1 We show that quantum algorithms of time T and space S \ge \log T with intermediate measurements can be simulated by quantum algorithms of time T\cdot \mathrm{poly}(S) and space O(S\cdot \log T) without intermediate measurements. The best simulations prior to this work required either \Omega(T) space (by the deferred measurement ... more >>> TR21-153 | 9th November 2021 Ronen Shaltiel, Emanuele Viola #### On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization The hardness vs.~randomness paradigm aims to explicitly construct pseudorandom generators G:\{0,1\}^r \to \{0,1\}^m that fool circuits of size m, assuming the existence of explicit hard functions. A high-end PRG'' with seed length r=O(\log m) (implying BPP=P) was achieved in a seminal work of Impagliazzo and Wigderson (STOC 1997), assuming \textsc{the ... more >>> TR21-171 | 2nd December 2021 Bruno Pasqualotto Cavalar, Zhenjian Lu #### Algorithms and Lower Bounds for Comparator Circuits from Shrinkage Comparator circuits are a natural circuit model for studying bounded fan-out computation whose power sits between nondeterministic branching programs and general circuits. Despite having been studied for nearly three decades, the first superlinear lower bound against comparator circuits was proved only recently by Gál and Robere (ITCS 2020), who established ... more >>> TR22-034 | 3rd March 2022 Chin Ho Lee, Edward Pyne, Salil Vadhan #### Fourier Growth of Regular Branching Programs We analyze the Fourier growth, i.e. the L_1 Fourier weight at level k (denoted L_{1,k}), of read-once regular branching programs. We prove that every read-once regular branching program B of width w \in [1,\infty] with s accepting states on n-bit inputs must have its L_{1,k} bounded by$$
\min\left\{ ... more >>>

ISSN 1433-8092 | Imprint