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

Leibniz international proceedings in informatics

A Lifting Theorem with Applications to Symmetric Functions

Arkadev Chattopadhyay, Nikhil S. Mande

Published Jan 1, 2018• 4 citations
Publisher

Abstract

We use a technique of “lifting” functions introduced by Krause and Pudlak [Theor. Comput. Sci., 1997], to amplify degree-hardness measures of a function to corresponding monomial-hardness properties of the lifted function. We then show that any symmetric function F projects onto a “lift” of another suitable symmetric function f . These two key results enable us to prove several results on the complexity of symmetric functions in various models, as given below: 1. We provide a characterization of the approximate spectral norm of symmetric functions in terms of the spectrum of the underlying predicate, affirming a conjecture of Ada et al. [APPROX-RANDOM, 2012] which has several consequences. 2. We characterize symmetric functions computable by quasi-polynomial sized Threshold of Parity circuits. 3. We show that the approximate spectral norm of a symmetric function f characterizes the (quantum and classical) bounded error communication complexity of f o XOR. 4. Finally, we characterize the weakly-unbounded error communication complexity of symmetric XOR functions, resolving a weak form of a conjecture by Shi and Zhang [Quantum Information & Computation, 2009]

DOI
10.4230/lipics.fsttcs.2017.23

Related papers

Dual polynomials and communication complexity of $\textsf{XOR}$ functions

Arkadev Chattopadhyay, Nikhil S. Mande

We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f \circ \textsf{XOR}$, called an $\textsf{XOR}$ function. Using this duality, we develop polynomial based techniques for understanding the bounded error ($\textsf{BPP}$) and the weakly-unbounded error ($\textsf{PP}$) communication complexities of $\textsf{XOR}$ functions. We show the following. A weak form of an interesting conjecture of Zhang and Shi (Quantum Information and Computation, 2009) (The full conjecture has just been reported to be independently settled by Hatami and Qian (Arxiv, 2017). However, their techniques are quite different and are not known to yield many of the results we obtain here). Zhang and Shi assert that for symmetric functions $f : \{0, 1\}^n \rightarrow \{-1, 1\}$, the weakly unbounded-error complexity of $f \circ \textsf{XOR}$ is essentially characterized by the number of points $i$ in the set $\{0,1, \dots,n-2\}$ for which $D_f(i) \neq D_f(i+2)$, where $D_f$ is the predicate corresponding to $f$. The number of such points is called the odd-even degree of $f$. We show that the $\textsf{PP}$ complexity of $f \circ \textsf{XOR}$ is $Ω(k/ \log(n/k))$. We resolve a conjecture of a different Zhang characterizing the Threshold of Parity circuit size of symmetric functions in terms of their odd-even degree. We obtain a new proof of the exponential separation between $\textsf{PP}^{cc}$ and $\textsf{UPP}^{cc}$ via an $\textsf{XOR}$ function. We provide a characterization of the approximate spectral norm of symmetric functions, affirming a conjecture of Ada et al. (APPROX-RANDOM, 2012) which has several consequences. Additionally, we prove strong $\textsf{UPP}$ lower bounds for $f \circ \textsf{XOR}$, when $f$ is symmetric and periodic with period $O(n^{1/2-ε})$, for any constant $ε> 0$.

arXiv:1704.02537•Apr 8, 2017•2 citations

On the Spectral Properties of Symmetric Functions

Anil Ada, Omar Fawzi, Raghav Kulkarni

We characterize the approximate monomial complexity, sign monomial complexity , and the approximate L 1 norm of symmetric functions in terms of simple combinatorial measures of the functions. Our characterization of the approximate L 1 norm solves the main conjecture in [AFH12]. As an application of the characterization of the sign monomial complexity, we prove a conjecture in [ZS09] and provide a characterization for the unbounded-error communication complexity of symmetric-xor functions.

arXiv:1704.03176•Apr 11, 2017•4 citations

The Unbounded-Error Communication Complexity of symmetric XOR functions

Hamed Hatami, Yingjie Qian

Settling a conjecture of Shi and Zhang, we determine the unbounded-error communication complexity of the symmetric XOR functions up to a poly-logarithmic factor. Our proof is by a simple reduction to an earlier result of Sherstov.

arXiv:1704.00777•Apr 3, 2017•6 citations

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

The Unbounded-Error Communication Complexity of Symmetric Functions

Alexander A. Sherstov

We prove an essentially tight lower bound on the unbounded-error communication complexity of every symmetric function, i.e., f(x,y)=D(|x∧y|), where D: {0,1,…,n}→{0,1} is a given predicate and x,y range over {0,1} n . Specifically, we show that the communication complexity of f is between Θ(k/log5 n) and Θ(k logn), where k is the number of value changes of D in {0,1,…, n}. Prior to this work, the problem was solved only for the parity predicate D (Forster 2001). Our proof is built around two new ideas. First, we show that a predicate D gives rise to a rapidly mixing random walk on ℤ 2 , which allows us to reduce the problem to communication lower bounds for “typical” predicates. Second, we use Paturi’s approximation lower bounds (1992), suitably generalized here to clusters of real nodes in [0,n] and interpreted in their dual form, to prove that a typical predicate behaves analogous to the parity predicate with respect to a smooth distribution on the inputs.

