💻 computer science

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

This paper proves that the communication class $\mathsf{UPP}^{\mathsf{cc}}$ is not closed under intersection by constructing an explicit matrix with low sign rank whose conjunction exhibits exponentially higher sign rank, a result established through a novel continuous analog of Forster's method linking rotational symmetry to polynomial sign representations.

Original authors: Mark Bun, Mandar Juvekar

Published 2026-10-28

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Mark Bun, Mandar Juvekar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computer science, there is a fundamental question about how much information two people need to share to solve a problem together. Imagine two friends, Alice and Bob, who each hold a piece of a puzzle. They cannot see each other's pieces, and they want to figure out if their pieces fit together to form a specific shape. They can talk to each other, but they want to say as little as possible. In the standard version of this game, they are allowed to make a few mistakes, as long as they are right most of the time. However, there is a more extreme version of the game where they are only allowed to be right slightly more often than if they were just guessing blindly. This is called the unbounded-error model. It is a powerful way of thinking about communication because it strips away the safety net of high accuracy, forcing the players to rely on the pure structure of the problem.

For decades, researchers have wondered if this powerful model behaves nicely when problems are combined. Specifically, if Alice and Bob can solve one puzzle with very little talking, and they can solve a second, similar puzzle with very little talking, can they solve a combined puzzle—where they must solve both at the same time—without talking much more? Intuitively, one might expect the answer to be yes. If the rules of the game are simple enough for one task, they should remain simple enough for two. This question has remained a major open mystery in the field, with many experts suspecting the answer might be yes, but no one could prove it.

A team of researchers from Boston University has now settled this question with a definitive no. They have constructed a specific type of puzzle where Alice and Bob can solve a single instance with very little communication, but when they are forced to solve two instances simultaneously, the amount of information they must exchange explodes. The jump is not just a little bit larger; it is exponentially larger. To put this in perspective, if solving one puzzle requires a few words, solving two of them together might require a number of words so vast it would take a lifetime to speak them. This discovery proves that the class of problems solvable with minimal communication in this strict model is not closed under intersection, meaning that combining two easy problems can create a problem that is suddenly incredibly hard.

The researchers arrived at this conclusion by looking at a geometric version of the puzzle. Instead of abstract bits, they imagined Alice and Bob holding points on a sphere, a surface like the skin of a ball. The rule of the game is simple: they must determine if the angle between their two points is sharp or obtuse. This is a classic problem that is easy to solve with a small amount of communication. The researchers then asked what happens if Alice and Bob are given two pairs of points and must determine if both pairs form sharp angles. They found that while the single pair is easy, the double pair creates a geometric complexity that forces the communication cost to skyrocket.

To prove this, the team used a technique that translates the communication problem into a question about the shape of mathematical functions. They imagined the sphere not as a collection of points, but as a continuous surface where the rules of the game are smoothed out. By studying how these rules behave on the sphere, they discovered a hidden barrier. The rules for the combined puzzle require a function that changes sign in a very specific, jagged way, similar to how a shadow might fall on a corner. However, the smooth, continuous nature of the sphere makes it impossible to create a simple, low-dimensional shape that can mimic this jagged behavior without being extremely large.

The researchers showed that any attempt to represent the solution to the combined puzzle using a simple geometric arrangement would fail unless the arrangement was exponentially large. They demonstrated that the "margin" of error—the distance between the solution and the boundary of the decision—becomes vanishingly small. In the language of the field, this means the sign rank of the problem, which measures the complexity of the matrix representing the puzzle, grows exponentially. This growth is so severe that it cannot be bridged by any efficient communication protocol.

This result is not just a theoretical curiosity; it has immediate consequences for how we understand the limits of learning and circuit design. The researchers showed that their findings imply that certain types of computer circuits, which are built from layers of simple decision gates, must become exponentially larger when asked to perform two tasks at once. Similarly, in the field of machine learning, their work suggests that learning the intersection of two simple geometric shapes is fundamentally harder than learning just one, and that this difficulty cannot be overcome by simply finding a better way to represent the data.

