ﻻ يوجد ملخص باللغة العربية
We propose a new setting for testing properties of distributions while receiving samples from several distributions, but few samples per distribution. Given samples from $s$ distributions, $p_1, p_2, ldots, p_s$, we design testers for the following problems: (1) Uniformity Testing: Testing whether all the $p_i$s are uniform or $epsilon$-far from being uniform in $ell_1$-distance (2) Identity Testing: Testing whether all the $p_i$s are equal to an explicitly given distribution $q$ or $epsilon$-far from $q$ in $ell_1$-distance, and (3) Closeness Testing: Testing whether all the $p_i$s are equal to a distribution $q$ which we have sample access to, or $epsilon$-far from $q$ in $ell_1$-distance. By assuming an additional natural condition about the source distributions, we provide sample optimal testers for all of these problems.
In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution $p$ over a poset is monotone if, for any pair of domain elements $x$ and $y$ such that $x preceq y$, $p(x) leq
In graph property testing the task is to distinguish whether a graph satisfies a given property or is far from having that property, preferably with a sublinear query and time complexity. In this work we initiate the study of property testing in sign
It is known that testing isomorphism of chordal graphs is as hard as the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a tree. The leafage of a chordal graph, is defined to be
We study the problem of testing identity against a given distribution with a focus on the high confidence regime. More precisely, given samples from an unknown distribution $p$ over $n$ elements, an explicitly given distribution $q$, and parameters $
It was shown recently by Fakcharoenphol et al that arbitrary finite metrics can be embedded into distributions over tree metrics with distortion O(log n). It is also known that this bound is tight since there are expander graphs which cannot be embed