Following Ergun et al. (JCSS 2000), we consider testing group properties and focus on the problem of testing whether a binary operation is a group operation.
That is, given a finite set $S$ and oracle access to a function $f:S\times S \to S$, we wish to distinguish the case that ... more >>>

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 >>>