Uniform circuit lower bound for the permanent

Eric Allender, Vivek Gore

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


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
Issue number5
StatePublished - 1994

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)


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

Cite this