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 study the problem of estimating the number of edges in an $n$-vertexgraph, accessed via the Bipartite Independent Set query model introduced byBeame et al. (ITCS '18). In this model, each query returns a Boolean,indicating the existence of at least one edge between two specified sets ofnodes. We present a non-adaptive algorithm that returns a $(1\pm \epsilon)$relative error approximation to the number of edges, with query complexity$\tilde O(\epsilon^{-5}\log^{5} n )$, where $\tilde O(\cdot)$ hides$\textrm{poly}(\log \log n)$ dependencies. This is the first non-adaptivealgorithm in this setting achieving $\textrm{poly}(1/\epsilon,\log n)$ querycomplexity. Prior work requires $\Omega(\log^2 n)$ rounds of adaptivity. Weavoid this by taking a fundamentally different approach, inspired by work onsingle-pass streaming algorithms. Moreover, for constant $\epsilon$, our querycomplexity significantly improves on the best known adaptive algorithm due toBhattacharya et al. (STACS '22), which requires $O(\epsilon^{-2} \log^{11} n)$queries. Building on our edge estimation result, we give the first non-adaptivealgorithm for outputting a nearly uniformly sampled edge with query complexity$\tilde O(\epsilon^{-6} \log^{6} n)$, improving on the works of Dell et al.(SODA '20) and Bhattacharya et al. (STACS '22), which require $\Omega(\log^3n)$ rounds of adaptivity. Finally, as a consequence of our edge samplingalgorithm, we obtain a $\tilde O(n\log^ 8 n)$ query algorithm for connectivity,using two rounds of adaptivity. This improves on a three-round algorithm ofAssadi et al. (ESA '21) and is tight; there is no non-adaptive algorithm forconnectivity making $o(n^2)$ queries.

Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries