5 citations · 12 across the 9 of their papers we have counts for
13 papers
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<…
The Approximate Degree of DNF and CNF Formulas
Alexander A. Sherstov
The approximate degree of a Boolean function is the minimum degree of a real polynomial that approximates pointwise: for a…
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}…
Quantum Communication Complexity of Distribution Testing
Aleksandrs Belovs, Arturo Castellanos, François Le Gall +2
The classical communication complexity of testing closeness of discrete distributions has recently been studied by Andoni, Malkin and Nosatzki (ICALP'19). In this problem, two play…
Vanishing-Error Approximate Degree and QMA Complexity
Alexander A. Sherstov, Justin Thaler
The -approximate degree of a function is the least degree of a multivariate real polynomial such that for all . We det…
The Hardest Halfspace
Alexander A. Sherstov
We study the approximation of halfspaces in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit cons…