Search Results

In this work we study oblivious complexity classes. These classes capture the power of interactive proofs where the prover(s) are only given the input size rather than the actual input. In particular, we study the connections between the symmetric polynomial time - S₂P and its oblivious counterpart - O₂P. Among our results: - For each k ∈ ℕ, we construct an explicit language L_k ∈ O₂P that cannot be computed by circuits of size n^k. - We prove a hierarchy theorem for O₂TIME. In particular, for any time constructible function t:ℕ → ℕ and any ε > 0 we show that: O₂TIME[t(n)] ⊊ O₂TIME[t(n)^{1 + ε}]. - We prove new structural results connecting O₂P and S₂P. - We make partial progress towards the resolution of an open question posed by Goldreich and Meir (TOCT 2015) that relates the complexity of NP to its oblivious counterpart - ONP. - We identify a natural class of problems in O₂P from computational Ramsey theory, that are not expected to be in 𝖯 or even BPP. To the best of our knowledge, these results constitute the first explicit fixed-polynomial lower bound and hierarchy theorem for O₂P. The smallest uniform complexity class for which such lower bounds were previously known was S₂P 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. Our techniques build upon the de-randomization framework of the powerful Range Avoidance problem that has yielded many new interesting explicit circuit lower bounds.