Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Composition Theorem via Conflict Complexity
72
0
0.0
(
0
)
Added by
Swagato Sanyal
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Swagato Sanyal
Ask ChatGPT about the research
No Arabic abstract
Let $R(cdot)$ stand for the bounded-error randomized query complexity. We show that for any relation $f subseteq {0,1}^n times mathcal{S}$ and partial Boolean function $g subseteq {0,1}^n times {0,1}$, $R_{1/3}(f circ g^n) = Omega(R_{4/9}(f) cdot sqrt{R_{1/3}(g)})$. Independently of us, Gavinsky, Lee and Santha cite{newcomp} proved this result. By an example demonstrated in their work, this bound is optimal. We prove our result by introducing a novel complexity measure called the emph{conflict complexity} of a partial Boolean function $g$, denoted by $chi(g)$, which may be of independent interest. We show that $chi(g) = Omega(sqrt{R(g)})$ and $R(f circ g^n) = Omega(R(f) cdot chi(g))$.
rate research
Read More
Let $R_epsilon(cdot)$ stand for the bounded-error randomized query complexity with error $epsilon > 0$. For any relation $f subseteq {0,1}^n times S$ and partial Boolean function $g subseteq {0,1}^m times {0,1}$, we show that $R_{1/3}(f circ g^n) in Omega(R_{4/9}(f) cdot sqrt{R_{1/3}(g)})$, where $f circ g^n subseteq ({0,1}^m)^n times S$ is the composition of $f$ and $g$. We give an example of a relation $f$ and partial Boolean function $g$ for which this lower bound is tight. We prove our composition theorem by introducing a new complexity measure, the max conflict complexity $bar chi(g)$ of a partial Boolean function $g$. We show $bar chi(g) in Omega(sqrt{R_{1/3}(g)})$ for any (partial) function $g$ and $R_{1/3}(f circ g^n) in Omega(R_{4/9}(f) cdot bar chi(g))$; these two bounds imply our composition result. We further show that $bar chi(g)$ is always at least as large as the sabotage complexity of $g$, introduced by Ben-David and Kothari.
Let the randomized query complexity of a relation for error probability $epsilon$ be denoted by $R_epsilon(cdot)$. We prove that for any relation $f subseteq {0,1}^n times mathcal{R}$ and Boolean function $g:{0,1}^m rightarrow {0,1}$, $R_{1/3}(fcirc g^n) = Omega(R_{4/9}(f)cdot R_{1/2-1/n^4}(g))$, where $f circ g^n$ is the relation obtained by composing $f$ and $g$. We also show that $R_{1/3}left(f circ left(g^oplus_{O(log n)}right)^nright)=Omega(log n cdot R_{4/9}(f) cdot R_{1/3}(g))$, where $g^oplus_{O(log n)}$ is the function obtained by composing the xor function on $O(log n)$ bits and $g^t$.
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.
Let $fsubseteq{0,1}^ntimesXi$ be a relation and $g:{0,1}^mto{0,1,*}$ be a promise function. This work investigates the randomised query complexity of the relation $fcirc g^nsubseteq{0,1}^{mcdot n}timesXi$, which can be viewed as one of the most general cases of composition in the query model (letting $g$ be a relation seems to result in a rather unnatural definition of $fcirc g^n$). We show that for every such $f$ and $g$, $$mathcal R(fcirc g^n) in Omega(mathcal R(f)cdotsqrt{mathcal R(g)}),$$ where $mathcal R$ denotes the randomised query complexity. On the other hand, we demonstrate a relation $f_0$ and a promise function $g_0$, such that $mathcal R(f_0)inTheta(sqrt n)$, $mathcal R(g_0)inTheta(n)$ and $mathcal R(f_0circ g_0^n)inTheta(n)$ $-$ that is, our composition statement is tight. To the best of our knowledge, there was no known composition theorem for the randomised query complexity of relations or promise functions (and for the special case of total functions our lower bound gives multiplicative improvement of $sqrt{log n}$).
For integers $n$ and $k$, the density Hales-Jewett number $c_{n,k}$ is defined as the maximal size of a subset of $[k]^n$ that contains no combinatorial line. We show that for $k ge 3$ the density Hales-Jewett number $c_{n,k}$ is equal to the maximal size of a cylinder intersection in the problem $Part_{n,k}$ of testing whether $k$ subsets of $[n]$ form a partition. It follows that the communication complexity, in the Number On the Forehead (NOF) model, of $Part_{n,k}$, is equal to the minimal size of a partition of $[k]^n$ into subsets that do not contain a combinatorial line. Thus, the bound in cite{chattopadhyay2007languages} on $Part_{n,k}$ using the Hales-Jewett theorem is in fact tight, and the density Hales-Jewett number can be thought of as a quantity in communication complexity. This gives a new angle to this well studied quantity. As a simple application we prove a lower bound on $c_{n,k}$, similar to the lower bound in cite{polymath2010moser} which is roughly $c_{n,k}/k^n ge exp(-O(log n)^{1/lceil log_2 krceil})$. This lower bound follows from a protocol for $Part_{n,k}$. It is interesting to better understand the communication complexity of $Part_{n,k}$ as this will also lead to the better understanding of the Hales-Jewett number. The main purpose of this note is to motivate this study.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
