FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |

«Abstract The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MODm gates, where m 1 is an arbitrary ...»

-- [ Page 1 ] --

Non-Uniform ACC Circuit Lower Bounds

Ryan Williams∗

IBM Almaden Research Center

November 23, 2010


The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR,

NOT, and MODm gates, where m 1 is an arbitrary constant. We prove:

• NTIME[2n ] does not have non-uniform ACC circuits of polynomial size. The size lower bound

can be slightly strengthened to quasi-polynomials and other less natural functions.

• ENP, the class of languages recognized in 2O(n) time with an NP oracle, doesn’t have non-uniform o(1) ACC circuits of 2n size. The lower bound gives an exponential size-depth tradeoff: for every d δ there is a δ 0 such that ENP doesn’t have depth-d ACC circuits of size 2n.

Previously, it was not known whether EXPNP had depth-3 polynomial size circuits made out of only MOD6 gates. The high-level strategy is to design faster algorithms for the circuit satisfiability problem over ACC circuits, then prove that such algorithms entail the above lower bounds. The algorithm combines known properties of ACC with fast rectangular matrix multiplication and dynamic programming, while the second step requires a subtle strengthening of the author’s prior work [STOC’10].

∗ Supported by the Josef Raviv Memorial Fellowship.

1 Introduction Non-uniform computation allows the size of a program to grow with the sizes of inputs. A non-uniform computation can be naturally represented as an infinite family of Boolean circuits, one for each possible input length. A longstanding aim of complexity theory is to understand the power of non-uniform computation in relation to the usual uniform models which have fixed-size programs. One complication is that non-uniform computations can recognize undecidable languages by having a large enough circuit for each input length. Finding uniform computations that cannot be simulated by small non-uniform circuit families is an extremely difficult venture that is related to other major problems. For instance, P = NP follows if one could provide an NP problem that cannot be solved by any circuit family where the size of the nth circuit is at most polynomial in n. Non-uniform lower bounds establish impossibility results for computation in the physical world: it could be that P = NP, yet NP-complete problems can still be efficiently solved using a “bloated” program with sufficiently many lines of code. Non-uniform circuit size lower bounds for NP would rule outthis possibility. (However, it is currently possible that all of NP has circuits of size 6n.) In the early 1980’s, researchers began to carefully study the power of non-uniform low depth circuits.

Intuitively, such circuits correspond to extremely fast parallel computations. The initial hope was that if some functions in NP were proved to require large, restricted circuit families, then by gradually lifting the restrictions over time, superpolynomial size unrestricted lower bounds for NP could be attained, proving P = NP. Furst, Saxe, and Sipser [FSS81] and independently Ajtai [Ajt83] showed that functions such as the parity of n bits cannot be computed by polynomial size AC0 circuits, i.e., polynomial size circuit families of constant depth over the usual basis of AND, OR, and NOT gates, where each AND and OR may have arbitrarily many inputs. Yao [Yao85] improved the lower bounds to exponential size, and H˚ stad [H˚ s86] a a proved essentially optimal AC0 lower bounds for parity. Around the same time, Razborov [Raz85] proved superpolynomial lower bounds for solving clique with monotone circuits (i.e., general circuits without NOT gates), and the bound was improved to exponential size by Alon and Boppana [AB87]. However, it was later shown [Raz89] that the monotone techniques probably would not extend to general circuits.

Encouraged by the progress on AC0, attention turned to lower bounds for what seemed to be minor generalizations. The most natural generalization was to grant AC0 the parity function for free. Razborov [Raz87] proved an exponential lower bound for computing the majority of n bits with constant-depth circuits made up of AND, OR, NOT, and MOD2 gates. (A MODm gate outputs 1 iff m divides the sum of its inputs.) Then Smolensky [Smo87] proved exponential lower bounds for computing MODq with constant-depth circuits made up of AND, OR, NOT, and MODp gates, for distinct primes p and q. Barrington [Bar89] suggested the next step would be to prove lower bounds for the class ACC, which consists of constant-depth circuit families over the basis AND, OR, NOT, and MODm for arbitrary constant m 1.1 It is here that progress on strong lower bounds began to falter (although there has been progress on further restricted cases, cf. the Preliminaries). While it was conjectured that the majority of n bits cannot have polynomial ACC circuits, strong ACC lower bounds remained elusive.

After some years of failing to prove a superpolynomial lower bound, the primary questions were weakened. Rather than trying to find simple functions that cannot be computed with weak circuits, perhaps we could rule out weak circuits for complicated functions. Could one prove that nondeterministic exponential time (NEXP) doesn’t have polynomial size circuits? A series of papers starting with Babai, Fortnow, Nisan, and Wigderson [BFNW93, KvM99, IKW02] showed that even this sort of lower bound would imply derandomization results: in the case of NEXP lower bounds, it would imply that Merlin-Arthur games can The class is also called ACC0 in the literature. However, as ACCi is hardly studied at all, for any i 0, at the present time it

