We study sparse matrix multiplication in the low-bandwidth model: $n$ computers multiply two $n\times n$ matrices, and each computer can send and receive one $O(\log n)$-bit message per round. The input matrices are uniformly sparse, meaning that there are at most $d$ nonzero entries in each row and column, and the task is to compute a uniformly sparse part of their product. In prior work, Gupta et al.~(SPAA 2022) presented an $O(d^{1.907})$-round algorithm over fields for this problem when the sparsity structure is globally known in advance (this is referred to as the supported setting). The upper bound was later improved to $O(d^{1.832})$ rounds. In this work, we give a deterministic algorithm that solves this problem in $O(d^{3/2})$ rounds in the supported setting, improving the previous bounds over fields and semirings.
We study the reachability problem in directed surface-embedded graphs under two structural restrictions, using isolating weight assignments. First, we consider graphs whose underlying undirected embeddings contain at most polynomially many simple surface non-separating cycles. We develop a polynomially bounded, logspace-computable skew-symmetric edge-weight assignment with nonzero circulation around every simple cycle. This yields an unambiguous logspace (UL) upper bound for directed reachability. The construction also gives an SPL upper bound for bipartite perfect matching in the corresponding undirected graph class. Second, for $g$-genus directed graphs admitting a balanced hierarchical genus decomposition with $O(\log n)$ crossing edges at every partition, we obtain an unambiguous $O(\log g \cdot \log n)$-space bound for reachability. Our approach combines path-isolating weights for lower-genus subgraphs using polynomially bounded FKS hashing refinements at successive merging levels.