Computing the Boolean product of two n× n Boolean matrices using O(n²) mechanical operation

2020/04/27 by Andrzej Lingas, Lingas, Andrzej, Mia Persson +1
Computer Science · #Data Structures and Algorithms (cs.DS) #F.2.2 #F.4.1 #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.2004.13086

11 pages, 7 figures

arxiv created 2020/05/22 · arxiv updated 2020/05/25

Abstract

We study the problem of determining the Boolean product of two n× n Boolean matrices in an unconventional computational model allowing for mechanical operations. We show that O(n²) operations are sufficient to compute the product in this model.

Related

• A Matrix Product State Representation of Boolean Functions
• Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
• New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
• Lower Bounds for Matrix Product
• Near Quadratic Matrix Multiplication Modulo Composites