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:2404.07606

Lifting with Inner Functions of Polynomial Discrepancy

Yahel Manor, Or Meir

Published Apr 11, 2024• 0 citations
arXivHTMLPDF

Abstract

Lifting theorems are theorems that bound the communication complexity of a composed function $f\circ g^{n}$ in terms of the query complexity of $f$ and the communication complexity of $g$. Such theorems constitute a powerful generalization of direct-sum theorems for $g$, and have seen numerous applications in recent years. We prove a new lifting theorem that works for every two functions $f,g$ such that the discrepancy of $g$ is at most inverse polynomial in the input length of $f$. Our result is a significant generalization of the known direct-sum theorem for discrepancy, and extends the range of inner functions $g$ for which lifting theorems hold.

DOI
10.48550/arxiv.2404.07606

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•32 citations

A Direct Product Theorem for Discrepancy

Troy Lee, Adi Shraibman, Robert Špalek

Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in randomized, quantum, and even weakly-unbounded error models of communication. We show an optimal product theorem for discrepancy, namely that for any two Boolean functions f, g, disc(f odot g)=thetas(disc(f) disc(g)). As a consequence we obtain a strong direct product theorem for distributional complexity, and direct sum theorems for worst-case complexity, for bounds shown by the discrepancy method. Our results resolve an open problem of Shaltiel (2003) who showed a weaker product theorem for discrepancy with respect to the uniform distribution, discUodot(fodotk)=O(discU(f))k/3. The main tool for our results is semidefinite programming, in particular a recent characterization of discrepancy in terms of a semidefinite programming quantity by Linial and Shraibman (2006).

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2008•84 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.

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

Query-To-Communication Lifting for BPP Using Inner Product

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth +2 more

We prove a new query-to-communication lifting for randomized protocols, with inner product as gadget. This allows us to use a much smaller gadget, leading to a more efficient lifting. Prior to this work, such a theorem was known only for deterministic protocols, due to Chattopadhyay et al. [Arkadev Chattopadhyay et al., 2017] and Wu et al. [Xiaodi Wu et al., 2017]. The only query-to-communication lifting result for randomized protocols, due to Göös, Pitassi and Watson [Mika Göös et al., 2017], used the much larger indexing gadget. Our proof also provides a unified treatment of randomized and deterministic lifting. Most existing proofs of deterministic lifting theorems use a measure of information known as thickness. In contrast, Göös, Pitassi and Watson [Mika Göös et al., 2017] used blockwise min-entropy as a measure of information. Our proof uses the blockwise min-entropy framework to prove lifting theorems in both settings in a unified way.

Leibniz international proceedings in informatics•Jan 1, 2019•15 citations

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
Lifting theorems are theorems that bound the communication complexity of a composed function f∘gnf\circ g^{n}f∘gn in terms of the query complexity of fff and the communication complexity of ggg. Such theorems constitute a powerful generalization of direct-sum theorems for ggg, and have seen numerous applications in recent years. We prove a new lifting theorem that works for every two functions f,gf,gf,g such that the discrepancy of ggg is at most inverse polynomial in the input length of fff. Our result is a significant generalization of the known direct-sum theorem for discrepancy, and extends the range of inner functions ggg for which lifting theorems hold.
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.
Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in randomized, quantum, and even weakly-unbounded error models of communication. We show an optimal product theorem for discrepancy, namely that for any two Boolean functions f, g, disc(f odot g)=thetas(disc(f) disc(g)). As a consequence we obtain a strong direct product theorem for distributional complexity, and direct sum theorems for worst-case complexity, for bounds shown by the discrepancy method. Our results resolve an open problem of Shaltiel (2003) who showed a weaker product theorem for discrepancy with respect to the uniform distribution, discUodot(fodotk)=O(discU(f))k/3. The main tool for our results is semidefinite programming, in particular a recent characterization of discrepancy in terms of a semidefinite programming quantity by Linial and Shraibman (2006).
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 new query-to-communication lifting for randomized protocols, with inner product as gadget. This allows us to use a much smaller gadget, leading to a more efficient lifting. Prior to this work, such a theorem was known only for deterministic protocols, due to Chattopadhyay et al. [Arkadev Chattopadhyay et al., 2017] and Wu et al. [Xiaodi Wu et al., 2017]. The only query-to-communication lifting result for randomized protocols, due to Göös, Pitassi and Watson [Mika Göös et al., 2017], used the much larger indexing gadget. Our proof also provides a unified treatment of randomized and deterministic lifting. Most existing proofs of deterministic lifting theorems use a measure of information known as thickness. In contrast, Göös, Pitassi and Watson [Mika Göös et al., 2017] used blockwise min-entropy as a measure of information. Our proof uses the blockwise min-entropy framework to prove lifting theorems in both settings in a unified way.
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.