Reductions of self-reducible sets to depth-1 weighted threshold circuit classes, and sparse sets

Abstract

Let LT₁ denote the class of languages accepted by nonuniform families of polynomial size depth-1 circuits with a linear weighted threshold gate at the root. We show that disjunctive self-reducible bd-cylinders that many-one reduce to LT₁ are in P. It follows that for C∈{NP, Mod_kP, PP, C₌P}, if & Cscr; has a many-one hard problem in LT₁ then & Cscr;=P. As corollary, this result subsumes various collapse consequence results concerning reductions to sparse sets. We propose a technique by which some of these results for disjunctive self-reducible sets can be extended to Turing self-reducible sets. We show applications of this technique.