Document Open Access Logo

Lower Bounds for Multiplication via Network Coding

Authors Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.10.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Author Details

Peyman Afshani
  • Computer Science Department, Aarhus University, Denmark
Casper Benjamin Freksen
  • Computer Science Department, Aarhus University, Denmark
Lior Kamma
  • Computer Science Department, Aarhus University, Denmark
Kasper Green Larsen
  • Computer Science Department, Aarhus University, Denmark

Funding

Peyman Afshani is supported by DFF (Det Frie Forskningsraad) of Danish Council for Independent Research under grant ID DFF-7014-00404. Casper Benjamin Freksen and Lior Kamma are supported by Villum Young Investigator Grant 13163. Kasper Green Larsen is supported by Villum Young Investigator Grant 13163 and an AUFF Starting Grant.

Cite AsGet BibTex

Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, and Kasper Green Larsen. Lower Bounds for Multiplication via Network Coding. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 10:1-10:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.10

Abstract

Multiplication is one of the most fundamental computational problems, yet its true complexity remains elusive. The best known upper bound, very recently proved by Harvey and van der Hoeven (2019), shows that two n-bit numbers can be multiplied via a boolean circuit of size O(n lg n). In this work, we prove that if a central conjecture in the area of network coding is true, then any constant degree boolean circuit for multiplication must have size Omega(n lg n), thus almost completely settling the complexity of multiplication circuits. We additionally revisit classic conjectures in circuit complexity, due to Valiant, and show that the network coding conjecture also implies one of Valiant’s conjectures.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Circuit complexity
Keywords
  • Circuit Complexity
  • Circuit Lower Bounds
  • Multiplication
  • Network Coding
  • Fine-Grained Complexity

Metrics

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

References

  1. Micah Adler, Nicholas J. A. Harvey, Kamal Jain, Robert Kleinberg, and April Rasala Lehman. On the Capacity of Information Networks. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06, pages 241-250. Society for Industrial and Applied Mathematics, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109585.
  2. Mark Braverman, Sumegha Garg, and Ariel Schvartzman. Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, pages 18:1-18:18, 2017. Google Scholar
  3. Raphaël Clifford and Markus Jalsenius. Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, pages 593-604, 2011. Google Scholar
  4. Stephen Arthur Cook. On the minimum computation time of functions. PhD thesis, Harvard University, 1966. Google Scholar
  5. Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi. Lower Bounds for External Memory Integer Sorting via Network Coding. In Proceedings of the 52st Symposium on Theory of Computing, STOC 2019, 2019. To appear. Google Scholar
  6. Martin Fürer. Faster Integer Multiplication. SIAM Journal on Computing, 39(3):979-1005, 2009. URL: http://dx.doi.org/10.1137/070711761.
  7. D. Harvey and J. van der Hoeven. Integer multiplication in time O(n log n). Technical report, HAL, 2019. ěrb|http://hal.archives-ouvertes.fr/hal-02070778|. Google Scholar
  8. David Harvey and Joris van der Hoeven. Faster integer multiplication using short lattice vectors. CoRR, 2018. URL: http://arxiv.org/abs/1802.07932.
  9. Anatoly Alekseevich Karatsuba and Yurii Petrovich Ofman. Multiplication of Many-Digital Numbers by Automatic Computers. Proceedings of the USSR Academy of Sciences, 145:293-294, 1962. Google Scholar
  10. Zongpeng Li and Baochun Li. Network Coding: The Case of Multiple Unicast Sessions. In Proceedings of the 42nd Annual Allerton Conference on Communication, Control, and Computing, 2004. Google Scholar
  11. Jacques Morgenstern. Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform. Journal of the ACM, 20(2):305-306, 1973. URL: http://dx.doi.org/10.1145/321752.321761.
  12. Stephen Ponzio. A Lower Bound for Integer Multiplication with Read-Once Branching Programs. SIAM J. Comput., 28(3):798-815, 1998. Google Scholar
  13. Søren Riis. Information flows, graphs and their guessing numbers. The Electronic Journal of Combinatorics, 14(1), 2007. Google Scholar
  14. Arnold Schönhage and Volker Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7(3):281-292, September 1971. URL: http://dx.doi.org/10.1007/BF02242355.
  15. Andrei Leonovich Toom. The complexity of a scheme of functional elements realizing the multiplication of integers. Proceedings of the USSR Academy of Sciences, 150(3):496-498, 1963. Google Scholar
  16. Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In Mathematical Foundations of Computer Science 1977, pages 162-176, 1977. Google Scholar
  17. Leslie G. Valiant. Why is Boolean Complexity Theory Difficult? In Proceedings of the London Mathematical Society Symposium on Boolean Function Complexity, pages 84-94, 1992. Google Scholar
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