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

For "large" class $\mathcal{C}$ of continuous probability density functions(p.d.f.), we demonstrate that for every $w\in\mathcal{C}$ there is mixture ofdiscrete Binomial distributions (MDBD) with $T\geq N\sqrt{\phi_{w}/\delta}$distinct Binomial distributions $B(\cdot,N)$ that $\delta$-approximates adiscretized p.d.f. $\widehat{w}(i/N)\triangleqw(i/N)/[\sum_{\ell=0}^{N}w(\ell/N)]$ for all $i\in[3:N-3]$, where$\phi_{w}\geq\max_{x\in[0,1]}|w(x)|$. Also, we give two efficient parallelalgorithms to find such MDBD.  Moreover, we propose a sequential algorithm that on input MDBD with $N=2^k$for $k\in\mathbb{N}_{+}$ that induces a discretized p.d.f. $\beta$, $B=D-M$that is either Laplacian or SDDM matrix and parameter $\epsilon\in(0,1)$,outputs in $\widehat{O}(\epsilon^{-2}m + \epsilon^{-4}nT)$ time a spectralsparsifier $D-\widehat{M}_{N} \approx_{\epsilon}D-D\sum_{i=0}^{N}\beta_{i}(D^{-1} M)^i$ of a matrix-polynomial, where$\widehat{O}(\cdot)$ notation hides $\mathrm{poly}(\log n,\log N)$ factors.This improves the Cheng et al.'s [CCLPT15] algorithm whose run time is$\widehat{O}(\epsilon^{-2} m N^2 + NT)$.  Furthermore, our algorithm is parallelizable and runs in work$\widehat{O}(\epsilon^{-2}m + \epsilon^{-4}nT)$ and depth $O(\logN\cdot\mathrm{poly}(\log n)+\log T)$. Our main algorithmic contribution is topropose the first efficient parallel algorithm that on input continuous p.d.f.$w\in\mathcal{C}$, matrix $B=D-M$ as above, outputs a spectral sparsifier ofmatrix-polynomial whose coefficients approximate component-wise the discretizedp.d.f. $\widehat{w}$.  Our results yield the first efficient and parallel algorithm that runs innearly linear work and poly-logarithmic depth and analyzes the long termbehaviour of Markov chains in non-trivial settings. In addition, we strengthenthe Spielman and Peng's [PS14] parallel SDD solver.

An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials