We knew the best threshold-circuit lower bounds long ago

Thoughts 2019-08-20

Summary:

For more than 20 years we’ve had lower bounds for threshold circuits of depth [IPS97], for a fixed . There have been several “explanations” for the lack of progress [AK10]. Recently Chen and Tell have given a better explanation showing that you can’t even improve the result to a better without proving “the whole thing.” […]

Link:

https://emanueleviola.wordpress.com/2019/06/25/we-knew-the-best-threshold-circuit-lower-bounds-long-ago/

From feeds:

Online Mathematical Communication » Thoughts

Tags:

bounds

Authors:

Manu

Date tagged:

08/20/2019, 19:24

Date published:

06/25/2019, 14:02