Zobrazeno 1 - 10
of 44
pro vyhledávání: '"Alexander A. Sherstov"'
Autor:
Alexander A. Sherstov, François Le Gall, Guillaume Malod, Aleksandrs Belovs, Arturo Castellanos
Publikováno v:
Quantum Information and Computation. 21:1261-1273
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 players each receive $t$ samples from one distribution over $[n]$, and the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9d4be9b3ce100916be00320ec7d584e7
https://doi.org/10.26421/qic21.15-16-1
https://doi.org/10.26421/qic21.15-16-1
Publikováno v:
ACM Transactions on Computation Theory. 12:1-28
A major goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems f :({0, 1} n ) k → {0, 1} with k > log n parties. We study the problems of inner product and set disjointness and determine their ran
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::66849ca289922d30592e7e08822b8783
https://doi.org/10.1145/3428671
https://doi.org/10.1145/3428671
Autor:
Alexander A. Sherstov
Publikováno v:
computational complexity. 30
We study the approximation of halfspaces $$h:\{0,1\}^n\to\{0,1\}$$ h : { 0 , 1 } n → { 0 , 1 } in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the “hardest” halfspac
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::73c638c54cca81cf9a881448d47c2e9b
https://doi.org/10.1007/s00037-021-00211-4
https://doi.org/10.1007/s00037-021-00211-4
Autor:
Alexander A. Sherstov
Publikováno v:
Theory of Computing. 14:1-17
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ce0388b8446bad296bc8ecc505cec888
https://doi.org/10.4086/toc.2018.v014a022
https://doi.org/10.4086/toc.2018.v014a022
Autor:
Pei Wu, Alexander A. Sherstov
Publikováno v:
SIAM Journal on Computing. 52:STOC19-1
The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::76a57a316e51e130376f2014d09987b8
https://doi.org/10.1137/20m1312459
https://doi.org/10.1137/20m1312459
Autor:
Pei Wu, Alexander A. Sherstov
Publikováno v:
STOC
The threshold degree of a Boolean function f∶{0,1}n→{0,1} is the minimum degree of a real polynomial p that represents f in sign: sgn p(x)=(−1)f(x). A related notion is sign-rank, defined for a Boolean matrix F=[Fij] as the minimum rank of a re
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::083184e353bb032af329fef29a0366f7
https://doi.org/10.1145/3313276.3316408
https://doi.org/10.1145/3313276.3316408
Autor:
Alexander A. Sherstov
Publikováno v:
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing.
The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5af589fdeb213fb495498862c931b508
https://doi.org/10.1145/3188745.3188958
https://doi.org/10.1145/3188745.3188958
Autor:
Pei Wu, Alexander A. Sherstov
Publikováno v:
FOCS
Interactive coding, pioneered by Schulman (FOCS ’92, STOC ’93), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::100e2b4afbf8ab3ca4653155f8e4695c
https://doi.org/10.1109/focs.2017.30
https://doi.org/10.1109/focs.2017.30
Autor:
Alexander A. Sherstov
Publikováno v:
Theory of Computing. 9:593-615
A basic question in any computational model is how to reliably compute a given function when the inputs or intermediate computations are subject to noise at a constant rate. Ideally, one would like to use at most a constant factor more resources comp
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7e53b6e39bc45a69d7e3c258a5c30e87
https://doi.org/10.4086/toc.2013.v009a018
https://doi.org/10.4086/toc.2013.v009a018
Autor:
Alexander A. Sherstov
Publikováno v:
Theory of Computing. 9:653-663
The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f within 1=3 at every point. We prove that the function V n i=1 W n j=1 xi j, known as the AND-OR tree, has approximate degree W(n). This lower
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4e5d0e709c58013de7278bf643c7c629
https://doi.org/10.4086/toc.2013.v009a020
https://doi.org/10.4086/toc.2013.v009a020