Igor Mancini

IPS Problem 1: partial results and where they stop

Partial results on Problem 1 of Impagliazzo, Paturi and Saks (SIAM J. Comput. 1997), which asksfor the best exponent r in their restriction lemma for threshold circuits; r = 2 gives theirconstant θ = 1+√2 in the n^(1+c·θ^(-d)) wire lower bound for parity. For gates with weights i...