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

We continue the study of the Stoquastic Local Hamiltonian problem, a physically motivated restriction of the $\QMA$-complete Local Hamiltonian problem \cite{KSV02}. For the $\beta$-gapped, frustration-free case, \citet{BBT06} showed that the problem is $\MA$-complete when $\beta= \frac{1}{\poly(n)}$. \citet{AG19} derandomized this algorithm and proved membership in $\NP$ for constant gap $\beta = ... more >>>