2 ms·
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
by tromp 4y ago
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 ∆.
[1] Improved Low-Depth Set-Multilinear Circuit Lower Bounds