PaperlayerView exact revision on arXiv

Source-linked AI summary

UPP$^{\text{cc}}$ is Not Closed Under Intersection

Mark Bun, Mandar Juvekar

arXiv:2610.37634v1cs.CC

TL;DR

Whether UPPcc is closed under intersection remained unresolved. Using a continuous average-margin analysis and transferring its bound to explicit halfspace matrices, the paper gives a negative answer, with U(F)=O(log n) but U(F ∧ F)=Ω(√n).

  • Problem

    Whether UPPcc is closed under intersection remained unresolved, despite prior work showing that intersection can increase unbounded-error communication complexity.

    Source: §1 · p. 3

  • Method

    The authors bound average margins for conjunctions of inner-product sign tests on spheres using rotational symmetry, then transfer the bound to finite halfspace matrices.

    Source: §1.1.2 · p. 5, §5 · p. 24, §6 · p. 27

  • Results

    U(F)=O(log n) while U(F ∧ F)=Ω(√n) for an explicit family of functions on n-bit inputs.

    Source: §1 · p. 3

  • Takeaways & Limitations

    UPPcc is not closed under intersection, and the separation is tight for the bounded integer halfspace family when M=2^Θ(d).

    Source: §1 · p. 3

    The construction does not achieve the near-maximal separation U(F)=O(log n) versus U(F ∧ F)=Θ(n).

    Source: §1.4 · p. 11

Abstract

from arXiv · show

The sign rank of a ${\pm 1}$-valued matrix $A$ is the minimum rank of a real matrix that agrees with $A$ entrywise in sign. For every sufficiently large $d$, we give an explicit matrix $A$ with $2^{\Theta(d^2)}$ rows and columns and sign rank $\Theta(d)$ such that $A \land A$ has sign rank $2^{\Theta(d)}$. Here, $A \land A$ is the communication matrix of the problem obtained by evaluating $A$ on disjoint inputs and taking the conjunction of the results. As the logarithm of sign rank characterizes unbounded-error communication complexity, this implies that the communication class $\mathsf{UPP}^{\mathsf{cc}}$ is not closed under intersection. The starting point for our lower bound is Forster's method, which relates the sign rank of a matrix to the average margin of representations of its rows and columns by points and halfspaces. We study a continuous analog for conjunctions of inner-product sign tests on the unit sphere. Rotational symmetry connects this problem to polynomial sign representations, yielding an exponentially small upper bound on the average margin. This bound holds even when sign constraints are relaxed near the sign tests' decision boundary, allowing us to transfer it to explicit finite sign matrices arising from intersections of integer halfspaces.

1 Introduction

The introduction presents an explicit halfspace problem whose two-fold intersection has higher unbounded-error communication complexity, supported by a continuous average-margin argument and a boundary-tolerant transfer. It places the spherical symmetrization in context and outlines open questions about intersection gaps, finite-dimensional bounds, and lifting sign degree to sign rank.

1 Introduction

  • For M ≥ 2^cd, U(HS_M,d) = O(log d) but U(HS_M,d ∧ HS_M,d) = Ω(d); both bounds are tight for M = 2^Θ(d).The same separation holds for halfspace evaluation on 2^Θ(d^2) random points on the unit sphere.Source: §1 · p. 3

1.1.1 Sign rank

  • Sign rank is the minimum rank of a real matrix agreeing entrywise in sign, and it equals the minimum dimension of a point-and-hyperplane arrangement realizing the matrix.The communication matrix of HS_M,d has sign rank at most d + 1, giving unbounded-error communication complexity O(log d).Source: §1.1.1 · p. 4

1.1.2 A continuous formulation

  • Rotational symmetry yields a smooth symmetrized function whose sign represents the conjunction of two inner-product tests, and its expected absolute value is at most 2^-Ω(d).Taylor approximation and the impossibility of polynomially sign-representing the quadrant indicator force the function to be small near the origin; concentration then bounds average margin.Source: §1.1.2 · pp. 5–6

1.1.3 Transfer to the discrete problem

  • Rounding continuous sphere inputs can reverse signs near decision boundaries, so the argument allows sign errors there and uses polynomial interpolation to recover the exponential average-margin bound.The strengthened approximation result bounds Taylor-polynomial coefficients, yielding |H(s1, s2)| ≤ 2^-Ω(d) on a constant-sized neighborhood of the origin.Source: §1.1.3 · pp. 6–7

