Uniform circuit lower bound for the permanent

Eric Allender; Vivek Gore

doi:10.1137/S0097539792233907

Uniform circuit lower bound for the permanent

Eric Allender, Vivek Gore

School of Arts and Sciences, Computer Science

Research output: Contribution to journal › Article › peer-review

31 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 (2^n(O(1))) that does not have nonuniform ACC circuits.

Original language	English (US)
Pages (from-to)	1026-1049
Number of pages	24
Journal	SIAM Journal on Computing
Volume	23
Issue number	5
DOIs	https://doi.org/10.1137/S0097539792233907
State	Published - 1994

All Science Journal Classification (ASJC) codes

Computer Science(all)
Mathematics(all)

Access to Document

10.1137/S0097539792233907

Cite this

@article{0a236f1861064b9a9641360a01a08930,

title = "Uniform circuit lower bound for the permanent",

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.",

author = "Eric Allender and Vivek Gore",

year = "1994",

doi = "10.1137/S0097539792233907",

language = "English (US)",

volume = "23",

pages = "1026--1049",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "5",

}

TY - JOUR

T1 - Uniform circuit lower bound for the permanent

AU - Allender, Eric

AU - Gore, Vivek

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028516587&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028516587&partnerID=8YFLogxK

U2 - 10.1137/S0097539792233907

DO - 10.1137/S0097539792233907

M3 - Article

AN - SCOPUS:0028516587

SN - 0097-5397

VL - 23

SP - 1026

EP - 1049

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 5

ER -

Uniform circuit lower bound for the permanent

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this