Zobrazeno 1 - 7
of 7
pro vyhledávání: '"Mohammad Bavarian"'
Publikováno v:
Theory of Computing. 16:1-18
In the "correlated sampling" problem, two players are given probability distributions $P$ and $Q$, respectively, over the same finite set, with access to shared randomness. Without any communication, the two players are each required to output an ele
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::722496964812e369775e91d2920584b8
https://doi.org/10.4086/toc.2020.v016a012
https://doi.org/10.4086/toc.2020.v016a012
Publikováno v:
STOC
We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate - in other words,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f988c7db0e79c2212ede49d94873ed86
https://doi.org/10.1145/3055399.3055433
https://doi.org/10.1145/3055399.3055433
Autor:
Arturs Backurs, Mohammad Bavarian
Publikováno v:
IEEE Conference on Computational Complexity
For a function f over the discrete cube, the total L1 influence of f is defined as the sum of the L1 norm of the discrete derivatives of f in all n directions. In this work, we show that in the case of bounded functions this quantity can be upper bou
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e5dfac505fd2becb0632ff2ecbe1f105
https://doi.org/10.1109/ccc.2014.21
https://doi.org/10.1109/ccc.2014.21
Publikováno v:
Automata, Languages, and Programming ISBN: 9783662439470
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1bb41c1b54924d54fcb553cef3efb35b
https://doi.org/10.1007/978-3-662-43948-7_3
https://doi.org/10.1007/978-3-662-43948-7_3
Publikováno v:
Automata, Languages, and Programming ISBN: 9783662439470
ICALP (1)
ICALP (1)
Suppose two parties who are interested in performing certain distributed computational tasks are given access to a source of correlated random bits ρ. This source of correlated randomness could be quite useful to the parties for solving various dist
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d344dbaf9daed83a33bd56b77a0791ae
https://doi.org/10.1007/978-3-662-43948-7_13
https://doi.org/10.1007/978-3-662-43948-7_13
Publikováno v:
Automata, Languages, and Programming ISBN: 9783662439470
ICALP (1)
Lecture Notes in Computer Science
ICALP (1)
Lecture Notes in Computer Science
The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functio
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2bb46bbc738700938bd5630af0c1f361
https://doi.org/10.1007/978-3-662-43948-7_9
https://doi.org/10.1007/978-3-662-43948-7_9
Publikováno v:
MIT web domain
We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2 + ε fraction of input strings, but must do so with high probability on those inputs where one does suc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::51168216701bb46fec3cb880b621a59a