DOI

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.

Язык оригиналаанглийский
Название основной публикацииComputer Science - Theory and Applications - 7th International Computer Science Symposium in Russia, CSR 2012, Proceedings
Страницы81-88
Число страниц8
DOI
СостояниеОпубликовано - 4 сен 2012
Событие7th International Computer Science Symposium in Russia on Computer Science - Theory and Applications, CSR 2012 - Nizhny Novgorod, Российская Федерация
Продолжительность: 3 июл 20127 июл 2012

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том7353 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция7th International Computer Science Symposium in Russia on Computer Science - Theory and Applications, CSR 2012
Страна/TерриторияРоссийская Федерация
ГородNizhny Novgorod
Период3/07/127/07/12

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 49825947