FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 |

«Electronic Colloquium on Computational Complexity, Report No. 57 (2012) Pseudorandomness from Shrinkage Raghu Meka∗ Russell Impagliazzo University ...»

-- [ Page 1 ] --

Electronic Colloquium on Computational Complexity, Report No. 57 (2012)

Pseudorandomness from Shrinkage

Raghu Meka∗

Russell Impagliazzo

University of California, San Diego and Institute for Advanced Study

Institute for Advanced Study

David Zuckerman†

University of Texas at Austin and

Institute for Advanced Study


One powerful theme in complexity theory and pseudorandomness in the past few decades

has been the use 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 which are essentially best possible without in turn improving the lower bounds.

More specifically, say that a circuit family has shrinkage exponent Γ 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Γ+o(1). Our PRG uses a seed of length s1/(Γ+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 s1/3+o(1) ;

2. For formulas over an arbitrary basis, seed length s1/2+o(1) ;

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

4. For branching programs of size s, seed length s1/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) [BPW11].

∗ Supported in part by NSF grant DMS-0835373.

† Supported in part by NSF Grants CCF-0916160 and DMS-0835373.

ISSN 1433-8092 1 Introduction Two of the most important general challenges for complexity are to prove constructive lower bounds for non-uniform measures of computational complexity such as circuit size, and to show that randomized algorithms have efficient deterministic simulations. The “Hardness vs. Randomness” paradigm ([BM84, Yao82, AW85, NW94, Nis91, BFNW93]) shows that these questions are linked.

More precisely, these results show how to use any problem that is hard for a class of circuits to create a pseudorandom generator (PRG) for the same class of circuits. This PRG can then be used to construct a relatively efficient deterministic version of any probabilistic algorithm with a corresponding complexity. This has been used both to create unconditional PRGs for circuit classes with known lower bounds, such as AC0, and conditional results, implications between the existence of hard problems and derandomization for classes where no strong lower bounds are known. In the converse direction, it is easy to see that any PRG for a circuit class immediately gives a corresponding lower bound for the class. Somewhat more surprisingly, it has been shown that any efficient deterministic simulation of some probabilistic algorithms would yield circuit lower bounds ([IKW02, KI04, Wil10]). This hardness vs. randomness connection is one of the most important tools in computational complexity. It formalizes the intuition that efficient algorithms for “metacomputational problems”, where the input is a computational device from a certain class, is linked to our ability to prove lower bounds for that class.

However, being so general comes at a quantitative price. Ideally, the stretch of a PRG (the output length as a function of the input length) equals the known lower bound. However, in the hardness to randomness constructions, there are a number of stages that each lose a large polynomial factor. In particular, this means, that, for example, a quadratic or cubic circuit lower bound for a class does not immediately give any nontrivial PRG. For completely generic, “blackbox”, reductions between a hard problem and a PRG, some of these costs are inherent ([GV08, SV08, Wat11, AS11b]). In particular, this is an issue for those models where super-linear but not super-polynomial bounds are known, such as Boolean formulas.

In this work, we show a general method for obtaining tight “hardness to randomness” results from the proofs of lower bounds, rather than as a black-box consequence of the lower bounds. In particular, our methods apply to lower bound proofs that involve restricting some of the inputs to the circuit. Our construction goes in two stages. We start with a lower bound proved by the following kind of shrinkage argument: if we restrict a size s circuit leaving a p fraction of variables unset, the expected size of the restricted circuit is O(pΓ s). The best Γ for which this holds is known as the “shrinkage exponent” of the circuit class. The first stage of our construction is to derandomize the shrinkage argument, showing that there is a distribution with similar shrinkage properties that can be sampled with few bits. This stage of our argument is general, but not totally generic. While the same general construction and analysis ideas work in a variety of models, the details depend on the model. Then we show how to go from such a distribution on restrictions to a PRG. This part is generic, being identical for all models, and is very related to the generator from [NZ96]. The total number of bits r used by the generator is roughly s1/(1+Γ) times the number of bits needed to sample from the distribution on restrictions.

Every generator using r bits to fool tests of size s = s(r) immediately gives a problem requiring size Ω(s(r)) to compute in the model. So, if our function s(r) is close to the known lower bounds, this shows that we have essentially converted all of the “hardness” in the lower bound to “randomness”.

