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

On the Spectral Properties of Symmetric Functions

Anil Ada, Omar Fawzi, Raghav Kulkarni

Published Apr 11, 2017• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1704.03176

Related papers

A Lifting Theorem with Applications to Symmetric Functions

Arkadev Chattopadhyay, Nikhil S. Mande

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]

Leibniz international proceedings in informatics•Jan 1, 2018•2 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•4 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•37 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•Jun 3, 2026•0 citations

Communication complexities of symmetric XOR functions

Z.-Q. Zhang, Y.-Y. Shi

We call $F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}$ a symmetric XOR function if for a function $S:\{0, 1, ..., n\}\to\{0, 1\}$, $F(x, y)=S(|x\oplus y|)$, for any $x, y\in\{0, 1\}^n$, where $|x\oplus y|$ is the Hamming weight of the bit-wise XOR of $x$ and $y$. We show that for any such function, (a) the deterministic communication complexity is always $\Theta(n)$ except for four simple functions that have a constant complexity, and (b) up to a polylog factor, both the error-bounded randomized complexity and quantum communication with entanglement complexity are $\Theta(r_0+r_1)$, where $r_0$ and $r_1$ are the minimum integers such that $r_0, r_1\leq n/2$ and $S(k)=S(k+2)$ for all $k\in[r_0, n-r_1)$.

Quantum Information and Computation•Mar 1, 2009•39 citations

Communication Complexities of XOR functions

Yaoyun Shi, Zhiqiang Zhang

We call $F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}$ a symmetric XOR function if for a function $S:\{0, 1, ..., n\}\to\{0, 1\}$, $F(x, y)=S(|x\oplus y|)$, for any $x, y\in\{0, 1\}^n$, where $|x\oplus y|$ is the Hamming weight of the bit-wise XOR of $x$ and $y$. We show that for any such function, (a) the deterministic communication complexity is always $Θ(n)$ except for four simple functions that have a constant complexity, and (b) up to a polylog factor, the error-bounded randomized and quantum communication complexities are $Θ(r_0+r_1)$, where $r_0$ and $r_1$ are the minimum integers such that $r_0, r_1\leq n/2$ and $S(k)=S(k+2)$ for all $k\in[r_0, n-r_1)$.

arXiv:0808.1762•Aug 13, 2008•11 citations
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.
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]
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.
We call F:{0,1}n×{0,1}n→{0,1}F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}F:{0,1}n×{0,1}n→{0,1} a symmetric XOR function if for a function S:{0,1,...,n}→{0,1}S:\{0, 1, ..., n\}\to\{0, 1\}S:{0,1,...,n}→{0,1}, F(x,y)=S(∣x⊕y∣)F(x, y)=S(|x\oplus y|)F(x,y)=S(∣x⊕y∣), for any x,y∈{0,1}nx, y\in\{0, 1\}^nx,y∈{0,1}n, where ∣x⊕y∣|x\oplus y|∣x⊕y∣ is the Hamming weight of the bit-wise XOR of xxx and yyy. We show that for any such function, (a) the deterministic communication complexity is always Θ(n)\Theta(n)Θ(n) except for four simple functions that have a constant complexity, and (b) up to a polylog factor, both the error-bounded randomized complexity and quantum communication with entanglement complexity are Θ(r0+r1)\Theta(r_0+r_1)Θ(r0​+r1​), where r0r_0r0​ and r1r_1r1​ are the minimum integers such that r0,r1≤n/2r_0, r_1\leq n/2r0​,r1​≤n/2 and S(k)=S(k+2)S(k)=S(k+2)S(k)=S(k+2) for all k∈[r0,n−r1)k\in[r_0, n-r_1)k∈[r0​,n−r1​).
We call F:{0,1}n×{0,1}n→{0,1}F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}F:{0,1}n×{0,1}n→{0,1} a symmetric XOR function if for a function S:{0,1,...,n}→{0,1}S:\{0, 1, ..., n\}\to\{0, 1\}S:{0,1,...,n}→{0,1}, F(x,y)=S(∣x⊕y∣)F(x, y)=S(|x\oplus y|)F(x,y)=S(∣x⊕y∣), for any x,y∈{0,1}nx, y\in\{0, 1\}^nx,y∈{0,1}n, where ∣x⊕y∣|x\oplus y|∣x⊕y∣ is the Hamming weight of the bit-wise XOR of xxx and yyy. We show that for any such function, (a) the deterministic communication complexity is always Θ(n)Θ(n)Θ(n) except for four simple functions that have a constant complexity, and (b) up to a polylog factor, the error-bounded randomized and quantum communication complexities are Θ(r0+r1)Θ(r_0+r_1)Θ(r0​+r1​), where r0r_0r0​ and r1r_1r1​ are the minimum integers such that r0,r1≤n/2r_0, r_1\leq n/2r0​,r1​≤n/2 and S(k)=S(k+2)S(k)=S(k+2)S(k)=S(k+2) for all k∈[r0,n−r1)k\in[r_0, n-r_1)k∈[r0​,n−r1​).