Depth reduction for composites

Research output: Contribution to journalArticlepeer-review

Abstract

We show that every circuit with AND, OR, NOT, and MODm gates, m \∈ ℤ +, 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)2O(d) . Therefore, depth-reduction for composite m matches the size of the Allender-Hertrampf construction for primes from 1989. We also list two among the consequences of our construction. One immediate implication is a near-exponential improvement in the depth, from o(log log n) to o(log n/log log n), in Williams' program for NEXP circuit lower bounds. In fact, this pushes William's program to the NC1 frontier. Another, but nontrivial, implication is the strengthening of this o(log n/log log n) depth lower bound in the Chattopadhyay-Santhanam interactive compression setting.

Original languageEnglish (US)
Pages (from-to)668-686
Number of pages19
JournalSIAM Journal on Computing
Volume48
Issue number2
DOIs
StatePublished - 2019

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(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