Re:Computer Scientists Prove That Certain Problems Are Truly...
by tromp on Friday May 13, 2022 @04:02AM
(#31364639)
There is no link to an actual article, but I found a recent paper "Improved Low-Depth Set-Multilinear Circuit Lower Bounds" by Kush and Saraf [1] that
includes this reference
[LST22] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Set-multilinear and noncommutative formula lower bounds for iterated matrix multiplication. To appear in STOC
that appears to be the subject of this quanta article,
and the new paper claims to improve upon their work.
From what I gather, these papers construct some polynomial f of degree n in VNP defined over poly(n) many variables, such that any product-depth ∆ set-multilinear formula computing f has size at least a certain exponential in ∆.
Re:Computer Scientists Prove That Certain Problems Are Truly...
by LeegleechN on Friday May 13, 2022 @12:04PM
(#31369321)
No, they can solve integer factoring. This result shows that polynomial factoring is fundamentally different from integer factoring. The latter is believed to not be NP Hard.
[LST22] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Set-multilinear and noncommutative formula lower bounds for iterated matrix multiplication. To appear in STOC
that appears to be the subject of this quanta article, and the new paper claims to improve upon their work. From what I gather, these papers construct some polynomial f of degree n in VNP defined over poly(n) many variables, such that any product-depth ∆ set-multilinear formula computing f has size at least a certain exponential in ∆.
[1] Improved Low-Depth Set-Multilinear Circuit Lower Bounds