Quantified derandomization of linear threshold circuits
Roei Tell · 2018
One of the prominent current challenges in complexity theory is the attempt to prove lower bounds for TC0, the class of constant-depth, polynomial-size circuits with majority gates. Relying on the results of Williams (2013), an appealing approach to prove such lower bounds is to construct a non-trivial derandomization algorithm for TC0. In this work we take a first step towards the latter goal, by proving the first positive results regarding the derandomization of TC0 circuits of depth d>2.