Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2503.24351

Lifting for Arbitrary Gadgets

Iyer, Siddharth

Published Mar 31, 2025• 0 citations
arXivHTMLPDF

Abstract

We prove a sensitivity-to-communication lifting theorem for arbitrary gadgets. Given functions $f: \{0,1\}^n\to \{0,1\}$ and $g : \mathcal X\times \mathcal Y\to \{0,1\}$, denote $f\circ g(x,y) := f(g(x_1,y_1),\ldots,g(x_n,y_n))$. We show that for any $f$ with sensitivity $s$ and any $g$, \[D(f\circ g) \geq s\cdot \bigg(\frac{Ω(D(g))}{\log\mathsf{rk}(g)} - \log\mathsf{rk}(g)\bigg),\] where $D(\cdot)$ denotes the deterministic communication complexity and $\mathsf{rk}(g)$ is the rank of the matrix associated with $g$. As a corollary, we get that if $D(g)$ is a sufficiently large constant, $D(f\circ g) = Ω(\min\{s,d\}\cdot \sqrt{D(g)})$, where $s$ and $d$ denote the sensitivity and degree of $f$. In particular, computing the OR of $n$ copies of $g$ requires $Ω(n\cdot\sqrt{D(g)})$ bits.

DOI
10.48550/arxiv.2503.24351

Related papers

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

Xudong Wu, Guangxu Yang, Penghui Yao

We investigates a model of hybrid classical-quantum communication complexity, in which two parties first exchange classical messages and subsequently communicate using quantum messages. We study the trade-off between the classical and quantum communication for composed functions of the form $f\circ G^n$, where $f:\{0,1\}^n\to\{\pm1\}$ and $G$ is an inner product function of $Θ(\log n)$ bits. To prove the trade-off, we establish a novel lifting theorem for hybrid communication complexity. This theorem unifies two previously separate lifting paradigms: the query-to-communication lifting framework for classical communication complexity and the approximate-degree-to-generalized-discrepancy lifting methods for quantum communication complexity. Our hybrid lifting theorem therefore offers a new framework for proving lower bounds in hybrid classical-quantum communication models. As a corollary, we show that any hybrid protocol communicating $c$ classical bits followed by $q$ qubits to compute $f\circ G^n$ must satisfy $c+q^2=Ω\big(\max\{\mathrm{deg}(f),\mathrm{bs}(f)\}\cdot\log n\big)$, where $\mathrm{deg}(f)$ is the degree of $f$ and $\mathrm{bs}(f)$ is the block sensitivity of $f$. For read-once formula $f$, this yields an almost tight trade-off: either they have to exchange $Θ\big(n\cdot\log n\big)$ classical bits or $\widetildeΘ\big(\sqrt n\cdot\log n\big)$ qubits, showing that classical pre-processing cannot significantly reduce the quantum communication required. To the best of our knowledge, this is the first non-trivial trade-off between classical and quantum communication in hybrid two-way communication complexity.

cs.CCCross-listedarXiv:2511.17227•Leibniz international proceedings in informatics•Nov 24, 2025•0 citations

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth +2 more

Lifting theorems are theorems that relate the query complexity of a function $f:\{0,1\}^{n}\to \{0,1\}$ to the communication complexity of the composed function $f\circ g^{n}$ for some “gadget” $g:\{ 0,1\}^{b}\times \{0,1\}^{b}\to \{0,1\}$. Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in recent years. In addition, such theorems can be viewed as a strong generalization of a direct-sum theorem for the gadget $g$. We prove a new lifting theorem that works for all gadgets $g$ that have logarithmic length and exponentially-small discrepancy, for both deterministic and randomized communication complexity. Thus, we significantly increase the range of gadgets for which such lifting theorems hold. Our result has two main motivations: first, allowing a larger variety of gadgets may support more applications. In particular, our work is the first to prove a randomized lifting theorem for logarithmic-size gadgets, thus improving some applications of the theorem. Second, our result can be seen as a strong generalization of a direct-sum theorem for functions with low discrepancy.

arXiv:1904.13056•SIAM Journal on Computing•Jan 1, 2021•12 citations

On Query-To-Communication Lifting for Adversary Bounds

