We provide a uniform framework for proving the collapse of the hierarchy, $NC^1(\mathcal{C})$
for an exact arithmetic class $\mathcal{C}$ of polynomial degree. These hierarchies collapses all the way down to the third level of the ${AC}^0$-hierarchy, ${AC^0_3}(\mathcal{C})$. Our main collapsing exhibits are the classes \[\mathcal{C} \in \{{C}_={NC^1}, {C}_={L}, {C}_={SAC^1}, {C}_={P}\}.\]
more >>>

We precisely characterize the role of private randomness in the ability of Alice to send a message to Bob while minimizing the amount of information revealed to him. We show that if using private randomness a message can be transmitted while revealing $I$ bits of information, the transmission can be ... more >>>

Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class $\mathcal{C} \subseteq P/poly$ of Boolean circuits is exactly learnable with membership and equivalence queries in polynomial-time, then $EXP^{NP} \not \subseteq \mathcal{C}$ (the class $EXP^{NP}$ was subsequently improved to $P$ by Hitchcock and ... more >>>