makes sense to drop the superscript.

be non-trivially simulated with nondeterministic algorithms. This indicated that proving good circuit lower bounds for NEXP would already require significantly new ideas.

In this paper, we address two frontier questions concerning non-uniform circuit complexity:

1. Does nondeterministic 2O(n) time have non-uniform polynomial size ACC circuits?

(Is NTIME[2O(n) ] in non-uniform ACC?)

2. Does exponential time with an NP oracle have non-uniform polynomial size circuits?

(Is EXPNP ⊆ P/poly?) Over the years, these questions have turned into notorious and somewhat embarrassing open problems, because it seems so obvious that the answers should be no. It was open if EXPNP could be recognized with depth-3 polynomial size circuits made out of only MOD6 gates.2 We make headway on these frontiers, giving a strong no answer to the first question.

Theorem 1.1 NTIME[2n ] does not have non-uniform ACC circuits of polynomial size.

Stronger size lower bounds hold (e.g. quasi-polynomial size) but the results are not very clean; see Section 5.1 for details. For EXPNP, we can prove an exponential lower bound.

–  –  –

Recall that the lowest complexity class for which we know exponential (unrestricted) circuit lower bounds is ∆EXP, the third level of the exponential hierarchy [MVW99].

Extending the approach of this paper to settle the second frontier question may be difficult, but this prospect does not look as implausible as it did before. If polynomial unrestricted circuits could be simulated by subexponential ACC circuits, or if one could improve just a little on the running time of algorithms for the circuit satisfiability problem, the second question would be settled.

1.1 An Overview of the Proofs Let us sketch how these new lower bounds are proved, giving a roadmap for the rest of the paper. In recent work [Wil10], the author suggested a research program for proving non-uniform circuit lower bounds for NEXP. It was shown that for many circuit classes C, sufficiently faster satisfiability algorithms for Ccircuits would entail non-uniform lower bounds for C-circuits. The objective of this paper is to carry out the proposed research program in the case of ACC circuits.

The proof of the lower bound for ENP (Theorem 1.2) is a combination of complexity-theoretic ideas (time hierarchies, compression by circuits, the local checkability of computation) and algorithmic ideas (fast matrix multiplication, dynamic programming, table lookup).

1. First, we show that satisfiability algorithms for subexponential size n-input ACC circuits with running time O(2n /nk ) imply exponential size ACC lower bounds for ENP (Theorem 3.2), where k is sufficiently large. The model of computation for the satisfiability algorithm is flexible; we may assume the multitape Turing model or a random access machine. This step considerably strengthens results of earlier work [Wil10] which could only show that an o(2n/3 ) time algorithm for ACC circuit satisfiability implies lower bounds.

Note that slightly larger classes such as MAEXP and NEXPNP are known to not have polynomial size circuits; see the Prelim



The strategy is to prove that, if there is a faster algorithm for ACC circuit satisfiability, and there are subexpoo(1) nential (2n ) size ACC circuits for ENP, then every L ∈ NTIME[2n ] can be accepted by a nondeterministic algorithm in O(2n n10 /nk ) time. (Here, 10 is a substitute for a small universal constant.) When k 10 this contradicts the nondeterministic time hierarchy theorem [SFM78, Zak83], so one of the assumptions must be false. The nondeterministic time hierarchy is fairly robust with respect to the machine model: for large enough k, NTIMET M [2n ] ⊆ NTIMERAM [2n /nk ] where NTIMET M denotes nondeterministic multitape Turing machines and NTIMERAM denotes nondeterministic RAMs in the usual logarithmic cost model (cf.

Lemma 2.1).

This implies it suffices for the underlying ACC SAT algorithm to work on a RAM (provided it runs in O(2n /nk ) time for large enough k).

Two known facts are required in the proof. First, there is a polynomial-time reduction from any L ∈ NTIME[2n ] to the NEXP-complete problem SUCCINCT 3SAT such that every instance x of length n (for sufficiently large n) is reduced to a (unrestricted, not ACC) circuit Cx of size O(n5 ) with at most n + 5 log n inputs (Fact 3.1). That is, the bit string obtained by evaluating Cx on its O(2n n5 ) possible assignments (in lex order) encodes a 3CNF formula FCx that is satisfiable iff x ∈ L. Second, if ENP is in subexponential ACC, then (given an input x) the lexicographically first satisfying assignment to the formula encoded by Cx can be described by an ACC circuit W of subexponential size (Fact 3.2). That is, the bit string obtained by evaluating W on all possible assignments encodes a satisfying assignment to the exponentially long FCx.

