Uniform circuit lower bound for the permanent

Eric Allender, Vivek Gore

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

The authors show that uniform families of ACC circuits of subexponential size cannot compute the permanent function. This also implies similar lower bounds for certain sets in PP. This is one of the very few examples of a lower bound in circuit complexity whose proof hinges on the uniformity condition; it is still unknown if there is any set in Ntime (2n(O(1))) that does not have nonuniform ACC circuits.

Original languageEnglish (US)
Pages (from-to)1026-1049
Number of pages24
JournalSIAM Journal on Computing
Volume23
Issue number5
DOIs
StatePublished - 1994

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Uniform circuit lower bound for the permanent'. Together they form a unique fingerprint.

Cite this