Name
Abstract | ||
|---|---|---|
Let $R_epsilon(cdot)$ stand for the bounded-error randomized query complexity with error $epsilon u003e 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$. 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$. 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. further show that $bar chi(g)$ is always at least as large as the sabotage complexity of $g$, introduced by Ben-David and Kothari. |
Year | Venue | Field |
|---|---|---|
2018 | arXiv: Computational Complexity | Boolean function,Discrete mathematics,Combinatorics,Upper and lower bounds,Omega,Information complexity,Mathematics |
DocType | Volume | Citations |
Journal | abs/1811.10752 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dmitry Gavinsky | 1 | 166 | 20.21 |
| Troy Lee | 2 | 276 | 28.96 |
| Miklos Santha | 3 | 728 | 92.42 |
| Swagato Sanyal | 4 | 1 | 3.39 |