Gąsieniec, Leszek; Kowaluk, Mirosław; Lingas, Andrzej Faster multi-witnesses for Boolean matrix multiplication. (English) Zbl 1190.65073 Inf. Process. Lett. 109, No. 4, 242-247 (2009). Cited in 1 ReviewCited in 7 Documents MSC: 65F99 Numerical linear algebra 15B34 Boolean and Hadamard matrices Keywords:Boolean matrix multiplication; witnesses for Boolean matrix product; time complexity PDF BibTeX XML Cite \textit{L. Gąsieniec} et al., Inf. Process. Lett. 109, No. 4, 242--247 (2009; Zbl 1190.65073) 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.