A depth 3 circuit lower bound for the parity function

Shi-Chun Tsai*

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

We consider small depth boolean circuits with basis {AND, OR, NOT}. We obtain lower bounds for the parity function using a relatively simple method. We prove that for any depth 3 circuit with top fan-in t, computing the n-variable parity function must have at least t2n-1/t wires. Similarly, we obtain a lower bound for computing the depth 4 circuits.

Original languageEnglish
Pages (from-to)857-860
Number of pages4
JournalJournal of Information Science and Engineering
Volume17
Issue number5
DOIs
StatePublished - 1 Sep 2001

Keywords

  • Boolean function complexity
  • Circuit complexity
  • Computational complexity
  • Lower bound
  • Parity

Fingerprint Dive into the research topics of 'A depth 3 circuit lower bound for the parity function'. Together they form a unique fingerprint.

  • Cite this