按年被提到
20192019 · 2 次2026
数学、逻辑与理论›数学猜想与重大证明·arXiv:1902.10935 · cs.DS

Lower Bounds for Multiplication via Network Coding

Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen · 2019
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2019-03-03 · 最近 2020-07-22
3不同的人
2活跃月份
3讨论串
7被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Multiplication is one of the most fundamental computational problems, yet its true complexity remains elusive. The best known upper bound, by Fürer, shows that two $n$-bit numbers can be multiplied via a boolean circuit of size $O(n \lg n \cdot 4^{\lg^*n})$, where $\lg^*n$ is the very slowly growing iterated logarithm. 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.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论moab · 2019-03

“This very recent paper shows a matching (conditional) lower bound of \Omega(n\log n): https://arxiv.org/abs/1902.10935 (the hardness is from a conjecture in network coding).”

Integer multiplication in time O(n log n) [pdf]原评论 ↗
评论ogogmad · 2020-07

“According to the article, it rests on a plausible conjecture. I need to read further. [edit] According to the abstract of the paper referred to in the article (https://arxiv.org/abs/1902.10935) it rests on a "central conjecture in the area of network coding". Make of that what you will.”

Mathematicians discover a perfect way to multiply (2019)原评论 ↗
被提交为 story · 1 次