Anshu, Anurag, Shalev Ben-David, Srijita Kundu

We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1) We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2) Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3) Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.

arXiv:2012.03415•Leibniz international proceedings in informatics•Dec 7, 2020•0 citations

On Query-To-Communication Lifting for Adversary Bounds

Anurag Anshu, Shalev Ben-David, Srijita Kundu

We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1) We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2) Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3) Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.

•Dec 7, 2020•1 citation

Randomized Lifting for One-Way Number-on-Forehead Communication

Chenyu Wang

We prove a lifting theorem from two-party public-coin one-way communication to multiparty public-coin one-way number-on-forehead (NOF) communication. For every fixed $k\ge2$ and prime $q>2k$, there is a generalized inner product gadget $\GIP_{q,r}^k:(\F_q^r)^k\to\F_q$ with $r=O_k(q/\log q)$ such that, for every partial Boolean function $f:D\to\bits$, where $D\subseteq\F_q\times\F_q$, \[ R_{1/3}^1(f)-O(1) \le R_{1/6}^{1,\NOF}\bigl(f\circ\GIP_{q,r}^k\bigr) \le R_{1/6}^1(f). \] Thus, composition with the gadget preserves one-way randomized communication complexity up to an additive constant and a change in the error parameter. The lower bound holds in the general one-way NOF model, where the last player sees the entire gadget input. This extends the deterministic one-way NOF lifting theorem of Yang and Zhang to randomized protocols, and extends the randomized lifting result of Wang and Wu from the conservative model to the general one-way NOF model. Our proof introduces a one-way cylinder partition bound that lower bounds public-coin one-way NOF communication complexity. We show that, for the lifted function, this bound is at least half the one-way partition bound of the outer function. The main technical step transfers a dual solution between the two bounds, using Möbius inversion and a discrepancy estimate for generalized inner product to control the loss. Combining this transfer with the characterization of two-party one-way randomized communication complexity by the one-way partition bound yields the lifting theorem.

arXiv:2609.32542•Sep 26, 2026•0 citations

Raz-McKenzie simulation: new gadget and unimprovability of Thickness Lemma.

Alexander Kozachinskiy

Assume that we have an outer function $f:\{0, 1\}^n \to \{0, 1\}$ and a gadget function $g:A\times B \to\{0, 1\}$ and we want to lower bound deterministic communication complexity of a composed function $f\circ g^n$, denoted here by $D^{cc}(f\circ g^n)$, in terms of deterministic query complexity of $f$, denoted here by $D^{dt}(f)$. The study of such questions, now usually called \emph{Simulation Theorems}, was initiated in the work of Raz and McKenzie (\cite{raz1997separation}). Recently, Chattopadhyaay et al. (\cite{chattopadhyay2017simulation}) introduced a very convenient tool to study such questions, they called this tool \emph{hitting distributions}. Using this tool, they proved that $D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)$, where $g$ is either Inner Product or Gap Hamming Distance gadget on $k$ bits, and $f$ is any function depending on at most $2^{ck}$ variables for some absolute constant $c$. In this work we use hitting distributions to show Simulation Theorem for a new gadget. Our gadget is the following one: Alice holds $a\in \mathbb{F}_{p^2}$, Bob holds $b\in \mathbb{F}_{p^2}$ and they want to know whether $a - b$ is a square in $\mathbb{F}_{p^2}$. We show that $D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)$, where $g$ is our gadget and $f$ is any function depending on at most $p^c$ variables for some constant $c$ (note that this bound is exponential in the size of gadget, which is $O(\log p)$). We also investigate hitting distributions for disjointness predicate on $k$-element subsets of $\{1, 2, \ldots, n\}$. Finally, we study Thickness Lemma, a combinatorial statement from the proof of Simulation Theorems of G\{o}\{o}s et al and Chattopadhyaay et al., and show that this Lemma can not be improved.

