Abstract
Given three n by n integer matrices A, B, and P, determining whether the product AB equals P can be done in randomized O(n <sup>2</sup> ) time by Freivalds’ algorithm. In this paper, we consider some generalized Boolean matrix multiplication AB= P <sub>f</sub> , which is defined to be setting the entry p <sub>ij</sub> of P <sub>f</sub> for i, j∈ [ n] as the value of a given function f of the entries on the ith row of A and jth column of B. We show that, for a family of functions f, it takes deterministic O(n <sup>2</sup> ) time to verify whether the generalized product P <sub>f</sub> contains only False entries. Then, we present how to apply such a result to detect small subgraphs efficiently, including: Detect any designated colored 4-cycle in randomized O(n <sup>2</sup> ) time for n-node k-edge-colored (for k= O(1 ) ) complete graphs with maximum color degree at most 2 (including 1-edge-colored general graphs), which unifies several independently discovered algorithms each corresponding to a customized Ramsey-type theorem. As a complementary result, we show that if the maximum color degree is at least 3, any combinatorial algorithm that solves this problem requires Ω (n <sup>3</sup> <sup>-</sup> <sup>ε</sup> ) time for any constant ε> 0, assuming the hardness of triangle detecting.Detect any designated 4-node induced subgraph in randomized O(n <sup>2</sup> ) time for n-node triangle-free graphs. In contrast, the known best algorithm for this problem on general graphs needs triangle time.