If Cx were an ACC circuit, then any L could be simulated in O(2n n5 /nk ) nondeterministic time, by nondeterministically guessing a subexponential ACC circuit W and constructing an ACC circuit satisfiability instance D built of Cx and W, where D is satisfiable if and only if W does not encode a satisfying assignment to FCx (as shown in the author’s prior paper). The circuit D has at most n + 5 log n inputs and o(1) 2n size, so the assumed ACC satisfiability algorithm can handle D in O(2n n5 /nk ) time.

The above argument doesn’t quite work, because we do not know how to produce a Cx that is an ACC circuit (indeed, it may not be possible). An ACC SAT algorithm will not work on D, because it contains a copy of an unrestricted Cx. However, assuming only P has subexponential ACC circuits, we show how to guess and verify an equivalent ACC circuit Cx in nondeterministic O(2n n10 /nk ) time using a faster ACC satisfiability algorithm (Lemma 3.1). This new result makes it possible to prove lower bounds even with weak ACC satisfiability algorithms. Furthermore, this part of the proof does not use any specific properties of ACC, so it could potentially be applied for stronger lower bounds in the future.

2. Next we show how satisfiability of subexponential ACC circuits of depth d and n inputs can be δ determined in 2n−Ω(n ) time, for a δ 0 that depends on d (Theorem 4.1). Given any such circuit C, δ replace it with C which is an OR of 2n copies of C, where the first nδ inputs of each copy are substituted δ with a variable assignment. This ACC circuit C has n − nδ inputs, 2O(n ) size, and C is satisfiable if and only if C is. Applying a powerful result of Yao, Beigel-Tarui, and Allender-Gore (Lemma 4.1), C can be δ2O(d) replaced by an equivalent depth-2 circuit C of 2n size, which consists of an efficiently computable 1/2O(d), and using a nearly symmetric function at the output gate and AND gates below it. Setting δ optimal rectangular matrix multiplication algorithm due to Coppersmith (Lemma 4.3), C can be evaluated δ on all of its possible assignments in 2n−n poly(n) time (Lemma 4.2). Alternatively, this evaluation of C can also be done via simple dynamic programming. This concludes the sketch of the ENP lower bound.

The only use of the full assumption “ENP has ACC circuits” is in Fact 3.2. The lower bound for NEXP (Theorem 1.1) applies the result (which follows from work of Impagliazzo, Kabanets, and Wigderson [IKW02]) that if NEXP has polynomial size (unrestricted) circuits then satisfiable instances of SUCCINCT 3SAT already have polynomial size (unrestricted) circuits W encoding satisfying assignments (Theorem 5.1). But if P has ACC circuits, it is easy to see that these unrestricted circuits must have equivalent ACC circuits as well (Lemma 5.1). This helps extend the ENP lower bound to NEXP. However, the resulting size lower bound is not exponential: from S(n)-size circuits for NEXP one only obtains S(S(S(n)c )c )c -size ACC circuits encoding satisfying assignments. This allows for some “half-exponential” type improvements in the size lower bounds against NEXP.

Perhaps the most interesting aspect of the proofs is that only the satisfiability algorithm for ACC circuits relies on specific properties of ACC. Improved exponential algorithms for satisfiability are the only barrier to further progress on circuit lower bounds for NEXP. In general, this paper weakens the algorithmic assumptions necessary to prove lower bounds, and strengthens the lower bounds obtained. Let C be a class of circuit families that is closed under composition (the composition of two circuit families from C is also a family in C) and contains AC0. Possible C include constant-depth threshold circuits, Boolean formulas, and unrestricted Boolean circuits. The arguments of Section 3 and Section 5 imply the following metatheorem.

Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |

Similar works:

«Exempt charities and the role of the Secretary of State as Principal Regulator Departmental advice for academy trusts, sixth form colleges, voluntary aided, voluntary controlled and foundation trust schools February 2014 Contents Summary 3 About this departmental advice 3 Who is this advice for? 3 Key points 3 Regulation of exempt charities 4 What are exempt charities? 4 The Secretary of State for Education as Principal Regulator 5 Requirements and duties of exempt charities 6 Accounts,...»

«Integrating management and marketing strategies at heritage sites Item type Article Authors Fullteron, L.; McGettigan, K.; Stephens, S. Citation Fullerton, L., McGettigan, K. & Stephens, S. (2010) 'Integrating management and marketing strategies at heritage sites', International Journal of Culture, Tourism and Hospitality Research, 5(2), 108-117 Downloaded 8-May-2016 19:11:06 Item License http://creativecommons.org/licenses/by-nc-nd/4.0/ Link to item http://hdl.handle.net/10759/331817...»

