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/

Zendy Plus

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

Zendy Tools

Zendy Open

We study space-pass tradeoffs in graph streaming algorithms for parameterestimation and property testing problems such as estimating the size of maximummatchings and maximum cuts, weight of minimum spanning trees, or testing if agraph is connected or cycle-free versus being far from these properties. Wedevelop a new lower bound technique that proves that for many problems ofinterest, including all the above, obtaining a $(1+\epsilon)$-approximationrequires either $n^{\Omega(1)}$ space or $\Omega(1/\epsilon)$ passes, even onhighly restricted families of graphs such as bounded-degree planar graphs. Formultiple of these problems, this bound matches those of existing algorithms andis thus (asymptotically) optimal.  Our results considerably strengthen prior lower bounds even for arbitrarygraphs: starting from the influential work of [Verbin, Yu; SODA 2011], therehas been a plethora of lower bounds for single-pass algorithms for theseproblems; however, the only multi-pass lower bounds proven very recently in[Assadi, Kol, Saxena, Yu; FOCS 2020] rules out sublinear-space algorithms withexponentially smaller $o(\log{(1/\epsilon)})$ passes for these problems.  One key ingredient of our proofs is a simple streaming XOR Lemma, a generichardness amplification result, that we prove: informally speaking, if a$p$-pass $s$-space streaming algorithm can only solve a decision problem withadvantage $\delta > 0$ over random guessing, then it cannot solve XOR of $\ell$independent copies of the problem with advantage much better than$\delta^{\ell}$. This result can be of independent interest and useful forother streaming lower bounds as well.

Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma