Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA quadratically tight partition bound for classical communication complexity and query complexity
118
0
0.0
(
0
)
Added by
Rahul Jain
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this work we introduce, both for classical communication complexity and query complexity, a modification of the partition bound introduced by Jain and Klauck [2010]. We call it the public-coin partition bound. We show that (the logarithm to the base two of) its communication complexity and query complexi
rate research
Read More
Let $f:{0,1}^n rightarrow {0,1}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) leq R_0(f) leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is also a quadratically tight bound on $R_0(f)$: $EC(f) leq R_0(f) = O(EC(f)^2)$. We prove that $EC(f) leq C(f) leq EC(f)^2$ and show that there is a quadratic separation between the two, thus $EC(f)$ gives a tighter upper bound for $R_0(f)$. The measure is also related to the fractional certificate complexity $FC(f)$ as follows: $FC(f) leq EC(f) = O(FC(f)^{3/2})$. This also connects to an open question by Aaronson whether $FC(f)$ is a quadratically tight bound for $R_0(f)$, as $EC(f)$ is in fact a relaxation of $FC(f)$. In the second part of the work, we upper bound the distributed query complexity $D^mu_epsilon(f)$ for product distributions $mu$ by the square of the query corruption bound ($mathrm{corr}_epsilon(f)$) which improves upon a result of Harsha, Jain and Radhakrishnan [2015]. A similar statement for communication complexity is open.
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions $f$ and $g$ such that $R(fcirc g)ll R(f) R(g)$. In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of $f$). Second, we show that for all $f$ and $g$, $R(fcirc g)=Omega(mathop{noisyR}(f)cdot R(g))$, where $mathop{noisyR}(f)$ is a measure describing the cost of computing $f$ on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure $M(cdot)$ satisfying $R(fcirc g)=Omega(M(f)R(g))$ for all $f$ and $g$, it must hold that $mathop{noisyR}(f)=Omega(M(f))$ for all $f$. We also give a clean characterization of the measure $mathop{noisyR}(f)$: it satisfies $mathop{noisyR}(f)=Theta(R(fcirc gapmaj_n)/R(gapmaj_n))$, where $n$ is the input size of $f$ and $gapmaj_n$ is the $sqrt{n}$-gap majority function on $n$ bits.
We prove upper bounds on deterministic communication complexity in terms of log of the rank and simp
This work addresses two problems in the context of two-party communication complexity of functions. First, it concludes the line of research, which can be viewed as demonstrating qualitative advantage of quantum communication in the three most common communication layouts: two-way interactive communication; one-way communication; simultaneous message passing (SMP). We demonstrate a functional problem, whose communication complexity is $O((log n)^2)$ in the quantum version of SMP and $tildeOmega(sqrt n)$ in the classical (randomised) version of SMP. Second, this work contributes to understanding the power of the weakest commonly studied regime of quantum communication $-$ SMP with quantum messages and without shared randomness (the latter restriction can be viewed as a somewhat artificial way of making the quantum model as weak as possible). Our function has an efficient solution in this regime as well, which means that even lacking shared randomness, quantum SMP can be exponentially stronger than its classical counterpart with shared randomness.
We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Goos, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and the author. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from lifting the query separation to communication complexity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
