The seminal work of Ahn, Guha, and McGregor in 2012 introduced the graph sketching technique and used it to present the first streaming algorithms for various graph problems over dynamic streams with both insertions and deletions of edges. This includes algorithms for cut sparsification, spanners, matchings, and minimum spanning trees ... more >>>

Given a distribution over $[n]^n$ such that any $k$ coordinates need $k/\log^{O(1)}n$ bits of communication to sample, we prove that any map that samples this distribution from uniform cells requires locality $\Omega(\log(n/k)/\log\log(n/k))$. In particular, we show that for any constant $\delta>0$, there exists $\varepsilon=2^{-\Omega(n^{1-\delta})}$ such that $\Omega(\log n/\log\log n)$ non-adaptive ... more >>>

We consider the following problem: Given an $n \times n$ multiplication table, decide whether it is a Cayley multiplication table of a group. Among deterministic algorithms for this problem, the best known algorithm is implied by F. W. Light's associativity test (1949) and has running time of $O(n^2 \log n)$. ... more >>>