Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-049 | 7th March 2024 19:29

Oblivious Classes Revisited: Lower Bounds and Hierarchies



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.

ISSN 1433-8092 | Imprint