On additive complexity of a sequence of matrices

2012/09/07 by Igor Sergeev, Sergeev, Igor
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1209.1645

7 pages, in English; 8 pages, in Russian

arxiv created 2012/09/07 · arxiv updated 2012/09/11

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.

Citations

• Fast Monotone Summation over Disjoint Sets

Related

• A relation between additive and multiplicative complexity of Boolean functions
• On relative OR-complexity of Boolean matrices and their complements
• Lower bounds for Combinatorial Algorithms for Boolean Matrix\n Multiplication
• The Pattern Basis Approach to Circuit Complexity
• New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms