On relative OR-complexity of Boolean matrices and their complements

2014/07/17 by Igor S. Sergeev, I. S. Sergeev, Sergeev, Igor S.
Computer Science · Engineering · #Advanced Algebra and Logic #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1407.4626

3 pages, published in Russian in Proc. 17-th Int. Conf. on Problems of Theoretical Cybernetics (Kazan, 16-20 June 2014), 262-264

arxiv created 2014/07/17 · openalex publication_date 2014/07/17 · arxiv updated 2014/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We construct explicit Boolean square matrices whose rectifier complexity (OR-complexity) differs significantly from the complexity of their complement matrices.

Related

• On additive complexity of a sequence of matrices
• On the complexity of Boolean matrix ranks
• A relation between additive and multiplicative complexity of Boolean functions
• Structure in Communication Complexity and Constant-Cost Complexity Classes
• The Pattern Basis Approach to Circuit Complexity