Document Open Access Logo

On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress

Author Marvin Künnemann

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.56.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Marvin Künnemann
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Cite AsGet BibTex

Marvin Künnemann. On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 56:1-56:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.56

Abstract

Motivated by studying the power of randomness, certifying algorithms and barriers for fine-grained reductions, we investigate the question whether the multiplication of two n x n matrices can be performed in near-optimal nondeterministic time O~(n^2). Since a classic algorithm due to Freivalds verifies correctness of matrix products probabilistically in time O(n^2), our question is a relaxation of the open problem of derandomizing Freivalds' algorithm. We discuss consequences of a positive or negative resolution of this problem and provide potential avenues towards resolving it. Particularly, we show that sufficiently fast deterministic verifiers for 3SUM or univariate polynomial identity testing yield faster deterministic verifiers for matrix multiplication. Furthermore, we present the partial algorithmic progress that distinguishing whether an integer matrix product is correct or contains between 1 and n erroneous entries can be performed in time O~(n^2) - interestingly, the difficult case of deterministic matrix product verification is not a problem of "finding a needle in the haystack", but rather cancellation effects in the presence of many errors. Our main technical contribution is a deterministic algorithm that corrects an integer matrix product containing at most t errors in time O~(sqrt{t} n^2 + t^2). To obtain this result, we show how to compute an integer matrix product with at most t nonzeroes in the same running time. This improves upon known deterministic output-sensitive integer matrix multiplication algorithms for t = Omega(n^{2/3}) nonzeroes, which is of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • matrix product verification
  • certifying computation
  • fine-grained complexity and algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15), pages 1681-1697, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.112.
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS'14), pages 434-443, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.53.
  3. Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15), pages 218-230, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.17.
  4. Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences, 54(2):255-262, 1997. URL: http://dx.doi.org/10.1006/jcss.1997.1388.
  5. Rasmus Resen Amossen and Rasmus Pagh. Faster join-projects and sparse matrix multiplications. In Proc. 12th International Conference on Database Theory (ICDT'09), pages 121-126, 2009. URL: http://dx.doi.org/10.1145/1514894.1514909.
  6. Ilya Baran, Erik D. Demaine, and Mihai Patrascu. Subquadratic algorithms for 3SUM. Algorithmica, 50(4):584-596, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9036-3.
  7. Michael Ben-Or and Prasoon Tiwari. A deterministic algorithm for sparse multivariate polynominal interpolation (extended abstract). In Proc. 20th Annual ACM Symposium on Theory of Computing (STOC'88), pages 301-309, 1988. URL: http://dx.doi.org/10.1145/62212.62241.
  8. Markus Bläser. Fast matrix multiplication. Theory of Computing, Graduate Surveys, 5:1-60, 2013. URL: http://dx.doi.org/10.4086/toc.gs.2013.005.
  9. Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams. Truly sub-cubic algorithms for language edit distance and RNA-folding via fast bounded-difference min-plus product. In Proc. 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS'16), pages 375-384, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.48.
  10. Harry Buhrman and Robert Spalek. Quantum verification of matrix products. In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06), pages 880-889, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109654.
  11. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility. In Proc. 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS'16), pages 261-270, 2016. URL: http://dx.doi.org/10.1145/2840728.2840746.
  12. Timothy M. Chan. More logarithmic-factor speedups for 3SUM, (median, +)-convolution, and some geometric 3SUM-hard problems. In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'18), pages 881-897, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.57.
  13. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal on Symbolic Computation, 9(3):251-280, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80013-2.
  14. Charles M. Fiduccia. Polynomial evaluation via the division algorithm: The fast Fourier transform revisited. In Proc. 4th Annual ACM Symposium on Theory of Computing (STOC'72), pages 88-93, 1972. URL: http://dx.doi.org/10.1145/800152.804900.
  15. Rusins Freivalds. Fast probabilistic algorithms. In Proc. 8th International Symposium on Mathematical Foundations of Computer Science (MFCS'79), pages 57-69, 1979. URL: http://dx.doi.org/10.1007/3-540-09526-8_5.
  16. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Computational Geometry, 5:165-185, 1995. URL: http://dx.doi.org/10.1016/0925-7721(95)00022-2.
  17. Leszek Gasieniec, Christos Levcopoulos, Andrzej Lingas, Rasmus Pagh, and Takeshi Tokuyama. Efficiently correcting matrix products. Algorithmica, 79(2):428-443, 2017. URL: http://dx.doi.org/10.1007/s00453-016-0202-3.
  18. Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. In Proc. 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS'14), pages 621-630, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.72.
  19. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  20. Mark A. Iwen and Craig V. Spencer. A note on compressed sensing and the complexity of matrix multiplication. Information Processing Letters, 109(10):468-471, 2009. URL: http://dx.doi.org/10.1016/j.ipl.2009.01.010.
  21. Riko Jacob and Morten Stöckel. Fast output-sensitive matrix multiplication. In Proc. 23rd Annual European Symposium on Algorithms (ESA'15), pages 766-778, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_64.
  22. Zahra Jafargholi and Emanuele Viola. 3SUM, 3XOR, triangles. Algorithmica, 74(1):326-343, 2016. URL: http://dx.doi.org/10.1007/s00453-014-9946-9.
  23. Stacey Jeffery, Robin Kothari, and Frédéric Magniez. Improving quantum query complexity of boolean matrix multiplication using graph collision. In Proc. 39th International Colloquium on Automata, Languages, and Programming (ICALP'12), pages 522-532, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_44.
  24. Erich Kaltofen and Yagati N. Lakshman. Improved sparse multivariate polynomial interpolation algorithms. In Proc. 1st International Symposium on Symbolic and Algebraic Computation (ISSAC'88), pages 467-474, 1988. URL: http://dx.doi.org/10.1007/3-540-51084-2_44.
  25. Daniel M. Kane, Shachar Lovett, and Shay Moran. Near-optimal linear decision trees for k-SUM and related problems. CoRR, abs/1705.01720, 2017. To appear in STOC'18. URL: http://arxiv.org/abs/1705.01720.
  26. Tracy Kimbrel and Rakesh K. Sinha. A probabilistic algorithm for verifying matrix products using O(n²) time and log₂ n + O(1) random bits. Information Processing Letters, 45(2):107-110, 1993. URL: http://dx.doi.org/10.1016/0020-0190(93)90224-W.
  27. Marvin Künnemann. On nondeterministic derandomization of Freivalds' algorithm: Consequences, avenues and algorithmic progress. CoRR, abs/1806.09189, 2018. URL: http://arxiv.org/abs/1806.09189.
  28. Konstantin Kutzkov. Deterministic algorithms for skewed matrix products. In Proc. 30th International Symposium on Theoretical Aspects of Computer Science (STACS'13), pages 466-477, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2013.466.
  29. François Le Gall. Powers of tensors and fast matrix multiplication. In Proc. 39th International Symposium on Symbolic and Algebraic Computation (ISSAC'14), pages 296-303, 2014. URL: http://dx.doi.org/10.1145/2608628.2608664.
  30. Andrzej Lingas. A fast output-sensitive algorithm for boolean matrix multiplication. In Proc. 17th Annual European Symposium on Algorithms (ESA'09), pages 408-419, 2009. URL: http://dx.doi.org/10.1007/978-3-642-04128-0_37.
  31. Ross M. McConnell, Kurt Mehlhorn, Stefan Näher, and Pascal Schweitzer. Certifying algorithms. Computer Science Review, 5(2):119-161, 2011. URL: http://dx.doi.org/10.1016/j.cosrev.2010.09.009.
  32. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing, 22(4):838-856, 1993. URL: http://dx.doi.org/10.1137/0222053.
  33. Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 026(2):415-419, 1985. URL: http://eudml.org/doc/17394.
  34. Rasmus Pagh. Compressed matrix multiplication. ACM Transactions on Computation Theory, 5(3):9:1-9:17, 2013. URL: http://dx.doi.org/10.1145/2493252.2493254.
  35. Daniel S. Roche. Error correction in fast matrix multiplication and inverse. CoRR, abs/1802.02270, 2018. URL: http://arxiv.org/abs/1802.02270.
  36. Claus-Peter Schnorr and C. R. Subramanian. Almost optimal (on the average) combinatorial algorithms for boolean matrix product witnesses, computing the diameter (extended abstract). In Proc. 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'98), pages 218-231, 1998. URL: http://dx.doi.org/10.1007/3-540-49543-6_18.
  37. Victor Shoup. On the deterministic complexity of factoring polynomials over finite fields. Information Processing Letters, 33(5):261-267, 1990. URL: http://dx.doi.org/10.1016/0020-0190(90)90195-4.
  38. Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13(4):354-356, Aug 1969. URL: http://dx.doi.org/10.1007/BF02165411.
  39. Terence Tao, Ernest Croot III, and Harald Helfgott. Deterministic methods to find primes. Mathematics of Computation, 81(278):1233-1246, 2012. URL: http://dx.doi.org/10.1090/S0025-5718-2011-02542-1.
  40. Leslie G. Valiant. General context-free recognition in less than cubic time. Journal of Computer and System Sciences, 10(2):308-315, 1975. URL: http://dx.doi.org/10.1016/S0022-0000(75)80046-8.
  41. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proc. 44th Annual ACM Symposium on Theory of Computing Conference (STOC'12), pages 887-898, 2012. URL: http://dx.doi.org/10.1145/2213977.2214056.
  42. Virginia Vassilevska Williams. Fine-grained algorithms and complexity. In Proc. 21st International Conference on Database Theory (ICDT'18), pages 1:1-1:1, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICDT.2018.1.
  43. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Proc. 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS'10), pages 645-654, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.67.
  44. Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra (3. ed.). Cambridge University Press, 2013. Google Scholar
  45. Jirí Wiedermann. Fast nondeterministic matrix multiplication via derandomization of Freivalds' algorithm. In Proc. 8th IFIP International Conference on Theoretical Computer Science (TCS'14), pages 123-135, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44602-7_11.
  46. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proc. 46th Annual ACM Symposium on Theory of Computing (STOC'14), pages 664-673, 2014. URL: http://dx.doi.org/10.1145/2591796.2591811.
  47. Ryan Williams. Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In Proc. 31st Conference on Computational Complexity (CCC'16), pages 2:1-2:17, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.2.
  48. Raphael Yuster and Uri Zwick. Fast sparse matrix multiplication. ACM Transactions on Algorithms, 1(1):2-13, 2005. URL: http://dx.doi.org/10.1145/1077464.1077466.
  49. Richard Zippel. Interpolating polynomials from their values. Journal of Symbolic Computation, 9(3):375-403, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80018-1.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact