We study the subclass of $\mathrm{prAM}$ problems such that derandomizing the corresponding Arthur--Merlin verifier (i.e. to an $\mathrm{NP}$ verifier) reduces to the Range Avoidance problem ($\mathrm{Avoid}$), the total search problem of finding a string outside the range of an expanding circuit.

We prove a new ... more >>>

Determining the communication complexity of graph connectivity has been one of the longest standing open problems in communication complexity since the seminal work of Babai, Frankl, and Simon [FOCS'86]. A simple protocol transmits a spanning forest using $O(N\log N)$ communication on $N$-vertex graphs. While this was shown optimal for deterministic ... more >>>

We prove a linear query complexity lower bound for two-sided testing of graph isomorphism in the bounded-degree model.
Specifically, there are constants $d$ and $\varepsilon_0$ such that, for every sufficiently large $n$,
there exists an $n$-vertex graph $H_n$ of maximum degree at most $d$ such that testing isomorphism ... more >>>