The following is taken from:
http://www.cs.cmu.edu/~ryanw/mat-vec3.pdf
“Let us briefly review some past combinatorial (non-algebraic) approaches to matrix multiplication.
The “Four Russians” algorithm of [Arlazarov et al.1970] performs Boolean n×n matrix
multiplication in O(n³/ log n) time. (For a reference in English, cf. Aho, Hopcroft, and Ullman’s
book [AHU74].) Savage [S74] and Santoro [S80] observed that this time bound extends to a wide
range of algebraic structures, assuming constant time arithmetic. This was eventually improved
slightly to O(n³/ log³/² n) time by Atkinson and Santoro [AS88]. Rytter [R85] (and independently
Basch, Khanna, and Motwani [BKM95]) gave an O(n³/ log²n) algorithm for Boolean matrix multiplication
on the (log n)-word RAM.”
[AHU74] A.V.Aho, J.E.Hopcroft, J.D.Ullman “The Design and Analysis of Computer Algorithms.”
Addison-Wesley, Reading, MA, 1974
[AS88] M.D.Atkinson, N.Santoro “A practical algorithm for Boolean matrix multiplication.” Inf. Proc.
Letters 29:37–38, 1988
[BKM95] J.Basch, S.Khanna, R.Motwani “On Diameter Verification and Boolean Matrix Multiplication.”
Technical Report No. STAN-CS-95-1544, Department of Computer Science, Stanford Univ., 1995
http://citeseer.ist.psu.edu/basch95diameter.html
[R85] W.Rytter “Fast Recognition of Pushdown Automaton and Context-free Languages.” Information
and Control 67(1-3):12–22, 1985 http://dx.doi.org/10.1016/S0019-9958(85)80024-3
[S74] J.E.Savage “An algorithm for the computation of linear forms.” SIAM J. Comput. 3(2):150–158, 1974
DOI: 10.1137/0203011, ( see also: http://portal.acm.org/citation.cfm?id=803746 )
[S80] N.Santoro “Extending the Four Russians’ Bound to General Matrix Multiplication.” Inf. Proc.
Letters 10(2):87–88, 1980 ( N.Santoro publications: http://www.scs.carleton.ca/~santoro/AllPub.html )
“Method of 4 Russians Inversion”: http://eprint.iacr.org/2006/251.pdf http://citeseer.ist.psu.edu/759459.html
See also:
L.Lee “Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication”
J. of the ACM 49(1), pp. 1–15, 2002 http://www.cs.cornell.edu/home/llee/papers/bmmcfl-jacm.pdf
F.Ebert “CFG Parsing and Boolean Matrix Multiplication”
http://www.ps.uni-sb.de/courses/seminar-ws06/papers/07_franziska_ebert.pdf
W.Rytter “Context-free recognition via shortest paths computation: a version of Valiant’s algorithm”
Theoretical Computer Science http://citeseer.ist.psu.edu/208339.html
( see also: http://citeseer.ist.psu.edu/site/208339 )
