Abstract
We study the complexity of the so called semi-disjoint bilinear forms over different semi-rings, in particular the n-dimensional vector convolution and \(n\times n\) matrix product. We consider a powerful unit-cost computational model over the ring of integers allowing for several additional operations and generation of large integers. We show the following dichotomy for such a powerful model: while almost all arithmetic semi-disjoint bilinear forms have the same asymptotic time complexity as that yielded by naive algorithms, matrix multiplication, the so called distance matrix product, and vector convolution can be solved in a linear number of steps. It follows in particular that in order to obtain a non-trivial lower bounds for these three basic problems one has to assume restrictions on the set of allowed operations and/or the size of used integers.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aho, A.V., Hopcroft, J.E., Ullman, J.: The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, Reading (1974)
Alon, N., Galil, Z., Margalit, O.: On the exponent of all pairs shortest path problem. J. Comput. Syst. Sci. 54, 25–51 (1997)
Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., Patrascu, M., Taslakian, P.: Necklaces, convolutions and X+Y. Algorithmica 69, 294–314 (2014)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symbolic Comput. 9, 251–280 (1990)
Fisher, M.J., Paterson, M.S.: String-matching and other products. In: Proceedings of the 7th SIAM-AMS Complexity of Computation, pp. 113–125 (1974)
Freivalds, R.: Probabilistic machines can use less running time. In: Proceedings of the IFIP Congress, pp. 839–842 (1977)
Hartmanis, J., Simon, J.: On the power of multiplication in random access machines. In: Proceedings of the SWAT (FOCS), pp. 13–23 (1974)
Korec, I., Wiedermann, J.: Deterministic verification of integer matrix multiplication in quadratic time. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 375–382. Springer, Cham (2014). doi:10.1007/978-3-319-04298-5_33
Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 296–303 (2014)
Mehlhorn, K., Galil, Z.: Monotone switching circuits and boolean matrix product. Computing 16, 99–111 (1976)
Pratt, R.: The power of negative thinking in multiplying boolean matrices. SIAM J. Comput. 4(3), 326–330 (1975)
Raz, R.: On the complexity of matrix product. In: Proceedings of the STOC, pp. 144–151 (2002)
Romani, F.: Shortest path problem is not harder than matrix multiplications. Inf. Process. Lett. 4(6), 134–136 (1980)
Schnorr, C.-P.: A lower bound on the number of additions in monotone computations. Theoret. Comput. Sci. 2(3), 305–315 (1976)
Schönhage, A.: On the power of random access machines. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol. 71, pp. 520–529. Springer, Heidelberg (1979). doi:10.1007/3-540-09510-1_42
Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13, 354–356 (1969)
Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science, New York, Stuggart (1987)
Wiedermann, J.: Fast nondeterministic matrix multiplication via derandomization of freivalds’ algorithm. In: Diaz, J., Lanese, I., Sangiorgi, D. (eds.) TCS 2014. LNCS, vol. 8705, pp. 123–135. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44602-7_11
Yuval, G.: An algorithm for finding all shortest paths using \(N^{2.81}\) infinite-precision multiplication. Inf. Process. Lett. 11(3), 155–156 (1976)
Vassilevska Williams, V.: Multiplying matrices faster than coppersmith-winograd. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 887–898 (2012)
Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49(3), 289–317 (2002)
Acknowledgments
The authors are grateful to Christos Levcopoulos for valuable comments. This research has been supported in part by Swedish Research Council grant 621-2011-6179.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Lingas, A., Persson, M., Sledneu, D. (2017). Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model. In: Gopal, T., Jäger , G., Steila, S. (eds) Theory and Applications of Models of Computation. TAMC 2017. Lecture Notes in Computer Science(), vol 10185. Springer, Cham. https://doi.org/10.1007/978-3-319-55911-7_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-55911-7_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55910-0
Online ISBN: 978-3-319-55911-7
eBook Packages: Computer ScienceComputer Science (R0)