•Feb 12, 2018•1 citation
We prove a sensitivity-to-communication lifting theorem for arbitrary gadgets. Given functions f:{0,1}n→{0,1}f: \{0,1\}^n\to \{0,1\}f:{0,1}n→{0,1} and g:X×Y→{0,1}g : \mathcal X\times \mathcal Y\to \{0,1\}g:X×Y→{0,1}, denote f∘g(x,y):=f(g(x1,y1),…,g(xn,yn))f\circ g(x,y) := f(g(x_1,y_1),\ldots,g(x_n,y_n))f∘g(x,y):=f(g(x1​,y1​),…,g(xn​,yn​)). We show that for any fff with sensitivity sss and any ggg, [D(f\circ g) \geq s\cdot \bigg(\frac{Ω(D(g))}{\log\mathsf{rk}(g)} - \log\mathsf{rk}(g)\bigg),] where D(⋅)D(\cdot)D(⋅) denotes the deterministic communication complexity and rk(g)\mathsf{rk}(g)rk(g) is the rank of the matrix associated with ggg. As a corollary, we get that if D(g)D(g)D(g) is a sufficiently large constant, D(f∘g)=Ω(min⁡{s,d}⋅D(g))D(f\circ g) = Ω(\min\{s,d\}\cdot \sqrt{D(g)})D(f∘g)=Ω(min{s,d}⋅D(g)​), where sss and ddd denote the sensitivity and degree of fff. In particular, computing the OR of nnn copies of ggg requires Ω(n⋅D(g))Ω(n\cdot\sqrt{D(g)})Ω(n⋅D(g)​) bits.
We investigates a model of hybrid classical-quantum communication complexity, in which two parties first exchange classical messages and subsequently communicate using quantum messages. We study the trade-off between the classical and quantum communication for composed functions of the form f∘Gnf\circ G^nf∘Gn, where f:{0,1}n→{±1}f:\{0,1\}^n\to\{\pm1\}f:{0,1}n→{±1} and GGG is an inner product function of Θ(log⁡n)Θ(\log n)Θ(logn) bits. To prove the trade-off, we establish a novel lifting theorem for hybrid communication complexity. This theorem unifies two previously separate lifting paradigms: the query-to-communication lifting framework for classical communication complexity and the approximate-degree-to-generalized-discrepancy lifting methods for quantum communication complexity. Our hybrid lifting theorem therefore offers a new framework for proving lower bounds in hybrid classical-quantum communication models. As a corollary, we show that any hybrid protocol communicating ccc classical bits followed by qqq qubits to compute f∘Gnf\circ G^nf∘Gn must satisfy c+q2=Ω(max⁡{deg(f),bs(f)}⋅log⁡n)c+q^2=Ω\big(\max\{\mathrm{deg}(f),\mathrm{bs}(f)\}\cdot\log n\big)c+q2=Ω(max{deg(f),bs(f)}⋅logn), where deg(f)\mathrm{deg}(f)deg(f) is the degree of fff and bs(f)\mathrm{bs}(f)bs(f) is the block sensitivity of fff. For read-once formula fff, this yields an almost tight trade-off: either they have to exchange Θ(n⋅log⁡n)Θ\big(n\cdot\log n\big)Θ(n⋅logn) classical bits or Θ~(n⋅log⁡n)\widetildeΘ\big(\sqrt n\cdot\log n\big)Θ(n​⋅logn) qubits, showing that classical pre-processing cannot significantly reduce the quantum communication required. To the best of our knowledge, this is the first non-trivial trade-off between classical and quantum communication in hybrid two-way communication complexity.
Lifting theorems are theorems that relate the query complexity of a function f:{0,1}n→{0,1}f:\{0,1\}^{n}\to \{0,1\}f:{0,1}n→{0,1} to the communication complexity of the composed function f∘gnf\circ g^{n}f∘gn for some “gadget” g:{0,1}b×{0,1}b→{0,1}g:\{ 0,1\}^{b}\times \{0,1\}^{b}\to \{0,1\}g:{0,1}b×{0,1}b→{0,1}. Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in recent years. In addition, such theorems can be viewed as a strong generalization of a direct-sum theorem for the gadget ggg. We prove a new lifting theorem that works for all gadgets ggg that have logarithmic length and exponentially-small discrepancy, for both deterministic and randomized communication complexity. Thus, we significantly increase the range of gadgets for which such lifting theorems hold. Our result has two main motivations: first, allowing a larger variety of gadgets may support more applications. In particular, our work is the first to prove a randomized lifting theorem for logarithmic-size gadgets, thus improving some applications of the theorem. Second, our result can be seen as a strong generalization of a direct-sum theorem for functions with low discrepancy.
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1) We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2) Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3) Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1) We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2) Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3) Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.
We prove a lifting theorem from two-party public-coin one-way communication to multiparty public-coin one-way number-on-forehead (NOF) communication. For every fixed k≥2k\ge2k≥2 and prime q>2kq>2kq>2k, there is a generalized inner product gadget $\GIP_{q,r}^k:(\F_q^r)^k\to\F_q$ with r=Ok(q/log⁡q)r=O_k(q/\log q)r=Ok​(q/logq) such that, for every partial Boolean function $f:D\to\bits$, where $D\subseteq\F_q\times\F_q$, \[ R_{1/3}^1(f)-O(1) \le R_{1/6}^{1,\NOF}\bigl(f\circ\GIP_{q,r}^k\bigr) \le R_{1/6}^1(f). \] Thus, composition with the gadget preserves one-way randomized communication complexity up to an additive constant and a change in the error parameter. The lower bound holds in the general one-way NOF model, where the last player sees the entire gadget input. This extends the deterministic one-way NOF lifting theorem of Yang and Zhang to randomized protocols, and extends the randomized lifting result of Wang and Wu from the conservative model to the general one-way NOF model. Our proof introduces a one-way cylinder partition bound that lower bounds public-coin one-way NOF communication complexity. We show that, for the lifted function, this bound is at least half the one-way partition bound of the outer function. The main technical step transfers a dual solution between the two bounds, using Möbius inversion and a discrepancy estimate for generalized inner product to control the loss. Combining this transfer with the characterization of two-party one-way randomized communication complexity by the one-way partition bound yields the lifting theorem.
Assume that we have an outer function f:{0,1}n→{0,1}f:\{0, 1\}^n \to \{0, 1\}f:{0,1}n→{0,1} and a gadget function g:A×B→{0,1}g:A\times B \to\{0, 1\}g:A×B→{0,1} and we want to lower bound deterministic communication complexity of a composed function f∘gnf\circ g^nf∘gn, denoted here by Dcc(f∘gn)D^{cc}(f\circ g^n)Dcc(f∘gn), in terms of deterministic query complexity of fff, denoted here by Ddt(f)D^{dt}(f)Ddt(f). The study of such questions, now usually called \emph{Simulation Theorems}, was initiated in the work of Raz and McKenzie (\cite{raz1997separation}). Recently, Chattopadhyaay et al. (\cite{chattopadhyay2017simulation}) introduced a very convenient tool to study such questions, they called this tool \emph{hitting distributions}. Using this tool, they proved that Dcc(f∘gn)=Ω(Ddt(f)⋅Dcc(g))D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)Dcc(f∘gn)=Ω(Ddt(f)⋅Dcc(g)), where ggg is either Inner Product or Gap Hamming Distance gadget on kkk bits, and fff is any function depending on at most 2ck2^{ck}2ck variables for some absolute constant ccc. In this work we use hitting distributions to show Simulation Theorem for a new gadget. Our gadget is the following one: Alice holds a∈Fp2a\in \mathbb{F}_{p^2}a∈Fp2​, Bob holds b∈Fp2b\in \mathbb{F}_{p^2}b∈Fp2​ and they want to know whether a−ba - ba−b is a square in Fp2\mathbb{F}_{p^2}Fp2​. We show that Dcc(f∘gn)=Ω(Ddt(f)⋅Dcc(g))D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)Dcc(f∘gn)=Ω(Ddt(f)⋅Dcc(g)), where ggg is our gadget and fff is any function depending on at most pcp^cpc variables for some constant ccc (note that this bound is exponential in the size of gadget, which is O(log⁡p)O(\log p)O(logp)). We also investigate hitting distributions for disjointness predicate on kkk-element subsets of {1,2,…,n}\{1, 2, \ldots, n\}{1,2,…,n}. Finally, we study Thickness Lemma, a combinatorial statement from the proof of Simulation Theorems of G\{o}\{o}s et al and Chattopadhyaay et al., and show that this Lemma can not be improved.