The paper also addresses a related question about whether the difficulty of the combined problem is bounded by the difficulty of the original problem. The authors prove that no such bound exists. Even if the original problem is trivial, the combined problem can be arbitrarily difficult. This rules out the possibility of a universal rule that limits how much harder a combined problem can be. The researchers constructed their counterexample using a family of functions defined on integer grids, showing that the phenomenon occurs even in the most basic, discrete settings.

One of the most striking aspects of the work is the method used to bridge the gap between the continuous sphere and the discrete grid. The researchers first solved the problem on the smooth sphere, where the mathematics of symmetry allowed them to see the underlying structure clearly. They then developed a way to "round" this continuous solution back to the discrete world of integers. This rounding process is delicate because the decision boundaries in the discrete world are sharp, and a small error in rounding could flip the answer. The team proved that their continuous bounds were robust enough to survive this rounding, ensuring that the exponential gap holds true for the discrete problems as well.

The findings also shed light on the difference between exact and approximate solutions. The researchers showed that if we allow for a small amount of error in the solution, the problem becomes much easier to solve. However, if we demand an exact solution, the difficulty returns with full force. This distinction is crucial for understanding the limits of algorithms that are allowed to make mistakes versus those that must be perfect. The paper provides a clear sequence of examples where the gap between the approximate and exact difficulty is exponential, a much larger gap than previously known.

In the broader context of computer science, this work challenges the intuition that complexity is additive. It shows that complexity can be multiplicative, or even exponential, when problems are combined. This has implications for how we design algorithms and how we understand the fundamental limits of computation. The researchers' proof is rigorous and complete, leaving no room for doubt about the existence of this gap. They have provided a concrete family of functions that demonstrates this phenomenon, moving the question from a theoretical possibility to a mathematical fact.

The paper concludes by pointing out that while their construction achieves a significant separation, it is not the maximum possible separation. There is still room to explore whether the gap can be made even larger, potentially reaching the maximum possible difference between the single and combined cases. This opens the door for future research to push the boundaries even further. The work stands as a testament to the power of geometric intuition in solving abstract computational problems, showing that sometimes the best way to understand the limits of communication is to look at the shape of the space in which the communication happens.

Technical Summary: UPPcc is Not Closed Under Intersection

Problem Statement
The paper addresses a fundamental open question in communication complexity: whether the class UPPcc (unbounded-error probabilistic communication complexity) is closed under intersection. A function $F$ belongs to UPPcc if it can be computed with probability strictly greater than $1/2$ using polylogarithmic communication. While the analogous class PP is known to be closed under intersection, the status of UPPcc has remained unresolved. Specifically, the authors investigate whether there exists a function $F$ such that $U(F)$ is small (polylogarithmic) but $U(F \land F)$ is significantly larger.

The problem is analyzed through the lens of sign rank. Paturi and Simon established that the unbounded-error communication complexity $U(F)$ is characterized by the sign rank of its communication matrix $A$ , denoted $\text{rank}_{\pm}(A)$ , up to an additive constant: $U(F) = \log(\text{rank}_{\pm}(A)) \pm O(1)$ . The sign rank is the minimum rank of a real matrix that agrees with $A$ entrywise in sign. The authors aim to construct an explicit family of matrices where the sign rank of the intersection $A \land A$ is exponentially larger than the sign rank of $A$ .

Methodology
The authors employ a geometric approach centered on Forster's method, which relates sign rank lower bounds to upper bounds on the average margin of linear arrangements. The core technical strategy involves a continuous-to-discrete transfer:

