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

The Sparsest Cut is a fundamental optimization problem that has beenextensively studied. For planar inputs the problem is in $P$ and can be solvedin $\tilde{O}(n^3)$ time if all vertex weights are $1$. Despite a significantamount of effort, the best algorithms date back to the early 90's and can onlyachieve $O(\log n)$-approximation in $\tilde{O}(n)$ time or a constant factorapproximation in $\tilde{O}(n^2)$ time [Rao, STOC92]. Our main result is an$\Omega(n^{2-\epsilon})$ lower bound for Sparsest Cut even in planar graphswith unit vertex weights, under the $(min,+)$-Convolution conjecture, showingthat approximations are inevitable in the near-linear time regime. Tocomplement the lower bound, we provide a constant factor approximation innear-linear time, improving upon the 25-year old result of Rao in both time andaccuracy.  Our lower bound accomplishes a repeatedly raised challenge by being the firstfine-grained lower bound for a natural planar graph problem in P. Moreover, weprove near-quadratic lower bounds under SETH for variants of the closest pairproblem in planar graphs, and use them to show that the popular Average-Linkageprocedure for Hierarchical Clustering cannot be simulated in truly subquadratictime.  We prove an $\Omega(n/\log{n})$ lower bound on the number of communicationrounds required to compute the weighted diameter of a network in the CONGESTmodel, even when the underlying graph is planar and all nodes are $D=4$ hopsaway from each other. This is the first poly($n$) + $\omega(D)$ lower bound inthe planar-distributed setting, and it complements the recent poly$(D,\log{n})$ upper bounds of Li and Parter [STOC 2019] for (exact) unweighteddiameter and for ($1+\epsilon$) approximate weighted diameter.

New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut