All reports by Author Mohammad Bavarian:

__
TR16-194
| 4th December 2016
__

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan#### The Optimality of Correlated Sampling

Revisions: 1

__
TR16-146
| 18th September 2016
__

Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini#### Computability Theory of Closed Timelike Curves

__
TR16-047
| 23rd March 2016
__

Mohammad Bavarian, Thomas Vidick, Henry Yuen#### Parallel repetition via fortification: analytic view and the quantum case

__
TR15-137
| 22nd August 2015
__

Mohammad Bavarian, Dmytro Gavinsky, Tsuyoshi Ito#### On the Role of Shared Randomness in Simultaneous Communication

__
TR14-152
| 13th November 2014
__

Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo#### Tighter Relations Between Sensitivity and Other Complexity Measures

__
TR13-164
| 28th November 2013
__

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian#### Weak Parity

__
TR13-039
| 18th March 2013
__

Arturs Backurs, Mohammad Bavarian#### On the sum of $L1$ influences

Revisions: 2

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan

In the "correlated sampling" problem, two players, say Alice and Bob, are given two distributions, say $P$ and $Q$ respectively, over the same universe and access to shared randomness. The two players are required to output two elements, without any interaction, sampled according to their respective distributions, while trying to ... more >>>

Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini

We ask, and answer, the question of what's computable by Turing machines equipped with time travel into the past: that is, closed timelike curves or CTCs (with no bound on their size). We focus on a model for CTCs due to Deutsch, which imposes a probabilistic consistency condition to avoid ... more >>>

Mohammad Bavarian, Thomas Vidick, Henry Yuen

In a recent work, Moshkovitz [FOCS '14] presented a transformation on two-player games called "fortification'', and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial ... more >>>

Mohammad Bavarian, Dmytro Gavinsky, Tsuyoshi Ito

Two parties wish to carry out certain distributed computational tasks, and they are given access to a source of correlated random bits.

It allows the parties to act in a correlated manner, which can be quite useful.

But what happens if the shared randomness is not perfect?

In this work, ... more >>>

Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo

Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other major complexity measures. Despite much attention to the problem and major advances ... more >>>

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

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+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that ... more >>>

Arturs Backurs, Mohammad Bavarian

For a multilinear polynomial $p(x_1,...x_n)$, over the reals, the $L1$-influence is defined to be $\sum_{i=1}^n E_x\left[\frac{|p(x)-p(x^i)|}{2} \right]$, where $x^i$ is $x$ with $i$-th bit swapped. If $p$ maps $\{-1,1\}^n$ to $[-1,1]$, we prove that the $L1$-influence of $p$ is upper bounded by a function of its degree (and independent of ... more >>>