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 present an algorithm for recovering planted solutions in two well-knownmodels, the stochastic block model and planted constraint satisfactionproblems, via a common generalization in terms of random bipartite graphs. Ouralgorithm matches up to a constant factor the best-known bounds for the numberof edges (or constraints) needed for perfect recovery and its running time islinear in the number of edges used. The time complexity is significantly betterthan both spectral and SDP-based approaches.  The main contribution of the algorithm is in the case of unequal sizes in thebipartition (corresponding to odd uniformity in the CSP). Here our algorithmsucceeds at a significantly lower density than the spectral approaches,surpassing a barrier based on the spectral norm of a random matrix.  Other significant features of the algorithm and analysis include (i) thecritical use of power iteration with subsampling, which might be of independentinterest; its analysis requires keeping track of multiple norms of an evolvingsolution (ii) it can be implemented statistically, i.e., with very limitedaccess to the input distribution (iii) the algorithm is extremely simple toimplement and runs in linear time, and thus is practical even for very largeinstances.

Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's