Threshold-of-Majority Circuit Size.

  • Threshold-of-Majority circuits can grow exponentially under intersection: some polynomial-size-computable F has F ∧ F requiring size 2^Ω(√n).The result follows from the sign-rank lower bound and the relation between sign rank and Threshold-of-Majority circuit size.Source: Threshold-of-Majority Circuit Size · pp. 7–8
  • Intersections of two halfspaces have dimension complexity 2^Ω(d) on integer grids with O(d)-bit coordinates, and 2^Ω(√n) on the Boolean domain.Dimension complexity characterizes representations by feature maps and underlies low-dimensional exact reductions in learning frameworks.Source: Threshold-of-Majority Circuit Size · p. 8
  • The paper gives explicit Boolean matrices with (1/3)-approximate sign rank at most 2d + 1 but sign rank at least 2^Ω(d), an exponential separation.Prior work gave a quasipolynomial separation using intersections of majorities.Source: Threshold-of-Majority Circuit Size · p. 8

1.3 Related Work

  • Related work developed Forster-style average-margin methods for explicit sign-rank lower bounds and explored lifting sign-degree bounds to sign rank; showed a quasipolynomial increase under intersection.Forster’s technique and smooth dual distributions underpin this line of work, while continuous-space formulations enable topological approaches to communication lower bounds.Source: §1.3 · pp. 9–10
  • Topological methods yield Gap Hamming sign-rank bounds, but the Z2-index framework cannot prove bounds above log2 N, while continuous average-margin analysis gives quantitatively larger bounds for this problem [FHM+26].The paper’s approach connects spherical averaging to polynomial approximability and Forster’s average-margin condition.Source: §1.3 · p. 10
  • Spherical symmetrization is new in sign rank and communication complexity, though related rotational averaging appeared in learning theory.The learning-theory approach symmetrizes a learner on high-dimensional spheres to depend on an inner product, then uses a low-degree polynomial approximation.Source: §1.3 · p. 11

1.4 Open Questions

  • An open question is whether the sign rank of HSM,d ∧HSM,d stays bounded over all arrangements for each fixed d, which would resolve whether U(F ∧F) is bounded by a function of U(F).The cited average-margin bound for intersections is at most exponential in the sign rank of the matrices, so resolving this would require going beyond average-margin lower bounds.Source: §1.4 · p. 11
  • The paper asks how much AND2 or ANDk intersections can increase U(F), and its construction does not attain the nearly maximal gap U(F) = O(log n) versus U(F ∧F) = Θ(n).Results are often stated for k-fold intersections; the authors say it is essentially no loss to read them with k = 2.Source: §1.4 · pp. 11–12
  • The authors ask whether their techniques can provide a more general lifting theorem from sign degree to sign rank, complementary to the pattern matrix method.In particular, they ask whether some sign-degree dual witnesses could be lifted by these techniques even when their smoothness is insufficient for existing pattern-matrix results.Source: §1.4 · p. 11

2 Preliminaries

The preliminaries relate unbounded-error communication complexity to sign rank and collect probability bounds for random points on the sphere. These bounds include inner-product tails and coverage by random neighborhoods.

2 Preliminaries

  • U(F) = log(rank±(M_F)) ± O(1), linking unbounded-error communication complexity to the sign rank of its communication matrix.Sign rank is the least rank of a real matrix that agrees entrywise in sign with the Boolean matrix.Source: §2 · p. 13

2.1 Random Points on the Sphere

  • For independent uniform points on S^(d−1), the probability that their inner product has magnitude at least δ is bounded above and below as a function of δ and d.The bounds are given in Proposition 2.2.Source: §2.1 · p. 13
  • With N ≥ e^(bd^2) independent uniform points on S^(d−1), the probability that some sphere point is farther than e^(−ad) from every sample is at most 1/N.For each constant a > 0, Lemma 2.3 supplies a corresponding constant b > 0 and requires sufficiently large d.Source: §2.1 · p. 13

3 Derivatives of Spherical Averages

The section studies spherical averages of bounded functions, using rotational symmetry and polynomial expansions to establish smoothness and Taylor approximation near the origin.

3 Derivatives of Spherical Averages

  • The spherical symmetrization H of bounded measurable functions has small derivatives near the origin and is well-approximated there by its Taylor polynomial.Theorem 3.1 establishes continuity on [−1,1]^k and continuous differentiability through order floor((d−2)/2).Source: §3 · pp. 14–15

