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

There is a trivial $O(\frac{n^3}{T})$ time algorithm for approximate trianglecounting where $T$ is the number of triangles in the graph and $n$ the numberof vertices. At the same time, one may count triangles exactly using fastmatrix multiplication in time $\tilde{O}(n^\omega)$. Is it possible to get anegative dependency on the number of triangles $T$ while retaining the$n^\omega$ dependency on $n$? We answer this question positively by providingan algorithm which runs in time $O\big(\frac{n^\omega}{T^{\omega - 2}}\big)\cdot \text{poly}(n^{o(1)}/\epsilon)$. This is optimal in the sense that aslong as the exponent of $T$ is independent of $n, T$, it cannot be improvedwhile retaining the dependency on $n$; this as follows from the lower bound ofEden and Rosenbaum [APPROX/RANDOM 2018]. Our algorithm improves upon the stateof the art when $T = \omega(1)$ and $T = o(n)$.  We also consider the problem of approximate triangle counting in sparsegraphs, parameterizing by the number of edges $m$. The best known algorithmruns in time $\tilde{O}\big(\frac{m^{3/2}}{T}\big)$ [Eden et al., SIAM Journalon Computing, 2017]. There is also a well known algorithm for exact trianglecounting that runs in time $\tilde{O}(m^{2\omega/(\omega + 1)})$. We again getan algorithm that retains the exponent of $m$ while running faster on graphswith larger number of triangles. Specifically, our algorithm runs in time$O\Big(\frac{m^{2\omega/(\omega+1)}}{ T^{2(\omega-1)/(\omega+1)}}\Big) \cdot\text{poly}(n^{o(1)}/\epsilon)$. This is again optimal in the sense that if theexponent of $T$ is to be constant, it cannot be improved without worsening thedependency on $m$. This algorithm improves upon the state of the art when $T =\omega(1)$ and $T = o(\sqrt{m})$.

Approximate Triangle Counting via Sampling and Fast Matrix Multiplication