給定三個 n × n 的整數矩陣 A, B, 和 C，其中 C 與 A × B 的乘積有最多 k 個
元素相異。我們研究如何有效率的修正整數矩陣乘積的錯誤，並找到了時間複雜
度為 O(k^0.5 × n^2) 的決定性演算法。另外，在執行演算法的過程中所須要處理的數
字最大值為 O(n^2α^2 + nα)，其中 α 是 A, B, 和 C 的元素的最大值。

Given three n × n matrices A, B, and C with C containing at most k entries differ
from A × B, we investigate how to find the correct matrix products over the ring over
integers efficiently and provide a deterministic algorithm running in O(k^0.5 × n^2) time. In addition, the values need to manipulate during the algorithm are O(n^2 × α^2 + n^α), where α is the largest value of entries in A, B, and C.

[1] BLUM, L., SHUB, M., AND SMALE, S. On a theory of computation and complexity over the real numbers: Np-completeness, recursive functions and universal machines. In The Collected Papers of Stephen Smale: Volume 3. World Scientific, 2000, pp. 1293–1338.
[2] CANTOR, D. G., AND KALTOFEN, E. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica 28, 7 (1991), 693–701.
[3] CARTER, J. L., AND WEGMAN, M. N. Universal classes of hash functions. Journal of computer and system sciences 18, 2 (1979), 143–154.
[4] CAUCHY, A. L. B. Exercices de mathématiques, vol. 3. De Bure frères, 1828.
[5] FREIVALDS, R. Probabilistic machines can use less running time. In IFIP congress
(1977), vol. 839, p. 842.
[6] GĄSIENIEC, L., LEVCOPOULOS, C., LINGAS, A., PAGH, R., AND TOKUYAMA, T. Efficiently correcting matrix products. Algorithmica 79, 2 (2017), 428–443.
[7] HALL, H. S., AND KNIGHT, S. R. Higher Algebra: A Sequel to elementary algebra
for schools. Macmillan and Company, 1910.
[8] HARDY, G. H., WRIGHT, E. M., ET AL. An introduction to the theory of numbers.
Oxford university press, 1979.
[9] IMPAGLIAZZO, R., AND ZUCKERMAN, D. How to recycle random bits. In FOCS (1989), vol. 89, pp. 248–253.
[10] KIMBREL, T., AND SINHA, R. K. A probabilistic algorithm for verifying matrix products using O(n^2) time and log_2 n+O(1) random bits. Inf. Process. Lett. 45, 2 (1993), 107–110.
[11] KOREC, I., AND WIEDERMANN, J. Deterministic verification of integer matrix multiplication in quadratic time. In International Conference on Current Trends in Theory and Practice of Informatics (2014), Springer, pp. 375–382.
[12] PAGH, R. Compressed matrix multiplication. ACM Transactions on Computation Theory (TOCT) 5, 3 (2013), 1–17.
[13] PRITCHARD, P. A sublinear additive sieve for finding prime number. Communications of the ACM 24, 1 (1981), 18–23.
[14] STRASSEN, V. Gaussian elimination is not optimal. Numerische mathematik 13, 4(1969), 354–356.
[15] WILLIAMS, V. V. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing (2012), pp. 887–898.