In this work we study oblivious complexity classes. Among our results:
1) For each k \in \mathbb{N}, we construct an explicit language L_k \in O_2P that cannot be computed by circuits of size n^k.
2) We prove a hierarchy theorem for O_2TIME. In particular, for any function t:\mathbb{N} \rightarrow \mathbb{N} we show that: O_2TIME[t(n)^4\log^9(t(n))] \not\subseteq O_2TIME[t(n)].
3) We prove new structural results connecting O_2P and S_2P.
4) We make partial progress towards the resolution of an open question posed by Goldreich and Meir (TOCT 2015).
5) We identify the first natural problem in O_2P, that is not expected to be in either P or even BPP.
To the best of our knowledge, these results constitute the first explicit fixed-polynomial lower bound, hierarchy theorem and hard natural problem for O_2P. The smallest uniform complexity class for which such lower bounds were previously known was S_2P due to Cai (JCSS 2007). In addition, this is the first uniform hierarchy theorem for a semantic class. All previous results required some non-uniformity.
In order to obtain some of the results in the paper, we introduce the notion of uniformly-sparse extensions which could be of independent interest.