arXiv:1801.03285

A Composition Theorem via Conflict Complexity

Swagato Sanyal

Published Jan 10, 2018• 4 citations

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) = Ω(\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 $χ(g)$, which may be of independent interest. We show that $χ(g) = Ω(\sqrt{\R(g)})$ and $\R(f \circ g^n) = Ω(\R(f) \cdot χ(g))$.

DOI: 10.48550/arxiv.1801.03285

Related papers

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Miklós Sántha, Dmitry Gavinsky, Troy Lee +1 more

Jan 1, 20190 citations

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Dmitry Gavinsky, Troy Lee, Miklós Sántha +1 more

arXiv:1811.10752Leibniz international proceedings in informaticsNov 27, 20184 citations

A Composition Theorem for Randomized Query Complexity

Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5 more

arXiv:1706.00335Jun 1, 20172 citations

A Composition Theorem for Randomized Query Complexity

Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5 more

Leibniz international proceedings in informaticsJan 1, 20182 citations

Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

cs.CCCross-listedarXiv:2601.08073Jan 14, 20260 citations

A General Composition Theorem for Approximate Degree

Samruddhi Pednekar, Supartha Podder

cs.CCCross-listedarXiv:2609.30139Sep 25, 20260 citations

arXiv:1801.03285

A Composition Theorem via Conflict Complexity

Swagato Sanyal

Published Jan 10, 2018• 4 citations

arXiv HTML PDF

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) = Ω(\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

χ(g)

, which may be of independent interest. We show that

χ(g) = Ω(\sqrt{\R(g)})

and

\R(f \circ g^n) = Ω(\R(f) \cdot χ(g))

DOI: 10.48550/arxiv.1801.03285

Related papers

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Miklós Sántha, Dmitry Gavinsky, Troy Lee +1 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 $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.

Jan 1, 20190 citations

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Dmitry Gavinsky, Troy Lee, Miklós Sántha +1 more

For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.

arXiv:1811.10752Leibniz international proceedings in informaticsNov 27, 20184 citations

A Composition Theorem for Randomized Query Complexity

Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5 more

Let the randomized query complexity of a relation for error probability $ε$ be denoted by $R_ε(\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}(f\circ g^n) = Ω(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)^n\right)=Ω(\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$ .Let the randomized query complexity of a relation for error probability $ε$ be denoted by $R_ε(\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}(f\circ g^n) = Ω(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)^n\right)=Ω(\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$.

arXiv:1706.00335Jun 1, 20172 citations

A Composition Theorem for Randomized Query Complexity

Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5 more

Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.

Leibniz international proceedings in informaticsJan 1, 20182 citations

Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

For a (possibly partial) Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ as well as a query complexity measure $M$ which maps Boolean functions to real numbers, define the composition limit of $M$ on $f$ by $M^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}$ . We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show $R_0^*(f)=\max\{R^*(f),C^*(f)\}$ . Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.For a (possibly partial) Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ as well as a query complexity measure $M$ which maps Boolean functions to real numbers, define the composition limit of $M$ on $f$ by $M^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}$. We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show $R_0^*(f)=\max\{R^*(f),C^*(f)\}$. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.

cs.CCCross-listedarXiv:2601.08073Jan 14, 20260 citations

A General Composition Theorem for Approximate Degree

Samruddhi Pednekar, Supartha Podder

A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$ , $\widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right),$ where $\widetilde{deg}$ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.

cs.CCCross-listedarXiv:2609.30139Sep 25, 20260 citations

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) = Ω(\R_{4/9}(f) \cdot \sqrt{\R_{1/3}(g)})

g

, denoted by

χ(g)

, which may be of independent interest. We show that

χ(g) = Ω(\sqrt{\R(g)})

and

\R(f \circ g^n) = Ω(\R(f) \cdot χ(g))

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

ε

be denoted by

R_ε(\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}(f\circ g^n) = Ω(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)^n\right)=Ω(\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

For a (possibly partial) Boolean function

f\colon\{0,1\}^n\to\{0,1\}

as well as a query complexity measure

M

which maps Boolean functions to real numbers, define the composition limit of

M

f

M^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}

. We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show

R_0^*(f)=\max\{R^*(f),C^*(f)\}

. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.

f:\{0,1\}^n\to\{0,1\}

and

g:\{0,1\}^m\to\{0,1\}

\widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right),

where

\widetilde{deg}

denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.