×

zbMATH — the first resource for mathematics

Faster multi-witnesses for Boolean matrix multiplication. (English) Zbl 1190.65073

MSC:
65F99 Numerical linear algebra
15B34 Boolean and Hadamard matrices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N.; Naor, M., Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Algorithmica, 16, 434-449, (1996) · Zbl 0857.68055
[2] Aumann, Y.; Lewenstein, M.; Lewenstein, N.; Tsur, D., Finding witnesses by peeling, (), 28-39 · Zbl 1138.68382
[3] Coppersmith, D., Rectangular matrix multiplication revisited, Journal of symbolic computation, 13, 42-49, (1997) · Zbl 0872.68052
[4] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. of symbolic computation, 9, 251-280, (1990) · Zbl 0702.65046
[5] S. Eckhardt, A. Mühling, J. Nowak, Fast lowest common ancestor computations in dags, in: Proc. of ESA 2007, 2007, pp. 705-716 · Zbl 1151.68736
[6] Czumaj, A.; Kowaluk, M.; Lingas, A., Faster algorithms for finding lowest common ancestors in directed acyclic graphs, The special ICALP 2005 issue, Theoretical computer science, 380, 1-2, 37-46, (2007) · Zbl 1118.68102
[7] M. Kowaluk, A. Lingas, Unique lowest common ancestors in dags are almost as easy as matrix multiplication, in: Proc. of ESA 2007, 2007, pp. 265-274 · Zbl 1151.68429
[8] Galil, Z.; Margalit, O., Witnesses for Boolean matrix multiplication and shortest paths, Journal of complexity, 417-426, (1993) · Zbl 0977.68562
[9] Huang, X.; Pan, V.Y., Fast rectangular matrix multiplications and applications, Journal of complexity, 14, 257-299, (1998) · Zbl 0919.65030
[10] P. Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, in: Proc. 13th Symposium on Discrete Algorithms (SODA), 2002, pp. 697-704 · Zbl 1093.68540
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.