- Pseudorandomness from Shrin...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in May 2014

## Pseudorandomness from Shrinkage

**Speaker:**
David Zuckerman
, Department of Computer Science, The University of Texas at Austin

**Date:**
Tuesday, May 06, 2014

**Time:**
4:15 PM to 5:15 PM
** Note: all times are in the Eastern Time Zone**

**Refreshments:**
3:45 PM

**Public:**
Yes

**Location:**
32-G449

**Event Type:**

**Room Description:**

**Host:**
Ankur Moitra

**Contact:**
Holly A Jones, hjones01@csail.mit.edu

**Relevant URL:**
http://toc.csail.mit.edu/node/487

**Speaker URL:**
None

**Speaker Photo:**

None

**Reminders to:**
seminars@csail.mit.edu, toc@csail.mit.edu, theory-seminars@csail.mit.edu

**Reminder Subject:**
TALK: Pseudorandomness from Shrinkage

Abstract: One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models where we don't know super-polynomial lower bounds but do know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can construct PRGs that are essentially best possible without in turn improving the lower bounds.

More specifically, say that a circuit family has shrinkage exponent Gamma if a random restriction leaving a p fraction of variables unset shrinks the size of any circuit in the family by a factor of p^{Gamma + o(1)}. Our PRG uses a seed of length s^{1/(Gamma + 1) + o(1)} to fool circuits in the family of size s. By using this generic construction, we get PRGs with polynomially small error for the following classes of circuits of size s and with the following seed lengths:

1. For de Morgan formulas, seed length s^{1/3+o(1)};

2. For formulas over an arbitrary basis, seed length s^{1/2+o(1)};

3. For read-once de Morgan formulas, seed length s^{.234...};

4. For branching programs of size s, seed length s^{1/2+o(1)}.

The previous best PRGs known for these classes used seeds of length bigger than n/2 to output n bits, and worked only when the size s=O(n).

Joint work with Russell Impagliazzo and Raghu Meka.

**Research Areas:**

**Impact Areas:**

Created by Holly A Jones at Thursday, May 01, 2014 at 2:37 PM.