Depth-Reduction for Composites

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating NEXP from non-uniform ACC. In particular, we show that every circuit with AND, OR, NOT, and MODm gates, m ϵ Z+, of polynomial size and depth d can be reduced to a depth-2, SYM-AND, circuit of size 2(log n) O(d). This is an exponential size improvement over the traditional Yao-Beigel-Tarui, which has size blowup 2(log n)2 O(d). Therefore, depth-reduction for composite m matches the size of the Allender-Hertrampf construction for primes from 1989. One immediate implication of depth reduction is an improvement of the depth from o(loglog n) to o(log n/loglog n), in Williams' program for ACC circuit lower bounds against NEXP. This is just short of O(log n/loglog n) and thus pushes William's program to the NC1 barrier, since NC1 is contained in ACC of depth O(log n/loglog n). A second, but non-immediate, implication regards the strengthening of the ACC lower bound in the Chattopadhyay-Santhanam interactive compression setting.

Original languageEnglish (US)
Title of host publicationProceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PublisherIEEE Computer Society
Pages99-108
Number of pages10
ISBN (Electronic)9781509039333
DOIs
StatePublished - Dec 14 2016
Event57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States
Duration: Oct 9 2016Oct 11 2016

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2016-December
ISSN (Print)0272-5428

Other

Other57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
Country/TerritoryUnited States
CityNew Brunswick
Period10/9/1610/11/16

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Circuit lower bound
  • Composite modulus
  • Depth-reduction
  • Interactive compression
  • Williams' program

Fingerprint

Dive into the research topics of 'Depth-Reduction for Composites'. Together they form a unique fingerprint.

Cite this