«Egyptian Computer Science Journal Vol.34 No. 5 September 2010 Addition-Subtraction Chain for 160 bit Integers by using 2’s Complement Mohamed M. Abd-Eldayem Ehab T. Alnfrawy Aly A. Fahmy Associate Professor, Assistant Lecturer, Professor, Department of Computer Engineering C o m p u t e r Science and Computer Science Department College of Computer and Information Sciences Information Systems Department Faculty o f Computers and Information King Saud University Sadat Academy, Alexandria Cairo...»

«L-R: Al-Saddiq Al-Raddi (© Crispin Hughes), Chris Beckett, Elizabeth Burns, Kate Clanchy, David Morley (© Graeme Oxby) and Carole Satyamurti Shaping and reshaping: the Ted Hughes Award for New Work in Poetry shortlist PRESS RELEASE is announced 28 February release For immediate 2014 Judges Jackie Kay, Andrew McMillan and Ali Smith announce For 3 March 2016 immediate release their chosen shortlist for the Ted Hughes Award for New Work in Poetry 2015 The shortlisted poets are: Al-Saddiq...»

«Foreword by Martin Glassborow, aka Storagebod, storage industry expert Rethinking Enterprise Storage A Hybrid Cloud Model Marc Farley Visit us today at microsoftpressstore.com Hundreds of titles available – Books, eBooks, and online • resources from industry experts • Free U.S. shipping eBooks in multiple formats – Read on your computer, • tablet, mobile device, or e-reader • Print & eBook Best Value Packs eBook Deal of the Week – Save up to 60% on featured titles • Newsletter...»

«Assessment & Evaluation in Higher Education Vol. 29, No. 1, February 2004 Academic procrastination and statistics anxiety Anthony JOnwuegbuzieDepartment of Educational Measurement and Research, Colege of EducationUniversity of South Florida4204 East Fowler AvenueTampaEDU 162FL33620-7750tonyonwuegbuzie@aol.com Anthony J. Onwuegbuzie* University of South Florida, USA Statistics anxiety, which is experienced by as many as 80% of graduate students, has been found to debilitate performance in...»

«CHAPTER 3 WHAT WORKS IN DISTANCE LEARNING: INSTRUCTIONAL STRATEGIES Richard Clark University of Southern California Published in: O’Neil, H. (Ed.), (2004) What works in distance learning: Guidelines. Greenwich Connecticut: Information Age Publishers.The following guidelines are presented in this chapter: Strategies Based on Providing Learner Control of Instructional Navigation Strategies Based on Providing Worked Examples and Practice Strategies Based on Effective Feedback During Learning...»

«Stephen Mitchell Blåkulla and Its Antecedents: Transvection and Conventicles in Nordic Witchcraft F ew aspects of human society have excited as much scholarly activity in recent decades as have those concerned with witchcraft — questions on the nature of the phenomenon itself, of the practices associated with it, of its discovery, of the means of protecting oneself against it, and so on (see Douglas 1970). The impressive response to this surge of interest by Nordic researchers (e.g., Alver...»

«    National Poverty Center Working Paper Series   #06‐24  July, 2006   REDLINING OR RISK?  A Spatial Analysis of Auto Insurance Rates in Los Angeles    Paul M. Ong, School of Public Affairs, UCLA    Michael A. Stoll, School of Public Affairs, UCLA          This paper is available online at the National Poverty Center Working Paper Series index at:  http://www.npc.umich.edu/publications/working_papers/  ...»

«RESEARCH REPORT 2013-5 Are AP Students More ® Likely to Graduate from College on Time? By Krista D. Mattern, Jessica P. Marini, and Emily J. Shaw Delete this black box when image is placed. Krista D. Mattern is a research scientist at the College Board. Jessica P Marini was a graduate intern at the College Board.. Emily J. Shaw is an associate research scientist at the College Board. About the College Board The College Board is a mission-driven not-for-profit organization that connects...»

«LS Course Descriptions *The following sections are NOT open to Global Liberal Studies (GLS) students. GLS students should consult the GLS course description document or see their advisor. click a link to navigate to all the course descriptions for a subject Cultural Foundations I Cultural Foundations II Cultural Foundations III Social Foundations I Social Foundations II Social Foundations III Writing I Writing II Global Cultures Creative Writing Economics Science Cultural Foundations I Cultural...»

«A New Strategy for Sport: Consultation Paper #SportingFuture August 2015 We can also provide documents to meet the specific requirements for people with disabilities. Please email sportstrategy@culture.gov.uk Department for Culture, Media & Sport Printed in the UK on recycled paper © Crown copyright 2015 You may re-use this information (excluding logos) free of charge in any format or medium, under the terms of the Open Government Licence. To view this licence, visit...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

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.