Furst–Saxe–Sipser lower bounds
E518865
Furst–Saxe–Sipser lower bounds are foundational results in circuit complexity theory that established superpolynomial lower bounds for constant-depth Boolean circuits (AC⁰), demonstrating inherent limitations of such circuits for computing certain functions.
Statements (43)
| Predicate | Object |
|---|---|
| instanceOf |
circuit complexity lower bound
ⓘ
result in computational complexity theory ⓘ |
| appliesTo |
AC⁰ circuits
ⓘ
Boolean circuits ⓘ constant-depth circuits ⓘ |
| authors |
James B. Saxe
NERFINISHED
ⓘ
Merrick L. Furst NERFINISHED ⓘ Michael Sipser NERFINISHED ⓘ |
| complexityClassContext |
AC⁰
NERFINISHED
ⓘ
P NERFINISHED ⓘ |
| consequence |
evidence of inherent limitations of shallow circuits
ⓘ
first superpolynomial lower bounds for natural circuit class ⓘ |
| depthRestriction | constant depth ⓘ |
| field |
circuit complexity
ⓘ
computational complexity theory ⓘ |
| gateType |
NOT gates
ⓘ
unbounded fan-in AND gates ⓘ unbounded fan-in OR gates ⓘ |
| historicalSignificance | among earliest strong lower bounds for explicit Boolean functions in a natural circuit model ⓘ |
| implies |
parity not in AC⁰
ⓘ
separation between AC⁰ and some functions in P ⓘ |
| influenced |
Håstad’s 1986 lower bounds
ⓘ
subsequent AC⁰ lower bound research ⓘ |
| isAbout | limitations of constant-depth polynomial-size circuits ⓘ |
| namedAfter |
James B. Saxe
NERFINISHED
ⓘ
Merrick Furst NERFINISHED ⓘ Michael Sipser NERFINISHED ⓘ |
| originalPaperTitle | Parity, circuits, and the polynomial-time hierarchy NERFINISHED ⓘ |
| provesLowerBoundFor |
MOD₂ function
ⓘ
parity function ⓘ |
| publishedIn | Journal of Computer and System Sciences NERFINISHED ⓘ |
| relatedTo | polynomial-time hierarchy ⓘ |
| resultType | nontrivial circuit lower bound ⓘ |
| shows |
existence of functions not computable by polynomial-size constant-depth circuits
ⓘ
limitations of AC⁰ circuits ⓘ relativized separation results for the polynomial-time hierarchy ⓘ superpolynomial lower bounds for constant-depth Boolean circuits ⓘ |
| sizeRestriction | polynomial size ⓘ |
| strengthenedBy |
Håstad’s optimal AC⁰ lower bounds
ⓘ
Håstad’s switching lemma ⓘ |
| techniqueUsed |
random restrictions
ⓘ
switching lemma–style arguments precursor ⓘ |
| yearPublished | 1981 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.