TY - GEN

T1 - Computing all MOD-functions simultaneously

AU - Demenkov, Evgeny

AU - Kulikov, Alexander S.

AU - Mihajlin, Ivan

AU - Morizumi, Hiroki

PY - 2012/9/4

Y1 - 2012/9/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84865537392&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-30642-6_9

DO - 10.1007/978-3-642-30642-6_9

M3 - Conference contribution

AN - SCOPUS:84865537392

SN - 9783642306419

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 81

EP - 88

BT - Computer Science - Theory and Applications - 7th International Computer Science Symposium in Russia, CSR 2012, Proceedings

T2 - 7th International Computer Science Symposium in Russia on Computer Science - Theory and Applications, CSR 2012

Y2 - 3 July 2012 through 7 July 2012

ER -