This is indeed the case for a variety of natural models of computation. For Boolean formulas over the de Morgan basis, we give a generator with s(r) = r3−o(1), almost matching the known lower bound of s(n) = Ω(n3 / log2 n) due to H˚ astad ([H˚as98], based on earlier work by [Sub61, And87, IN93, PZ93]).

To avoid technicalities, we assume that the size s is at least the number of input variables n in the following statements (if not, one could think of adding dummy variables).

Theorem 1.1.

For any constant c 0, there is an explicit PRG using a seed of length s1/3 · 2/3 2O(log s) = s1/3+o(1) random bits that s−c -fools formulas of size s over the de Morgan basis.

For Boolean formulas over an arbitrary basis, our generator has stretch s(r) = r2−o(1), almost matching the Khrapchenko bound of s(n) = Ω(n2 ) ([Khr71]).

Theorem 1.2.

For any constant c 0, there is an explicit PRG using a seed of length s1/2 · 1/2 2O(log s) = s1/2+o(1) random bits that s−c -fools formulas of size s over an arbitrary basis.

For branching programs, with size being the total number of edges, we get a similar bound.

Theorem 1.3.

For any constant c 0, there is an explicit PRG using a seed of length s1/2 · 1/2 2O(log s) = s1/2+o(1) random bits that s−c -fools branching programs of size at most s.

We also consider the case of read-once formulas over the DeMorgan basis. Here, there is no sensible notion of lower bound, since all functions computable in the model have size exactly n, but the notion of shrinkage is defined. The optimal shrinkage exponent for such read-once DeMorgan √ formulas was shown by [PZ93, HRY95] to be Γ = log 2/ log( 5 − 1) = 3.27...; using this result, we get a PRG with stretch s(r) = Ω(r4.27... ).

Theorem 1.4.

For any constant c 0, there is an explicit PRG using a seed of length s1/(Γ+1) · 2/3 2O(log s) = s1/(Γ+1)+o(1) random bits that s−c -fools read-once formulas of size s over the de Morgan √ basis, where Γ = log 2/ log( 5 − 1) = 3.27....

Any substantial improvement in our PRGs would thus yield better lower bounds than what is currently known.

Our results dramatically improve previous work. The only directly comparable PRG was by Bogdanov, Papakonstantinou, and Wan [BPW11], who constructed a PRG using a (1 − Ω(1))n bit seed to output n bits that fool read-once formulas and read-once branching programs, where the order of the bits is unknown beforehand. There has been significant work on read-once branching programs where the order of the bits is known in advance (e.g., [Nis91, INW94, NZ96]), but that is a much simpler model and the generators of [Nis91, INW94] are known to not work if the order of bits is unknown [BPW11].

1.1 Outline of Constructions Our techniques build upon those of [Nis92, INW94, NZ96]. The intuition behind all of these PRGs is to exploit communication bottlenecks in the computation. If the random inputs to a computation can be partitioned into two subsets X and Y, and the computation can be simulated with k bits of communication between these two subsets, then given the communication pattern, the two sets of bits have high entropy conditioned on each other. Then, instead of using independent bits for the two sides, we can use a randomness extractor to convert the conditional entropy of X given the communication into random bits to be used in place of Y.

Our construction follows the same basic intuition. The key insight is that shrinkage under random restrictions is a form of communication bottleneck, between X, the set of variables with values specified by the restriction ρ, and Y, the set of variables left unrestricted (and chosen later).

Consider a one-way protocol where the player knowing X has to send a message allowing the Y player to compute the function f. What this message exactly needs to specify is the restricted function f |ρ. If the circuit size of f |ρ is small, much smaller than the size of X, the message can be the circuit computing the restricted function, showing low communication.

Most of the previous constructions were for computational models like read-once branching programs, where one had an explicit description of which sets X and Y had a communication bottleneck, and there was a hierarchical structure available on such sets so that the construction could be defined recursively. Here, we do not have either one, but we know the bottleneck occurs for most sets X and their complements. Instead of explicitly partitioning the variables into blocks with low communication, we randomly sample sets that exhibit this bottleneck until all variables are covered. So far, we are not able to utilize recursion, which blocks us from making the seed size sub-polynomial (and hence proving super-polynomial lower bounds).

