In this note, we present improved upper bounds on the circuit complexity of symmetric Boolean functions. In particular, we describe circuits of size 4.5 n + o (n) for any symmetric function of n variables, as well as circuits of size 3n for MOD3n function.

Original languageEnglish
Pages (from-to)264-267
Number of pages4
JournalInformation Processing Letters
Volume110
Issue number7
DOIs
StatePublished - 1 Mar 2010

    Research areas

  • Boolean circuit complexity, Computational complexity, Modular functions, Symmetric functions, Upper bounds

    Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

ID: 49825441