5 citations · 5 across the 2 of their papers we have counts for
2 papers
cs.CC2024
The Communication Complexity of Approximating Matrix Rank
Alexander A. Sherstov, Andrey A. Storozhenko
We fully determine the communication complexity of approximating matrix rank, over any finite field . We study the most general version of this problem, where $0\leq r<…
cs.CC2020★ 5 cited
An Optimal Separation of Randomized and Quantum Query Complexity
Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order sum to at most $c^{\ell}\sqrt{\binom{d}{\ell}(1+\log n)^{\ell-1}…