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 show a new duality between the polynomial margin complexity of
f and the discrepancy of the function
f∘XOR, called an
XOR function. Using this duality, we develop polynomial based techniques for understanding the bounded error (
BPP) and the weakly-unbounded error (
PP) communication complexities of
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}, the weakly unbounded-error complexity of
f∘XOR is essentially characterized by the number of points
i in the set
{0,1,…,n−2} for which
Df(i)=Df(i+2), where
Df is the predicate corresponding to
f. The number of such points is called the odd-even degree of
f. We show that the
PP complexity of
f∘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
PPcc and
UPPcc via an
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 lower bounds for
f∘XOR, when
f is symmetric and periodic with period
O(n1/2−ε), for any constant
ε>0.
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), 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∘AND2 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.
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.
We call
F:{0,1}n×{0,1}n→{0,1} a symmetric XOR function if for a function
S:{0,1,...,n}→{0,1},
F(x,y)=S(∣x⊕y∣), for any
x,y∈{0,1}n, where
∣x⊕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, both the error-bounded randomized complexity and quantum communication with entanglement complexity are
Θ(r0+r1), where
r0 and
r1 are the minimum integers such that
r0,r1≤n/2 and
S(k)=S(k+2) for all
k∈[r0,n−r1).