Unbounded-error communication is not closed under AND, found with GPT-6 Astra
Awaiting review
The takeaway
Unbounded-error communication complexity (UPP^cc) is the communication analogue of PP. Beigel, Reingold and Spielman proved in 1995 that PP is closed under intersection. Whether UPP^cc is closed under intersection had been asked since Halstenberg and Reischuk (1988). In a 27 Oct preprint, Mark Bun and Mandar Juvekar (Boston University) give explicit matrices of sign rank Θ(d) whose AND has sign rank 2^Θ(d). The previous gap, by Bun, Mande and Thaler, was only log versus log². The paper began when they asked GPT-6 Astra how to beat that gap. ‘To our (in retrospect, naïve) astonishment,’ they write, the model ‘discovered what appeared to be complete proofs’.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- 3 of 5
- Last verified
- 29 October 2026
Your AI and this story
- GPT-6 Astra180 days after its cutoff
- Claude Opus 5.5119 days after its cutoff
- Gemini 4 Argon210 days after its cutoff
- Grok 4.7149 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 119 days before it.
Key facts
- Abstract: ‘For every sufficiently large d, we give an explicit matrix A with 2^Θ(d²) rows and columns and sign rank Θ(d) such that A ∧ A has sign rank 2^Θ(d). … this implies that the communication class UPP^cc is not closed under intersection’
- Concrete form (Theorem 1.2): the bounded integer halfspace problem HS_{M,d} has U(HS_{M,d}) = O(log d), while U(HS_{M,d} ∧ HS_{M,d}) = Ω(d) for M ≥ 2^{cd}; on n-bit inputs this is O(log n) versus Ω(√n), and both bounds are tight for this family
- Prior state: the only earlier example of growth under intersection was Bun–Mande–Thaler (ACM TOCT 2021), U(F) = O(log n) but U(F ∧ F) = Θ(log² n). The question was first asked explicitly by Halstenberg and Reischuk [HR88] and reiterated in Göös–Pitassi–Watson (2018), Sherstov (2018), BMT21 and BT22, per the paper
- AI acknowledgment (verbatim): ‘This paper arose out of our prompting OpenAI’s GPT-6 Astra model for ideas on how to improve the separation of [BMT21] beyond the quadratic gap they achieved. To our (in retrospect, naïve) astonishment, it discovered what appeared to be complete proofs that (slightly different parameterizations) of the functions we consider in this paper yield the separation U(f) = O(log n) vs. U(f ∧ f) = Ω(n^{1/4}). Subsequent interactions with GPT-6 Astra helped us understand the argument, simplify it, and improve it quantitatively.’
- Writing: ‘The text of this manuscript was written by the authors, with additional AI assistance used to locate references and provide feedback on our exposition.’ Access came through OpenAI’s ChatGPT for Academic Researchers program
- Status: unrefereed preprint; no expert comment found as of 29 Oct
What happened
In unbounded-error communication, two players need only beat a coin flip, and the cost of a problem is governed by the sign rank of its matrix. Because error cannot be amplified in this model, closure properties are hard to prove. The class PP of complexity theory was shown to be closed under intersection in 1995, but the communication analogue stayed open. The only known example of growth under AND, due to Bun, Mande and Thaler, raised the cost from log n to log² n.
Bun and Juvekar asked GPT-6 Astra how to go beyond that quadratic gap. The model returned arguments that appeared to prove a polynomial gap for halfspace problems. Working further with the model, the authors simplified the proof and pushed it to an exponential separation in sign rank, which they say is tight for the family.
Why it matters
It answers a structural question that has been open for about 38 years and that several recent surveys repeated. The authors’ account is unusually direct: the core proof came from the model in response to a request for ideas, and the humans’ work was to understand, verify, simplify and strengthen it.
What is disputed or not yet verified
| Verification | Unrefereed arXiv preprint |
|---|
Sources
1 source from 1 site. Numbers match the chips in the text.
1 source: 1 primary
Primary
Changes
- Filed (arXiv PDF of 2610.37634)