Continuous Formulation: The authors define a continuous analog of the problem, denoted $\text{CHS}_d \land \text{CHS}_d$ , where inputs are points on the unit sphere $S^{d-1}$ rather than discrete vectors. A linear arrangement for this problem is represented by functions $f, g: (S^{d-1})^2 \to \mathbb{R}^r$ .
Rotational Symmetrization: They introduce a "symmetrized" function $H(s_1, s_2)$ , which represents the expected inner product of the arrangement vectors given fixed inner products $s_1, s_2$ of the inputs. This function $H$ depends only on the inner products of the inputs, allowing the exploitation of rotational symmetry.
Approximation Theory and Derivatives:
- Using Gegenbauer polynomials and spherical harmonic analysis, they prove that $H$ is smooth and has bounded derivatives up to order $O(d)$ . Consequently, $H$ is well-approximated by its low-degree Taylor polynomials.
- They leverage a contradiction between the smoothness of $H$ and the requirement that it must sign-represent the conjunction of sign tests (the "lower-left quadrant" indicator $Q_2(s_1, s_2) = \text{sgn}(s_1) \land \text{sgn}(s_2)$ ). Polynomials cannot sign-represent $Q_2$ effectively near the origin.
- To handle the fact that the arrangement might fail near the decision boundary (where inner products are close to zero), they utilize results from approximation theory (specifically extending work by Newman and Sherstov) to show that even approximate sign representations of $Q_2$ on restricted domains must have uniformly small coefficients if the degree is low.
Average Margin Bound: By combining the smoothness of $H$ with the coefficient bounds for polynomials that nearly sign-represent $Q_2$ , they prove that the average margin of any arrangement for the continuous problem is exponentially small ( $2^{-\Omega(d)}$ ).
Discrete Transfer: They construct a rounding procedure mapping discrete integer vectors to points on the sphere. They show that if the continuous problem has a small average margin even when sign constraints are relaxed near the boundary, then the discrete problem (bounded integer halfspaces) inherits this small average margin. By Forster's theorem, a small average margin implies a large sign rank.

Key Contributions and Results
The paper establishes the following main results:

Main Theorem: There exists an explicit family of functions $F$ $F$ (specifically, bounded integer halfspaces $H_{M,d}$ $H_{M, d}$ ) such that $U(F) = O(\log n)$ $U (F) = O (lo g n)$ but $U(F \land F) = \Omega(\sqrt{n})$ $U (F \land F) = Ω (n)$ .
- The function $H_{M,d}$ is defined on inputs $a, b \in \{-M, \dots, M\}^d$ as $\text{sgn}(\langle a, b \rangle - 1/2)$ .
- For $M = 2^{\Theta(d)}$ , the input size is $n = \Theta(d^2)$ . The sign rank of $H_{M,d}$ is $O(d)$ , while the sign rank of $H_{M,d} \land H_{M,d}$ is $2^{\Omega(d)} = 2^{\Omega(\sqrt{n})}$ .
Random Vectors: The separation also holds for matrices formed by random unit vectors on the sphere, where the sign rank of the intersection is exponentially larger than the original matrix with high probability.
Tightness: The authors demonstrate that their lower bound analysis is optimal for this family of functions. They show that the sign rank of the intersection is at most $2^{O(d + \log M)}$ , matching the lower bound when $M = 2^{\Theta(d)}$ .

Significance
The paper provides a definitive negative answer to the question of whether UPPcc is closed under intersection. This resolves a long-standing open problem in communication complexity.

The significance of this result extends to several other areas:

Circuit Complexity: It implies that the size of Threshold-of-Majority circuits can increase exponentially under intersection. While a function $F$ may be computable by a polynomial-size Threshold-of-Majority circuit, $F \land F$ may require size $2^{\Omega(\sqrt{n})}$ .
Learning Theory: It establishes that the dimension complexity of the class of intersections of two halfspaces is exponential ( $2^{\Omega(d)}$ ). This rules out low-dimensional exact reductions for learning intersections of halfspaces in frameworks relying on dimension complexity, such as certain stochastic convex optimization reductions.
Sign Rank vs. Approximate Sign Rank: The results provide an explicit family of matrices exhibiting an exponential separation between sign rank and approximate sign rank. While previous work showed quasipolynomial separations, this work demonstrates that the gap can be exponential.

The authors note that their techniques rely on a continuous analog of "lifting" sign degree lower bounds to sign rank, utilizing spherical averaging and topological arguments (via the Borsuk-Ulam theorem context) to bypass limitations of previous discrete methods. The work also acknowledges that the construction was initially inspired by AI-generated ideas, which the authors then rigorously verified and refined.

Technical Summary: UPPcc is Not Closed Under Intersection

More like this