Derandomized Shrinkage Bounds. To use our main generator construction, we need a family of random restrictions that can be sampled with few random bits, and still causes the circuits to shrink. For branching programs and formulas over an arbitrary basis (shrinkage exponent Γ = 1) these are not too hard to get by taking O(log n)-wise independent random restrictions. For formulas over the de Morgan basis and read-once formulas getting such restrictions is far trickier.

The first difficulty we face is that H˚ astad’s original proof [H˚ as98] only shows shrinkage in expectation and does not give a high probability bound for the formulas to shrink. We get around this difficulty as follows. Let f be a formula over the DeMorgan basis. We first show shrinkage under restrictions for which the probability of being unset p = n−α for some α = o(1) and have k = no(1) -wise independence. By repeating this process independently, we get shrinkage for all values of p (both in the known lower bounds and in our PRG construction we need p ∼ n1/(Γ+1) ).

To do this, we decompose the target formula f into O(n/ ) subformulas gi of size at most, for a suitable k. Since each gi now has size at most k, the behavior of gi under restrictions should be the same under k-wise independent restrictions or truly random restrictions. Thus, we can roughly expect each gi to shrink by pΓ in expectation.

For read-once formulas, the events that the different gi shrink are independent, and hence by a Chernoff bound with high probability the total shrinkage is as promised. For the read-t case (each variable appears at most t times in the formula), we partition the subformulas into t + 1 color classes, such that within a color class the subformulas are on disjoint sets of variables. We can then proceed as in the read-once case. For the general case, we condition on heavy variables (the ones that appear many times) in a subtle way and reduce to the read-t case.

2 Preliminaries We start with some definitions and notations.

• For a restriction ρ ∈ {0, 1, ∗}n, let the set of active variables be A(ρ) = {i : ρi = ∗}.

• For ρ ∈ {0, 1, ∗}n and f : {0, 1}n → {0, 1}, define the ρ-restricted function fρ : {0, 1}A(ρ) → {0, 1} by fρ (y) = f (x), where x ∈ {0, 1}n satisfies xi = yi, i ∈ A(ρ) and xi = ρi otherwise.

• Call a distribution D on {0, 1, ∗}n p-regular if for every i ∈ [n], Prρ←D [ρi = ∗] = p. We say D is k-wise independent if any k coordinates of D are independent. There exist explicit k-wise independent distributions samplable with O (k(log n)(log p)) random bits [AS11a].

• For a class of functions F on n-variables we say s : F → N \ [n] is a size function if |{f ∈ F :

s(f ) ≤ m}| ≤ mO(m) for m ≥ n. By default, we shall assume that F is closed under negating the input variables and for any f ∈ F, s(g) = O(s(f )) if g is obtained from f by negating some input variables. We also assume that any f ∈ F depends on at most s(f ) variables.

• We say two distributions D, D (on the same universe) are ε-close if the statistical distance between D, D is at most ε.

–  –  –

Similarly, we say G δ-fools a class of functions F if G δ-fools all elements of F. We refer to the parameter r as the seed-length of the generator G and say G is explicit if G can be computed in poly(n, 1/δ) time.

• Throughout, we use upper case letters for random variables and lower case for constants.

Pages:   || 2 | 3 |

Similar works:

«BARNEGAT BAY STORM SURGE ELEVATIONS DURING HURRICANE SANDY And SOURCES OF SURGE FLOODING WITHIN THE BAY Hurricane Sandy came ashore in New Jersey Sunday evening, October 29, 2012 as a hybrid hurricane and northeaster which moved westward from the Atlantic Ocean crossing the coastline in northern Atlantic County. This path proved particularly devastating for NJ bayfront and oceanfront communities north of Little Egg Inlet in Ocean and Monmouth Counties, with extensive tidal flooding also...»

«1 Defeat of aging utopia or foreseeable scientific reality? Aubrey de Grey Department of Genetics, University of Cambridge Downing Street, Cambridge CB2 3EH, UK Email: ag24@gen.cam.ac.uk Abstract If we ignore reductions of mortality in infancy and childbirth, life expectancy in the developed world has risen only by between one and two years per decade in the past century. This is an impressive acceleration relative to previous centuries. Curiously, while many demographers consider that the...»

