TR24-049 Authors: Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

Publication: 10th March 2024 08:24

Downloads: 113

Keywords:

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.