COMBINATORICA•Oct 1, 2008•38 citations

Quantum-Classical Equivalence for AND-Functions

Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay +2 more

A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form $$ F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), $$ when the outer function $f$ is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function $f$, the bounded-error quantum and classical deterministic communication complexities of the function $f \circ \mathrm{AND}_2$ are polynomially related, up to polylogarithmic factors in $n$. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of $f$. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.

cs.CCCross-listedarXiv:2606.03249•Leibniz international proceedings in informatics•Jun 3, 2026•0 citations
We use a technique of “lifting” functions introduced by Krause and Pudlak [Theor. Comput. Sci., 1997], to amplify degree-hardness measures of a function to corresponding monomial-hardness properties of the lifted function. We then show that any symmetric function F projects onto a “lift” of another suitable symmetric function f . These two key results enable us to prove several results on the complexity of symmetric functions in various models, as given below: 1. We provide a characterization of the approximate spectral norm of symmetric functions in terms of the spectrum of the underlying predicate, affirming a conjecture of Ada et al. [APPROX-RANDOM, 2012] which has several consequences. 2. We characterize symmetric functions computable by quasi-polynomial sized Threshold of Parity circuits. 3. We show that the approximate spectral norm of a symmetric function f characterizes the (quantum and classical) bounded error communication complexity of f o XOR. 4. Finally, we characterize the weakly-unbounded error communication complexity of symmetric XOR functions, resolving a weak form of a conjecture by Shi and Zhang [Quantum Information & Computation, 2009]
Dual polynomials and communication complexity of XOR\textsf{XOR}XOR functions
We show a new duality between the polynomial margin complexity of fff and the discrepancy of the function f∘XORf \circ \textsf{XOR}f∘XOR, called an XOR\textsf{XOR}XOR function. Using this duality, we develop polynomial based techniques for understanding the bounded error (BPP\textsf{BPP}BPP) and the weakly-unbounded error (PP\textsf{PP}PP) communication complexities of XOR\textsf{XOR}XOR functions. We show the following. A weak form of an interesting conjecture of Zhang and Shi (Quantum Information and Computation, 2009) (The full conjecture has just been reported to be independently settled by Hatami and Qian (Arxiv, 2017). However, their techniques are quite different and are not known to yield many of the results we obtain here). Zhang and Shi assert that for symmetric functions f:{0,1}n→{−1,1}f : \{0, 1\}^n \rightarrow \{-1, 1\}f:{0,1}n→{−1,1}, the weakly unbounded-error complexity of f∘XORf \circ \textsf{XOR}f∘XOR is essentially characterized by the number of points iii in the set {0,1,…,n−2}\{0,1, \dots,n-2\}{0,1,…,n−2} for which Df(i)≠Df(i+2)D_f(i) \neq D_f(i+2)Df​(i)=Df​(i+2), where DfD_fDf​ is the predicate corresponding to fff. The number of such points is called the odd-even degree of fff. We show that the PP\textsf{PP}PP complexity of f∘XORf \circ \textsf{XOR}f∘XOR is Ω(k/log⁡(n/k))Ω(k/ \log(n/k))Ω(k/log(n/k)). We resolve a conjecture of a different Zhang characterizing the Threshold of Parity circuit size of symmetric functions in terms of their odd-even degree. We obtain a new proof of the exponential separation between PPcc\textsf{PP}^{cc}PPcc and UPPcc\textsf{UPP}^{cc}UPPcc via an XOR\textsf{XOR}XOR function. We provide a characterization of the approximate spectral norm of symmetric functions, affirming a conjecture of Ada et al. (APPROX-RANDOM, 2012) which has several consequences. Additionally, we prove strong UPP\textsf{UPP}UPP lower bounds for f∘XORf \circ \textsf{XOR}f∘XOR, when fff is symmetric and periodic with period O(n1/2−ε)O(n^{1/2-ε})O(n1/2−ε), for any constant ε>0ε> 0ε>0.
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.
We prove an essentially tight lower bound on the unbounded-error communication complexity of every symmetric function, i.e., f(x,y)=D(|x∧y|), where D: {0,1,…,n}→{0,1} is a given predicate and x,y range over {0,1} n . Specifically, we show that the communication complexity of f is between Θ(k/log5 n) and Θ(k logn), where k is the number of value changes of D in {0,1,…, n}. Prior to this work, the problem was solved only for the parity predicate D (Forster 2001). Our proof is built around two new ideas. First, we show that a predicate D gives rise to a rapidly mixing random walk on ℤ 2 , which allows us to reduce the problem to communication lower bounds for “typical” predicates. Second, we use Paturi’s approximation lower bounds (1992), suitably generalized here to clusters of real nodes in [0,n] and interpreted in their dual form, to prove that a typical predicate behaves analogous to the parity predicate with respect to a smooth distribution on the inputs.
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form F(x,y)=f(x1∧y1,…,xn∧yn), F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), F(x,y)=f(x1​∧y1​,…,xn​∧yn​), when the outer function fff is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function fff, the bounded-error quantum and classical deterministic communication complexities of the function f∘AND2f \circ \mathrm{AND}_2f∘AND2​ are polynomially related, up to polylogarithmic factors in nnn. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of fff. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.