ECCC-Report TR24-049https://eccc.weizmann.ac.il/report/2024/049Comments and Revisions published for TR24-049en-usSun, 10 Mar 2024 08:24:16 +0200
Paper TR24-049
| Oblivious Classes Revisited: Lower Bounds and Hierarchies |
Karthik Gajulapalli,
Zeyong Li,
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2024/049In 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.Sun, 10 Mar 2024 08:24:16 +0200https://eccc.weizmann.ac.il/report/2024/049