The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about ... more >>>

We introduce a new family of *parallel* time-bounded Kolmogorov complexity measures ($KP^t$).
A string $w$ has low $KP^t$ complexity if any individual bit of $w$ can be decompressed from a "short" description using "few" parallel processors within at most $t$ steps.

The definition of $KP^t$ uses Parallel Random Access Machines ... more >>>

We study batch verification in QMA query and communication complexity, where the goal is to understand how the resources needed to verify $m$ copies of a Boolean function $f$ depend on $m$. We give a general technique for proving lower bounds on the witness-query tradeoff needed to batch verify a ... more >>>