3.1 Gegenbauer Polynomials

  • Gegenbauer polynomials, which arise as spherical averages of Fourier frequencies, provide the polynomial basis used to control derivatives on subintervals.Theorem 3.5 gives a uniform derivative bound on subintervals of [−1,1].Source: §3 · p. 14, §3.1 · p. 16

3.2 Series Expansions of Symmetrized Functions

  • The spherical symmetrization has a uniformly convergent series expansion in products of Gegenbauer polynomials, with coefficients whose total magnitude is bounded.This expansion is used to derive the derivative bounds for H.Source: §3.2 · p. 18, §3.3 · pp. 19–20

3.3 Proof of Theorem 3.1

  • The proof of the derivative result combines the series expansion with termwise derivative bounds to obtain uniform convergence of differentiated series near the origin.The argument applies the Gegenbauer derivative bounds on a subinterval around zero.Source: §3.3 · pp. 19–20

4 Bounds for Approximations to the Orthant

The section bounds polynomial approximations to the orthant function, first through degree lower bounds for strict sign representations and then through coefficient bounds for approximate representations.

4 Bounds for Approximations to the Orthant

  • A low-degree polynomial that nearly sign-represents Q_k outside narrow bands around the coordinate hyperplanes must have small coefficients.The approximation condition is imposed on I_η^k, excluding a band around each coordinate hyperplane.Source: §4 · p. 20

4.1 Degree Lower Bounds for Strict Sign Representations

  • A polynomial sign-representing Q_k on I_η^k must have degree greater than 2C ln(1/η), for a universal constant C.The lower bound follows by relating a sign representation of the conjunction to rational approximations of its individual sign tests, using Sherstov's theorem [She13a].Source: §4.1 · p. 21

4.2 Coefficient Upper Bounds for Approximate Sign Representations

  • The coefficient bound is proved by converting a large-coefficient approximate representation into a strict sign representation, contradicting the degree lower bound.The conversion uses an integral bound on polynomial coefficients and constructs a degree-D polynomial that sign-represents Q_k on a slightly narrower domain.Source: §4.2 · pp. 21, 23, 24

5 Average Margin Bounds for CHS ∧CHS

The authors bound the average margin of continuous representations of CHS ∧ CHS, even when sign constraints are relaxed near the coordinate axes. The resulting bound is exponentially small in d.

5 Average Margin Bounds for CHS ∧ CHS

  • Averaging over sphere points with fixed paired inner products yields the symmetrized function H, whose expected magnitude is used to bound the embedding's average margin.The theorem's sign condition is needed only outside the narrow band around the coordinate axes.Source: §5 · pp. 24–26
  • E[|B(X,Y)|] = e^(−Ω(d)) for bounded embeddings that satisfy the sign condition whenever every paired inner product has magnitude greater than e^(−Cd).Theorem 5.1 permits a narrow excluded band around the coordinate axes.Source: §5 · pp. 24, 26
  • The proof symmetrizes the embedding inner product, uses a Taylor polynomial and orthant coefficient bounds to show the spherical average has low magnitude, then applies inner-product concentration.The degree-D Taylor polynomial has exponentially small coefficients for degrees at most D/2.Source: §5 · pp. 24–25

6 Rounding to the Discrete Setting

A generalized Forster argument transfers small average-margin bounds from continuous problems to discrete sign matrices obtained through well-behaved rounding. For intersections of two halfspaces, this yields an exponential sign-rank lower bound when the rounded tests agree with spherical inner-product signs away from a narrow boundary.

6 Rounding to the Discrete Setting

  • The transfer theorem bounds sign rank using the supremum average inner product of bounded arrangements that satisfy the sign constraints outside an exceptional set.It generalizes Forster’s theorem to discrete problems obtained from continuous problems through sufficiently well-behaved rounding maps.Source: §6 · pp. 26–27
  • If rounded entries match spherical inner-product signs whenever |⟨x, y⟩| > e^-Cd, then rank±(B ∧ B) ≥ e^cd for sufficiently large d.The transfer applies to measurable maps from the sphere into the discrete row and column sets.Source: §6 · p. 27
  • For two intersected halfspace tests, the continuous bound makes the supremum average inner product at most e^-cd, which yields the exponential discrete lower bound.The proof applies the continuous result to independent uniform points on (S^{d−1})².Source: §6 · p. 28

