Application of Approximating Algorithms to Boolean Matrix Multiplication

Bounded integer matrices are matrices whose entries are bounded integers. Arbitrary precision approximating algorithms (also called APA algorithms) [2], [3] yielding a complexity of"O(n?) for n × n matrix multiplication, can be used for bounded integer matrix multiplication. The resulting complexity is O(n?) log2n log log n log log log n) in terms of bit operations. Boolean matrices are a special case of bounded integer matrices and the same algorithms can be used. Copyright © 1980 by The Institute of Electrical and Electronics Engineers, Inc.