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

A recent model for property testing of probability distributions (Chakrabortyet al., ITCS 2013, Canonne et al., SICOMP 2015) enables tremendous savings inthe sample complexity of testing algorithms, by allowing them to condition thesampling on subsets of the domain. In particular, Canonne, Ron, and Servedio(SICOMP 2015) showed that, in this setting, testing identity of an unknowndistribution $D$ (whether $D=D^\ast$ for an explicitly known $D^\ast$) can bedone with a constant number of queries, independent of the support size $n$ --in contrast to the required $\Omega(\sqrt{n})$ in the standard sampling model.It was unclear whether the same stark contrast exists for the case of testingequivalence, where both distributions are unknown. While Canonne et al.established a $\mathrm{poly}(\log n)$-query upper bound for equivalencetesting, very recently brought down to $\tilde O(\log\log n)$ by Falahatgar etal. (COLT 2015), whether a dependence on the domain size $n$ is necessary wasstill open, and explicitly posed by Fischer at the Bertinoro Workshop onSublinear Algorithms (2014). We show that any testing algorithm for equivalencemust make $\Omega(\sqrt{\log\log n})$ queries in the conditional samplingmodel. This demonstrates a gap between identity and equivalence testing, absentin the standard sampling model (where both problems have sampling complexity$n^{\Theta(1)}$).  We also obtain results on the query complexity of uniformity testing andsupport-size estimation with conditional samples. We answer a question ofChakraborty et al. (ITCS 2013) showing that non-adaptive uniformity testingindeed requires $\Omega(\log n)$ queries in the conditional model. For therelated problem of support-size estimation, we provide both adaptive andnon-adaptive algorithms, with query complexities $\mathrm{poly}(\log\log n)$and $\mathrm{poly}(\log n)$, respectively.

A Chasm Between Identity and Equivalence Testing with Conditional Queries