7 Proof of the Main Theorems

The paper establishes an exponential sign-rank separation for both an explicit integer halfspace matrix and a matrix sampled from random unit vectors. In both settings, the individual matrix has low sign rank, while its intersection with itself has exponentially larger sign rank.

7.1 The Sign Rank of HS ∧HS

  • For M ≥ ⌈e^Cd⌉, rank±(HS_M,d) ≤ d + 1 while rank±(HS_M,d ∧ HS_M,d) ≥ e^cd, giving U = O(log n) versus Ω(√n).Here n is the number of bits needed to encode each row and column, with n = O(d²) for the chosen M.Source: §7.1 · pp. 28–29
  • Rounding sphere coordinates to multiples of 1/M preserves inner-product signs whenever |⟨x, y⟩| > e^-C′d, enabling the discrete lower bound.The proof chooses M exponentially large in d so the rounding error stays below the sign-test boundary.Source: §7.1 · pp. 28–29

7.2 Matrices of Random Unit Vectors

  • With probability 1 − o(1), N = ⌈e^Cd²⌉ random sphere points per side give rank±(G) ≤ d and rank±(G ∧ G) ≥ e^cd.The lower bound follows because the sampled points form a sufficiently fine net of the sphere, preserving signs away from the boundary.Source: §7.2 · p. 29

8 On the Tightness of Our Bounds

The paper shows its continuous average-margin upper bound and discrete sign-rank lower bounds are essentially tight. It establishes tightness for weak and strong sign representations in the continuous setting and gives matching-scale upper bounds for the discrete constructions.

8 On the Tightness of Our Bounds

  • For k = 2, even one-dimensional arrangements that weakly sign-represent the conjunction everywhere can attain average margin 2^-Θ(d).The construction uses a spherical cap of measure 2^-Θ(d), so the expected product is the square of that measure.Source: §8 · p. 30
  • The continuous average-margin bound remains essentially tight for strong sign representations, even when signs are required only outside a margin ε around each test boundary.Combining a weak low-margin arrangement with a strong arrangement preserves strong sign agreement while keeping the expected margin 2^-Θ(d).Source: §8 · p. 30
  • A polynomial sign representation of the k-fold conjunction on tests bounded away from zero has degree O(k² log(1/η)), yielding a corresponding upper bound on sign rank.The polynomial is constructed by combining rational approximations to the sign function; the sign-rank bound applies when all inner products have magnitude at least η.Source: §8 · p. 31
  • For M = 2^Θ(d), the integer halfspace intersection lower bound is tight, while the random-vector lower bound is tight up to a factor of log d in the exponent.The latter tightness statement applies for ⌈e^Cd²⌉ ≤ N ≤ 2^{d^{O(1)}}.Source: §8 · pp. 31–32

9 Applications

The paper applies the halfspace intersection separation to circuit complexity, learning theory, and approximate sign rank. These applications give exponential lower bounds for intersections despite efficient representations of individual halfspaces or low-dimensional approximate representations.

9 Applications

  • The halfspace problem on nonnegative integer inputs is equivalent to the shifted integer halfspace problem and can be expressed using a sparse sum of pairwise products of Boolean input bits.The representation uses O(d log² M) pairs of bit indices.Source: §9 · p. 33

9.1 Threshold-of-Majority Circuit Size

  • An explicit F on 2n Boolean inputs has polynomial-size Threshold-of-Majority circuits, but every such circuit for F ∧ F requires size 2^Ω(√n).The individual function has a Threshold-of-AND2 circuit of size O(d log² M).Source: §9.1 · pp. 33–34

9.2 Dimension Complexity of Intersections of Halfspaces

  • Intersections of two halfspaces have dimension complexity 2^Ω(d) on integer grids with O(d)-bit coordinates, and 2^Ω(√n) on the Boolean domain {0,1}^n.The Boolean-domain bound follows by encoding the integer halfspace problem over n = Θ(d²) variables.Source: §9.2 · p. 34

9.3 Approximate vs. Exact Sign Rank

  • Explicit Boolean matrices can have (1/3)-approximate sign rank at most 2d + 1 but exact sign rank at least 2^Ω(d).The approximate bound allows a row vector chosen for each distribution over columns while limiting its classification error to 1/3.Source: §9.3 · p. 34

