Source-linked AI summary
Pseudodeterminism and MA != NP^BPP in Communication Complexity
Thomas Watson
TL;DR
The paper studies pseudodeterministic communication for partial Boolean functions, where pseudodeterministic complexity is characterized through randomized algorithms for total extensions. It improves a prior separation to zero-sided error and extends the approach to separate MA from NP^BPP in communication complexity.
Problem
Pseudodeterministic communication differs from ordinary randomized communication because invalid inputs must receive a consistently high or low acceptance probability.
Method
The paper characterizes pseudodeterministic complexity via randomized complexity of total functions agreeing with the partial function, and relates NP^BPP to N qBPP within MA.
Results
The prior upper bound is improved to zero-sided error, yielding ZPP ⊄ psP and separating MA from NP^BPP in communication complexity.
Takeaways & Limitations
The results advance communication-complexity lower bounds near the frontier represented by MA and its related classes.
Abstract
from arXiv · showhide
We prove an exponential separation between zero-sided-error randomized and two-sided-error pseudodeterministic communication complexities of partial boolean functions. This qualitatively improves and simplifies the proof of the separation by Göös, Harms, Riazanov, Sofronova, Sokolov, and Yuan (STOC 2026), which had a two-sided-error randomized upper bound. Then, we generalize our technique to separate the communication complexity analogues of MA and NP^BPP.
1 Introduction
The paper studies pseudodeterministic communication complexity and proves separations from randomized and MA-type protocols, strengthening prior communication-complexity results. It also develops the NPBPP = N qBPP framework and places these classes within broader open questions about the communication polynomial hierarchy.
- Pseudodeterminism: Pseudodeterministic algorithms output one fixed solution with high probability, unlike general randomized algorithms whose successful outputs may vary.This places pseudodeterminism between deterministic and randomized computation and allows success probability amplification in settings where solutions are not efficiently checkable.
- Definitions: For partial Boolean functions, pseudodeterministic complexity is the minimum randomized complexity of a total extension agreeing with the function on valid inputs.Invalid inputs may be assigned either Boolean output by the extension, reflecting the promise-function interpretation.
- Pseudodeterministic communication complexity: Theorem 1 proves ZPP ⊄ psP in communication complexity, improving the prior separation by achieving a zero-sided-error randomized upper bound.The prior result separated BPP from psP with an O(log N) randomized upper bound, while its argument did not provide one-sided error.
- MA versus NPBPP: NPBPP equals N qBPP, where a short witness is appended to the inputs and a BPP protocol must accept some witness on 1-inputs and reject every witness on 0-inputs.For N qBPP, every witness has acceptance probability either at least 2/3 or at most 1/3, connecting the class to pseudodeterminism.
- MA versus NPBPP: Theorem 2 proves MA ⊄ NPBPP in communication complexity, contributing to the separation of subclasses within the communication polynomial hierarchy.MA is close to the frontier of known communication lower bounds and has applications in streaming, property testing, hardness of approximation, and cryptography.
2 Approach
The approach adapts query-to-communication lifting to prove separations unavailable from existing general lifting theorems, using iterative input modification and boosting arguments.
- Query-to-communication lifting: Query-to-communication lifting transfers query lower bounds to communication lower bounds by composing an outer function with a gadget.The gadget prevents communication protocols from doing substantially better than evaluating queried bits directly.
- Query-to-communication lifting: No general lifting theorems are known for psP or NPBPP, so the proofs use a white-box strategy tailored to specific query lower bounds.The simplest query-complexity proofs are not directly liftable.
- ZPP versus psP: In communication complexity, the proof tracks a large fraction of accepted inputs in a slice and interleaves boosting with batches of pn bit flips.Typically only about 0.01pn bits are fixed per iteration, so the protocol hardly notices the batch; unusually costly iterations are limited by a potential function.
- Proof strategy: The paper simplifies the earlier ZPP versus psP proof by focusing on an individual changing input and using the lifting theorem of [GLMWZ16].Its outline remains similar to, but the technical details differ fundamentally in this focus.
3 ZPP̸ ⊆psP
The construction composes a partial outer function with a gadget and proves it lies in ZPP while no low-cost pseudodeterministic protocol can compute any total extension.
- Upper bound: F is in ZPP because protocols randomly select and evaluate a gadget coordinate from either the right or left half.Each half supplies a one-sided randomized protocol.
- Contradiction setup: The contradiction assumes a cost d = 0.01pn randomized protocol for a total extension F′, amplified to two-sided error 0.01.The proof maintains a focused input, a balanced rectangle, a structure, and a potential-like parameter k.
- Iterative process: Each safe iteration flips pn zeros to ones in the left half and increases k by at most d + 13, while each unsafe iteration leaves z unchanged and decreases k.The process repeatedly shrinks the rectangle while maintaining its structural invariants.
- Width bound: The total increase in k is bounded by (d + 13)pn/3, implying w ≤ 0.02n when d = 0.01pn.Here w is the structure width, and unsafe iterations offset width increases.
- Safe iterations: A safe iteration is selected from balanced subrectangles whose associated structure increases width by at most 3d.The construction samples a random set I of pn currently unfixed zero coordinates and updates z, the structure, and the rectangle.
4 MA̸ ⊆NPBPP
The paper constructs a partial Boolean function F in MA with O(log n) communication cost, then proves that F has no low-cost NP^BPP-type protocol. The separation follows from preprocessing and iterative phases that maintain structured rectangles while forcing a contradiction.
- Function and MA protocol: F is defined by applying f to the coordinatewise composition g_n(x,y), namely F(x,y)=f(g_n(x,y)).
- Function and MA protocol: An MA-type protocol for F uses one randomized coordinate test over the first half and deterministic tests for each coordinate in the second half, with cost O(log n).If F(x,y)=1, at least one protocol outputs 1 with probability 1; if F(x,y)=0, every protocol outputs 1 with probability at most 1/3.
- Excluding NP^BPP: Assuming an NP^BPP protocol of cost d=0.01pn, the proof amplifies its BPP component to error 0.01 and selects a deterministic protocol from its support.The argument proceeds through preprocessing followed by an iterative phase over left- and right-half coordinates.
- Excluding NP^BPP: The preprocessing phase starts from z=1^{n/2}0^{n/2}, where f(z)=1, and restricts attention to a protocol agreeing with F on the valid inputs.The selected protocol is analyzed on structured rectangles associated with the 1- and 0-input regions of an extension F′.
- Iterative contradiction: Each iteration extends the rectangle structure and is safe or unsafe: safe iterations flip pn many bits of z and unsafe iterations increase the structure width.The invariant continues until |z←|≤n/6, yielding pn/3 safe iterations and ultimately f(z)=0.
- Iterative contradiction: The contradiction is that the final z satisfies f(z)=0, so R_z⊆F_0⊆F′_0, while the maintained rectangle and protocol properties force incompatible behavior.The width remains bounded by w≤0.02n during the iteration, supporting the final contradiction.