New upper bounds on the Boolean circuit complexity of symmetric functions

作者：Demenkov E; Kojevnikov A; Kulikov A^*; Yaroslavtsev G

来源：Information Processing Letters, 2010, 110(7): 264-267.

DOI：10.1016/j.ipl.2010.01.007

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

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

• 出版日期2010-3-1