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

We construct explicit hitting set generators for $\mathbb{F}_2$-polynomials in $n$ variables of degree at most $d$ with an almost optimal density, and seed length $O(d \log n+d^2)$, which is optimal for $d = O(\log n)$.

Second, we address large-field hitting set generators. The influential state-of-the-art construction by Guruswami and Xing ... more >>>