English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show new lower bounds in the \emph{Merlin-Arthur} (MA) communication modeland the related \emph{annotated streaming} or stream verification model. The MAcommunication model is an enhancement of the classical communication model,where in addition to the usual players Alice and Bob, there is an all-powerfulbut untrusted player Merlin who knows their inputs and tries to convince themabout the output. Most functions have MA protocols with total communicationsignificantly smaller than what would be needed without Merlin. We focus on theonline MA (OMA) model, which is the MA analogue of one-way communication, andintroduce the notion of \emph{non-trivial-OMA} complexity of a function. Thisis the minimum total communication needed by any non-trivial OMA protocolcomputing that function, where a trivial OMA protocol is one where Alice sendsBob roughly as many bits as she would have sent without Merlin. We prove alower 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 thiscomplexity: reductions from it (i) reproduce and/or improve upon the lowerbounds for all functions that were previously known to have largenon-trivial-OMA complexity, (ii) exhibit the first explicit functions whosenon-trivial-OMA complexity is superlinear, and even exponential, in theirclassical one-way complexity, and (iii) show functions on input size $n$ forwhich this complexity is as large as $n/\log n$. While exhibiting a functionwith $\omega(\sqrt{n})$ (standard) OMA complexity is a longstanding openproblem, we did not even know of any function with $\omega(\sqrt{n})$non-trivial-OMA complexity. We further extend the lower bounds to a relatedstreaming model called annotated streaming.

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification