Lower bounds for multiplication via network coding

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearch

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 Ω(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.

Original languageEnglish
Article number10
JournalLeibniz International Proceedings in Informatics, LIPIcs
Number of pages12
ISSN1868-8969
DOIs
Publication statusPublished - 2019
Event46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece
Duration: 9 Jul 201912 Jul 2019

Conference

Conference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
CountryGreece
CityPatras
Period09/07/201912/07/2019
SponsorCenter for Perspicuous Computing (CPEC), University of Patras

    Research areas

  • Circuit Complexity, Circuit Lower Bounds, Fine-Grained Complexity, Multiplication, Network Coding

See relations at Aarhus University Citationformats

ID: 160398439