New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
Authors:
Prantar Ghosh, Vihan Shah.
Abstract:
We show new lower bounds in the \emph{Merlin-Arthur} (MA) communication model and the related \emph{annotated streaming} or stream verification model.
The MA communication model is an enhancement of the classical communication model, where in addition to the usual players Alice and Bob, there is an all-powerful but untrusted player Merlin who knows their
inputs and tries to convince them about the output.
Most functions have MA protocols with total communication significantly smaller than what would be needed without Merlin.
We focus on the online MA (OMA) model, which is the MA analogue of one-way communication, and introduce the notion of \emph{non-trivial-OMA} complexity of a function.
This is the minimum total communication needed by any non-trivial OMA protocol computing that function, where a trivial OMA protocol is one where Alice sends
Bob roughly as many bits as she would have sent without Merlin.
We prove a lower bound on the non-trivial-OMA complexity of a natural function \emph{Equals-Index} (basically the well-known Index problem on large domains)
and identify it as a canonical problem for proving strong lower bounds on this complexity: reductions from it (i) reproduce and/or improve
upon the lower bounds for all functions that were previously known to have large non-trivial-OMA complexity, (ii) exhibit the first explicit functions whose non-trivial-OMA complexity is superlinear,
and even exponential, in their classical one-way complexity, and (iii) show functions on input size $n$ for which this complexity is as large as $n/\log n$.
While exhibiting a function with $\omega(\sqrt{n})$ (standard) OMA complexity is a longstanding open problem, we did not even know of any function with $\omega(\sqrt{n})$ non-trivial-OMA complexity.
Next, we turn to the annotated streaming model, the Prover-Verifier analogue of single-pass data streaming. We reduce from Equals-Index to establish strong lower bounds on the non-trivial complexity (for the analogous notion in this setting) of the fundamental streaming problem of counting distinct items, as well as of graph problems such as $k$-connectivity (both vertex and edge versions) in a certain edge update model that we call the \emph{support graph turnstile} (SGT) model. To set the benchmark space under which non-trivial annotated streaming schemes should solve these problems, we design classical streaming (sans Prover) algorithms for them under SGT streams by building \emph{strong} $\ell_0$-samplers that are robust to such streams and might be of independent interest. Finally, we exploit graph theoretic properties to design efficient schemes for $k$-connectivity on dynamic graph streams. This establishes a conceptual separation between classical streaming and annotated streaming: the former can handle certain turnstile and SGT streams almost as efficiently as dynamic streams, but the latter cannot.
Next, we turn to the annotated streaming model, the Prover-Verifier analogue of single-pass data streaming. We reduce from Equals-Index to establish strong lower bounds on the non-trivial complexity (for the analogous notion in this setting) of the fundamental streaming problem of counting distinct items, as well as of graph problems such as $k$-connectivity (both vertex and edge versions) in a certain edge update model that we call the \emph{support graph turnstile} (SGT) model. To set the benchmark space under which non-trivial annotated streaming schemes should solve these problems, we design classical streaming (sans Prover) algorithms for them under SGT streams by building \emph{strong} $\ell_0$-samplers that are robust to such streams and might be of independent interest. Finally, we exploit graph theoretic properties to design efficient schemes for $k$-connectivity on dynamic graph streams. This establishes a conceptual separation between classical streaming and annotated streaming: the former can handle certain turnstile and SGT streams almost as efficiently as dynamic streams, but the latter cannot.
Conference version:
[PDF]
Full version:
[arXiv]