«Pacific Journal of Mathematics CONCERNING BANACH SPACES WHOSE DUALS ARE Abstract L-SPACES JONNIE BEE BEDNAR AND HOWARD E. LACEY Vol. 41, No. 1 November 1972 PACIFIC JOURNAL OF MATHEMATICS Vol. 41, No. 1, 1972 CONCERNING BANACH SPACES WHOSE DUALS ARE ABSTRACT L-SPACES J. BEE BEDNAR AND H. ELTON LACEY The purpose of this paper is to give general methods for constructing Banach spaces whose duals are linearly isometric to abstract L spaces. These methods are based on annihilating certain subspaces...»

«Sharing Vision, Interrupting Speech: Hamlet’s Spectacular Community PAUL A. KOTTMAN Hamlet opens with the sharing of a spectacle, a vision. Horatio is invited by Marcellus to share in the experience of seeing the Ghost, “twice seen” by him and Barnardo. Curiously, Marcellus is not satisfied with simply telling Horatio about the Ghost; just as Horatio himself “will not let belief take hold of him,” as he puts it, “without the sensible and true avouch” of sight.1 Verbal narration,...»

«Generosity of Beloved Mustafa Translated into English by Majlis-e-Tarajim (Dawat-e-Islami) Generosity of Beloved Mustafa ََ َ ََ ُ َ َ ُ ََ َ َ ََ َ ‫ِ َـ َ ِ ـ َ ا‬ ‫َ رُ لا‬ ‫و ا ِ وا‬ ‫ة وا م‬ ‫ا‬ َ ََ ُ َ َ ُ ََ َ ََ َ َ ‫َ ـ ُـ‬ ‫و ا ـ وا ـ ِ َ ـ ـ ر ا‬ ‫َـ ـ ِ ا‬ ‫ِـ َ ـ‬ ‫ة وا م‬ ‫ا‬ َ َ ‫َ ُ ُ َ اِ ِ ف‬ ِ Translation: I have made the intention...»

«The Throne of God by Woodrow Kroll Today’s Radio Study: Woodrow Kroll: Chapter 4 of Revelation, verse 1, “After these things I looked, and behold, a door standing open in heaven. And the first voice which I heard was like a trumpet speaking with me, saying, ‘Come up here, and I will show you things which must take place after this.’” I’m going to stop there because you’ll hear me repeat this again and again and again in our studies: it is very important, in understanding...»

«Assessing Learning in Australian Universities Ideas, strategies and resources for quality in student assessment www.cshe.unimelb.edu.au/assessinglearning Assessing students unfamiliar with assessment practices in Australian higher education Helping students understand assessment expectations Australian higher education has assessment practices that are quite different from assessment practices in some other international settings. The following suggestions will particularly benefit...»


«Frederick Holbrook By KENNETH A. MOORE O War Governor1861Vermont after the previous administration of of Frederick Holbrook became the second Civil N SEPTEMBER of Erastus Fairbanks. As Governor Holbrook explained, the office was no bed of rosesl but in spite of the thorns he was able to realize, according to his Reminiscences, three important aims during his two year administration. They were: 1. A pay as you go financing of the War 2. A national draft Call in the spring of 1862 instigated by...»

«FROM PROFESSIONAL FUNCTIONING TO PERSONAL CONFESSION Henri J.M. Nouwen’s contribution to the contemporary spirituality of pastoral care Dissertation zur Erlangung der Doktorwürde der Theologischen Fakultät der Bayerischen Julius-Maximilian-Universität Würzburg vorgelegt von P. Jose Thomas Karickal msfs Aus Paravanthuruth, Kerala, Indien am 20.10.06 Referent: Professor Dr. Rolf Zerfaß Co-referent: Professor Dr. Erich Garhammer Wintersemester 2006/2007 ACKNOWLEDGEMENT A quick flash back...»

«Q: Welcome everyone to Inspired by Math. In this podcast series I interview people who are  inspired by math and who are inspired by others. I'm really excited this morning to be  having a phone conversation with Lou DiGioia. He is the executive director of the  MATHCOUNTS organization, the largest non­profit organization dedicated to extra  curricular middle school mathematics. So, Lou, welcome to Inspired by Math....»

«Mathematical Sciences Alumni News Volume 11, Issue 1 Summer 2002 Greetings! A warm hello to all alumni of the Department of Mathematical Sciences at Northern Illinois University! Once again it is our pleasure to send you news from the past year—including notes you submitted to us concerning your whereabouts and doings. We invite your comments on this issue along with notes on your activities. And we wish you well in all your endeavors. Chair’s Corner by Professor William Blair Chair’s...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.