The fundamental symmetric functions are EX k n (equal to 1 if the sum of n input bits is exactly k), TH k n (the sum is at least k), and MOD m,r n (the sum is congruent to r modulo m). It is well known that all these functions and in fact any symmetric Boolean function have linear circuit size. Simple counting shows that the circuit complexity of computing n symmetric functions is Ω(n 2 - o(1)) for almost all tuples of n symmetric functions. It is well-known that all EX and TH functions (i.e., for all 0 ≤ k ≤ n) of n input bits can be computed by linear size circuits. In this short note, we investigate the circuit complexity of computing all MOD functions (for all 1 ≤ m ≤ n). We prove an O(n) upper bound for computing the set of functions {MOD 1,r n, MOD 2,r n,..., MOD n,r n} and an O(nloglogn) upper bound for {MOD 1,r1 n, MOD 2,r2 n,..., MOD n,rn n}, where r 1, r 2,..., r n are arbitrary integers.

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - 7th International Computer Science Symposium in Russia, CSR 2012, Proceedings
Pages81-88
Number of pages8
DOIs
StatePublished - 4 Sep 2012
Event7th International Computer Science Symposium in Russia on Computer Science - Theory and Applications, CSR 2012 - Nizhny Novgorod, Russian Federation
Duration: 3 Jul 20127 Jul 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7353 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Computer Science Symposium in Russia on Computer Science - Theory and Applications, CSR 2012
Country/TerritoryRussian Federation
CityNizhny Novgorod
Period3/07/127/07/12

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 49825947