Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Afshani, Peyman; Freksen, Casper Benjamin; Kamma, Lior; Larsen, Kasper Green http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-105861
URL:

; ; ;

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: 2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI