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.” […]