5 citations · 16 across the 14 of their papers we have counts for
4 papers · 2 filters
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…
A note on the fast power series' exponential
Igor S. Sergeev
It is shown that the exponential of a complex power series up to order n can be implemented via (23/12+o(1))M(n) binary arithmetic operations over complex field, where M(n) stands…