4 citations · 8 across the 4 of their papers we have counts for
4 papers
A relation between additive and multiplicative complexity of Boolean functions
Igor S. Sergeev
In the present note we prove an asymptotically tight relation between additive and multiplicative complexity of Boolean functions with respect to implementation by circuits over th…
On additive complexity of a sequence of matrices
Igor Sergeev
We show new upper and lower bounds for the complexity of implementation of a sequence of Boolean matrices proposed by Kaski et al. (arXiv:1208.0554) with additive circuits.
Upper bounds for the formula size of the majority function
Igor S. Sergeev
It is shown that the counting function of n Boolean variables can be implemented with the formulae of size O(n^3.06) over the basis of all 2-input Boolean functions and of size O(n…
Fast Monotone Summation over Disjoint Sets
Petteri Kaski, Mikko Koivisto, Janne H. Korhonen
We study the problem of computing an ensemble of multiple sums where the summands in each sum are indexed by subsets of size of an -element ground set. More precisely, the t…