{'fraction_non_alphanumeric': 0.02385685884691849, 'fraction_numerical': 0.0009940357852882703, 'mean_word_length': 5.254658385093168, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the integer complexity of Boolean matrix multiplication

The complexity of multiplying two Boolean matrices is normally expressed in terms of number of bit operations performed in the computation; this follows from the natural assumption that Boolean operations can be implemented differently (and less expensively) than arithmetic operations. Should such a difference not exist (e.g., in the uniform-cost RAM model), the cost of Boolean matrix multiplication would equal, using existing algorithms, the cost of general matrix multiplication. The question arises of whether Boolean matrix multiplication and general matrix multiplication have indeed the same arithmetic complexity. The reason for this note is to show that, unless general matrices can be multiplied in quadratic time, this is not so; in fact, a simple technique is presented which multiplies two NxN Boolean matrices using O(N 2) integer operations. Consider the product C= AxB where both A and B are NxN Boolean matrices. Let Pi denote