The existence of "unstructured" hard languages in $\text{NP}\cap\text{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\text{P}$ is separated from $\text{NP}\cap\text{coNP}$ relative to a random oracle, a question that remained open ever since. While a hard language in $\text{NP}\cap\text{coNP}$ can be constructed in a black-box way ... more >>>

In this paper, we prove the first super-polynomial and, in fact, exponential lower bound for the model of sum of read-once oblivious algebraic branching programs (ROABPs). In particular, we give an explicit polynomial such that any sum of ROABPs
(equivalently, sum of *ordered* set-multilinear branching programs, each with a ... more >>>

We study the problem of whether \emph{persistent} randomness is helpful for polynomial-time algorithms that only use \emph{logarithmic} space. In more detail, we consider the class $\searchBPLs$, of \emph{search}-problems that are solvable by a polynomial-time Probabilistic Logspace TMs with \emph{2-way} access (i.e., with multiple, as opposed to one-time, access) to a ... more >>>