On additive complexity of a sequence of matrices

Abstract

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.

arXiv comment7 pages, in English; 8 pages, in Russian

References in corpus (2)

• Cancellation-free circuits: An approach for proving superlinear lower bounds for linear Boolean operators
• Fast Monotone Summation over Disjoint Sets

Cited by in corpus (1)

• Cancellation-Free Circuits in Unbounded and Bounded Depth