Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.10
URN: urn:nbn:de:0030-drops-105861
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10586/
Afshani, Peyman ; Freksen, Casper Benjamin ; Kamma, Lior ; Larsen, Kasper Green
Lower Bounds for Multiplication via Network Coding
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{afshani_et_al:LIPIcs:2019:10586,
author = {Peyman Afshani and Casper Benjamin Freksen and Lior Kamma and Kasper Green Larsen},
title = {{Lower Bounds for Multiplication via Network Coding}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {10:1--10:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-109-2},
ISSN = {1868-8969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10586},
URN = {urn:nbn:de:0030-drops-105861},
doi = {10.4230/LIPIcs.ICALP.2019.10},
annote = {Keywords: Circuit Complexity, Circuit Lower Bounds, Multiplication, Network Coding, Fine-Grained Complexity}
}
| Keywords: | Circuit Complexity, Circuit Lower Bounds, Multiplication, Network Coding, Fine-Grained Complexity | |
| Seminar: | 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 04.07.2019 |
