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 an Omega(sqrt{n}/T) lower bound for the space required by anyunidirectional constant-error randomized T-pass streaming algorithm thatrecognizes whether an expression over two types of parenthesis iswell-parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak(2009) and rigorously establishes that bidirectional streams are exponentiallymore efficient in space usage as compared with unidirectional ones. We obtainthe lower bound by establishing the minimum amount of information that isnecessarily revealed by the players about their respective inputs in atwo-party communication protocol for a variant of the Index function, namelyAugmented Index. The information cost trade-off is obtained by a novelapplication of the conceptually simple and familiar ideas such as averageencoding and the cut-and-paste property of randomized protocols.  Motivated by recent examples of exponential savings in space by streamingquantum algorithms, we also study quantum protocols for Augmented Index.Defining an appropriate notion of information cost for quantum protocolsinvolves a delicate balancing act between its applicability and the ease withwhich we can analyze it. We define a notion of quantum information cost whichreflects some of the non-intuitive properties of quantum information and give atrade-off for this notion. While this trade-off demonstrates the strength ofour proof techniques, it does not lead to a space lower bound for checkingparentheses. We leave such an implication for quantum streaming algorithms asan intriguing open question.

The space complexity of recognizing well-parenthesized expressions in the streaming model: the Index function revisited