We study the consequences of NP having non-uniform polynomial size circuits of various types. We continue the work of Agrawal and Arvind~\cite{AA:96} who study the consequences of $\SAT$ being many-one reducible to functions computable by non-uniform circuits consisting of a single weighted threshold gate. ($\SAT \leq_m^p \LT$). They claim that as a consequence $\PTIME = \NP$ follows, but unfortunately their proof was incorrect. We take up this question and use results from computational learning theory to show that if $\SAT \leq_m^p \LT$ then $\PH = \PTIME^\NP$. We furthermore show that if $\SAT$ disjunctive truth-table (or majority truth-table) reduces to a sparse set then $\SAT \leq_m^p \LT$ and hence a collapse of $\PH$ to $\PTIME^\NP$ also follows. Lastly we show several interesting consequences of $\SAT \leq_{dtt}^p \SPARSE$.

Additional Metadata
THEME Life Sciences (theme 5), Logistics (theme 3)
Publisher CWI
Series CWI Deliverables
Citation
Buhrman, H, Fortnow, L, Hitchcock, J.M, & Loff Barreto, B. S. (2012). Learning Weak Reductions to Sparse Sets. CWI Deliverables. CWI.