A.1 Tail Bounds for Inner Products of Random Unit Vectors

The appendix bounds the probability that the inner product of two independent uniform unit vectors lies near zero or exceeds a threshold. The proof uses rotational symmetry to express that inner product through Gaussian variables.

A.1 Tail Bounds for Inner Products of Random Unit Vectors

  • Rotational symmetry identifies the inner product with the first coordinate of a uniform point on the sphere, and hence with a normalized Gaussian coordinate.The proof represents it as G1 divided by the square root of G1^2 + V^2, where V^2 sums the other Gaussian squares.Source: §A.1 · p. 39
  • The upper-tail bound follows by combining Markov’s inequality with independence of the Gaussian variables.The passage states that chaining these inequalities yields the upper tail bound of Proposition 2.2.Source: §A.1 · p. 39
  • For 0 < δ < 1/2, the lower-tail proof conditions on the Gaussian variables and averages a density-based bound.The argument uses the normalized-Gaussian representation and then averages over V.Source: §A.1 · p. 40

A.2 Properties of Gegenbauer Polynomials

This section establishes properties of normalized Gegenbauer polynomials, including a spherical averaging identity, boundedness, and dimension reduction. The averaging identity follows from polynomial degree and orthogonality.

A.2 Properties of Gegenbauer Polynomials

  • Spherical averaging of a degree-i polynomial orthogonal to all lower-degree polynomials gives its value at x times the normalized Gegenbauer polynomial G_i^d(t).The proof shows the average is a degree-i polynomial orthogonal to all lower degrees, then fixes its scale using its value at t = 1.Source: §A.2 · pp. 40–41
  • For every i ≥ 0 and t in [−1, 1], the normalized Gegenbauer polynomial satisfies |G_i^d(t)| ≤ 1.The proof bounds the spherical average by the maximum absolute value of the original polynomial.Source: §A.2 · pp. 40–41
  • For d ≥ 4, G_i^d is a convex combination of G_j^{d−2} for 0 ≤ j ≤ i with j congruent to i modulo 2.The proof reduces this to showing the orthogonal-expansion coefficients are nonnegative.Source: §A.2 · pp. 40, 42
  • The derivative recurrence is stated as another property of the normalized Gegenbauer polynomials for d ≥ 4.The supplied passage identifies the recurrence but does not include its formula.Source: §A.2 · p. 41

A.3 Rational Approximations to the Sign Function

The section proves a degree lower bound for rational approximations to the sign function away from zero. Its proof follows Newman’s argument, using polynomial factorization and logarithmic integration.

A.3 Rational Approximations to the Sign Function

  • D ≥ 2C ln(2k − 1) ln(1/η) when p/q approximates sgn x within 1/k on Iη, for a universal constant C > 0.The polynomials p and q have degree at most D, and q is nonzero on Iη.Source: §A.3 · p. 43
  • The proof follows Newman’s argument by converting the approximation into inequalities for p − q and p + q, then integrating logarithms after factoring their roots.The argument uses the polynomials’ complex roots and combines the resulting inequalities to obtain the degree bound.Source: §A.3 · pp. 43–44
  • The logarithmic integral remains convergent as an improper integral even if A(x)B(−x) has roots.Source: §A.3 · p. 43

A.4 Properties of (Shifted) Legendre Polynomials

This section proves properties of shifted Legendre polynomials on [1, 2], including orthogonality, a uniform bound, and a bound on coefficient magnitudes. The orthogonality proof uses binomial identities and polynomial expansion.

A.4 Properties of (Shifted) Legendre Polynomials

  • The shifted Legendre polynomials satisfy the stated orthogonality integral: 1/(2i + 1) when i = j, and 0 otherwise.The proof reduces the integral to coefficient sums that vanish for i < j and equal 1 for i = j.Source: §A.4 · pp. 44–45
  • The sum of the magnitudes of the coefficients of L_i is at most 12i.The proof bounds coefficient sums for powers of (t − 1) and (t − 2), then combines those bounds.Source: §A.4 · pp. 44, 46
  • On [1, 2], the shifted Legendre polynomial satisfies |L_i(t)| ≤ 1.The proof bounds λL_i(t)^2 by λ using endpoint values of the associated expression.Source: §A.4 · pp. 45–46
Loading 2610.37634v1…