Improved output-sensitive quantum algorithms for Boolean matrix multiplication. (English) Zbl 1422.68079
Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1464-1476 (2012).
MSC:
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 15B34 | Boolean and Hadamard matrices |
References:
| [1] | Andris Ambainis, Quantum Walk Algorithm for Element Distinctness, SIAM Journal on Computing, v.37 n.1, p.210-239, April 2007 [doi>10.1137/S0097539705447311] · Zbl 1134.81010 · doi:10.1137/S0097539705447311 |
| [2] | Rasmus Resen Amossen , Rasmus Pagh, Faster join-projects and sparse matrix multiplications, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia [doi>10.1145/1514894.1514909] · Zbl 1311.68188 |
| [3] | Arlazarov, V. L., Dinic, E. A., Kronrod, M. A., and Faradzev, I. A. On economical construction of the transitive closure of a directed graph. Soviet Mathematics Doklady (English translation) 11, 5 (1970), 1209-1210. · Zbl 0214.23601 |
| [4] | Nikhil Bansal , Ryan Williams, Regularity Lemmas and Combinatorial Algorithms, Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, p.745-754, October 25-27, 2009 [doi>10.1109/FOCS.2009.76] · Zbl 1292.05242 · doi:10.1109/FOCS.2009.76 |
| [5] | Boyer, M., Brassard, G., Høyer, P., and Tapp, A. Tight bounds on quantum searching. Fortschritte der Physik 46, 4-5 (1998), 493-505. |
| [6] | Gilles Brassard , Peter Høyer , Alain Tapp, Quantum Counting, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.820-831, July 13-17, 1998 · Zbl 1508.68118 |
| [7] | Harry Buhrman , Ronald de Wolf, Complexity measures and decision tree complexity: a survey, Theoretical Computer Science, v.288 n.1, p.21-43, 9 October 2002 [doi>10.1016/S0304-3975(01)00144-X] · Zbl 1061.68058 · doi:10.1016/S0304-3975(01)00144-X |
| [8] | Harry Buhrman , Robert Špalek, Quantum verification of matrix products, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.880-889, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109654] · Zbl 1192.81056 |
| [9] | Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2] · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2 |
| [10] | Dorit Dor , Shay Halperin , Uri Zwick, All-Pairs Almost Shortest Paths, SIAM Journal on Computing, v.29 n.5, p.1740-1759, March 2000 [doi>10.1137/S0097539797327908] · Zbl 0948.05047 · doi:10.1137/S0097539797327908 |
| [11] | M. J. Fischer , A. R. Meyer, Boolean matrix multiplication and transitive closure, Proceedings of the 12th Annual Symposium on Switching and Automata Theory (swat 1971), p.129-131, October 13-15, 1971 [doi>10.1109/SWAT.1971.4] · doi:10.1109/SWAT.1971.4 |
| [12] | Furman, M. E. Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph. Soviet Mathematics Doklady (English translation) 11, 5 (1970), 1252. · Zbl 0214.23602 |
| [13] | Zvi Galil , Oded Margalit, All pairs shortest distances for graphs with small integer length edges, Information and Computation, v.134 n.2, p.103-139, May 1, 1997 [doi>10.1006/inco.1997.2620] · Zbl 0879.68081 · doi:10.1006/inco.1997.2620 |
| [14] | Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, USA [doi>10.1145/237814.237866] · Zbl 0922.68044 |
| [15] | Itai, A., and Rodeh, M. Finding a minimum circuit in a graph. SIAM Journal on Computing 7, 4 (1978), 413-423. · Zbl 0386.68064 |
| [16] | Hartmut Klauck , Robert Sˇpalek , Ronald de Wolf, Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs, SIAM Journal on Computing, v.36 n.5, p.1472-1493, December 2006 [doi>10.1137/05063235X] · Zbl 1123.68045 · doi:10.1137/05063235X |
| [17] | Andrzej Lingas, A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication, Algorithmica, v.61 n.1, p.36-50, September 2011 [doi>10.1007/s00453-010-9441-x] · Zbl 1218.68195 · doi:10.1007/s00453-010-9441-x |
| [18] | Frédéric Magniez , Ashwin Nayak , Jérémie Roland , Miklos Santha, Search via Quantum Walk, SIAM Journal on Computing, v.40 n.1, p.142-164, February 2011 [doi>10.1137/090745854] · Zbl 1223.05289 · doi:10.1137/090745854 |
| [19] | Fre´de´ric Magniez , Miklos Santha , Mario Szegedy, Quantum Algorithms for the Triangle Problem, SIAM Journal on Computing, v.37 n.2, p.413-424, May 2007 [doi>10.1137/050643684] · Zbl 1166.68032 · doi:10.1137/050643684 |
| [20] | Munro, J. I. Efficient determination of the transitive closure of a directed graph. Information Processing Letters 1, 2 (1971), 56-58. · Zbl 0221.68030 |
| [21] | Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000 · Zbl 1049.81015 |
| [22] | Wojciech Rytter, Fast recognition of pushdown automaton and context-free languages, Information and Control, v.67 n.1-3, p.12-22, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80024-3] · Zbl 0611.68052 · doi:10.1016/S0019-9958(85)80024-3 |
| [23] | Claus-Peter Schnorr , C. R. Subramanian, Almost Optimal (on the average) Combinatorial Algorithms for Boolean Matrix Product Witnesses, Computing the Diameter (Extended Abstract), Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.218-231, October 08-10, 1998 |
| [24] | Raimund Seidel, On the all-pairs-shortest-path problem in unweighted undirected graphs, Journal of Computer and System Sciences, v.51 n.3, p.400-403, Dec. 1995 [doi>10.1006/jcss.1995.1078] · Zbl 1295.05240 · doi:10.1006/jcss.1995.1078 |
| [25] | Avi Shoshan , Uri Zwick, All Pairs Shortest Paths in Undirected Graphs with Integer Weights, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.605, October 17-18, 1999 |
| [26] | Leslie G. Valiant, General context-free recognition in less than cubic time, Journal of Computer and System Sciences, v.10 n.2, p.308-314, April, 1975 [doi>10.1016/S0022-0000(75)80046-8] · Zbl 0312.68042 · doi:10.1016/S0022-0000(75)80046-8 |
| [27] | Virginia Vassilevska Williams , Ryan Williams, Subcubic Equivalences between Path, Matrix and Triangle Problems, Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, p.645-654, October 23-26, 2010 [doi>10.1109/FOCS.2010.67] · Zbl 1426.68133 · doi:10.1109/FOCS.2010.67 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
