A note on the formula size of the ``mod k'' functions (Q1264165)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the formula size of the ``mod k'' functions |
scientific article |
Statements
A note on the formula size of the ``mod k'' functions (English)
0 references
1987
0 references
The symmetric Boolean functions in n variables are defined as \(C^ n_ k(x_ 1,...,x_ n)\) iff \(\sum^{n}_{i=1}x_ i=0 mod k\). This note proves the existence of formulas of size \(O(n^ 2)\) for \(C^ n_ 3\), size \(O(n^{2.58})\) for \(C^ n_ 7\), and size \(O(n^ 3)\) for the functions \(C^ n_ 5\) and \(C^ n_{15}\).
0 references
formula size
0 references
finite field
0 references
symmetric Boolean functions
0 references