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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

A conditional sampling oracle for a probability distribution D returnssamples from the conditional distribution of D restricted to a specified subsetof the domain. A recent line of work (Chakraborty et al. 2013 and Cannone etal. 2014) has shown that having access to such a conditional sampling oraclerequires only polylogarithmic or even constant number of samples to solvedistribution testing problems like identity and uniformity. This significantlyimproves over the standard sampling model where polynomially many samples arenecessary.  Inspired by these results, we introduce a computational model based onconditional sampling to develop sublinear algorithms with exponentially fasterruntimes compared to standard sublinear algorithms. We focus on geometricoptimization problems over points in high dimensional Euclidean space. Accessto these points is provided via a conditional sampling oracle that takes asinput a succinct representation of a subset of the domain and outputs auniformly random point in that subset. We study two well studied problems:k-means clustering and estimating the weight of the minimum spanning tree. Incontrast to prior algorithms for the classic model, our algorithms have time,space and sample complexity that is polynomial in the dimension andpolylogarithmic in the number of points.  Finally, we comment on the applicability of the model and compare withexisting ones like streaming, parallel and distributed computational models.

Faster Sublinear Algorithms using Conditional Sampling