Algebraic methods in the theory of lower bounds for Boolean circuit complexity

1987/01/01 by Roman Smolensky · 8 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Coding theory and cryptography #Quantum Computing Algorithms and Architecture #Oracle #Boolean function #Mathematics #Boolean circuit #Algebraic number #Circuit complexity #Constant (computer programming) #Statement (logic) #Electronic circuit #Discrete mathematics #Set (abstract data type) #Parity function #Prime (order theory) #Combinatorics #Arithmetic #Computer science #Boolean expression

paper · pdf · doi:10.1145/28395.28404

openalex publication_date 1987/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We use algebraic methods to get lower bounds for complexity of different functions based on constant depth unbounded fan-in circuits with the given set of basic operations. In particular, we prove that depth k circuits with gates NOT, OR and MODp where p is a prime require Exp(Ο(n1/2k)) gates to calculate MODr functions for any r ≠ pm. This statement contains as special cases Yao's PARITY result [ Ya 85 ] and Razborov's new MAJORITY result [Ra 86] (MODm gate is an oracle which outputs zero, if the number of ones is divisible by m).

Citations

• Bounded-width polynomial-size branching programs recognize exactly those languages in NC1

Cited by

• Non-uniform ACC Circuit Lower Bounds
• Finite monoids and the fine structure of NC 1
• Lower Bounds on Stabilizer Rank
• Limits on Efficient Computation in the Physical World
• Logic Meets Algebra: the Case of Regular Languages
• Circuit complexity before the dawn of the new millennium
• On ACC
• ACC0 [wikipedia]