We prove several new results regarding the relationship between probabilistic time, BPTime(t), and alternating time, \Sigma_{O(1)} Time(t). Our main results are the following:

1) We prove that BPTime(t) \subseteq \Sigma_3 Time(t polylog(t)). Previous results show that BPTime(t) \subseteq \Sigma_2 Time(t^2 log t) (Sipser and Gacs, STOC '83; Lautemann, IPL '83) ... more >>>

This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the \mathrm{AC}^0[\oplus] basis (unbounded fan-in AND, OR, NOT and MOD_2 gates). We show, for all d(n) \le O(\frac{\log n}{\log\log n}), that there exist {\em polynomial-size depth-d circuits} that are not equivalent ... more >>>

We give two results on the size of AC0 circuits computing promise majority. \epsilon-promise majority is majority promised that either at most an \epsilon fraction of the input bits are 1, or at most \epsilon are 0.

First, we show super quadratic lower bounds on both monotone and general depth ... more >>>