Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-250 | 12th October 2026 06:33

Input-oblivious complexity classes in the second level of the Polynomial Hierarchy

RSS-Feed

Abstract:

We continue to investigate input-oblivious computations and build a map of known and new complexity classes. In particular,
* We prove a new upper bound for $OL_2^P$ defined by Hirsch and Volkovich (STACS, 2026), which is a natural input-oblivious version of the $L_2^P$ class of Korten and Pitassi (FOCS, 2024): it is captured by symmetric (shared-witness) input-oblivious unambiguous computations with one query to a nondeterministic input-oblivious computation.
We introduce the corresponding class $SOUP$ and prove that it is closed under polynomial-time Turing reductions.
* We give an equivalent characterization of $OL_2^P$: a new symmetric input-oblivious class $OMIN$. We prove that $OMIN$ contains hard functions against fixed-polynomial size circuits.
* We prove a number of query aggregation results showing a number of containments and equivalences between input-oblivious complexity classes. In particular, we prove that $BPP^{OL_2^P}=OL_2^P$ and $O_2^P=ONP^{prONP}$. We also characterize a number of input-oblivious classes using the dot-operator.
* We extract a number of derandomization corollaries from our results: an upper bound for $BPP^{ONP}$, as well as the new characterization $OMA=BP\cdot prONP$, and new upper bounds for $MA$, $OMA$, $P^{prMA}$, $P^{OprMA}$. These improve and extend earlier bounds of Chakaravarthy and Roy (STACS, 2006) and Hirsch and Volkovich (STACS, 2026).



ISSN 1433-8092 | Imprint