Testing shape restriction properties of probability distributions in a unified way

Autor: Gouleakis, Themistoklis

Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.
Title as it appears in MIT Commencement Exercises program, June 5, 2015: Testing and correcting probability distributions. Cata

Externí odkaz: http://hdl.handle.net/1721.1/99864

Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation

Autor: Aliakbarpour, Maryam, Biswas, Amartya Shankha, Gouleakis, Themistoklis, Peebles, John, Rubinfeld, Ronitt, Yodpinyanee, Anak

We study the problem of estimating the value of sums of the form $S_p \triangleq \sum \binom{x_i}{p}$ when one has the ability to sample $x_i \geq 0$ with probability proportional to its magnitude. When $p=2$, this problem is equivalent to estimating

Externí odkaz: http://arxiv.org/abs/1601.04233

Testing Shape Restrictions of Discrete Distributions

Autor: Canonne, Clément L., Diakonikolas, Ilias, Gouleakis, Themis, Rubinfeld, Ronitt

Publikováno v: Canonne, C L, Diakonikolas, I, Gouleakis, T & Rubinfeld, R 2016, Testing Shape Restrictions of Discrete Distributions . in Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016) ., 25, Leibniz International Proceedings in Informatics (LIPIcs), vol. 47, pp. 1-14, 33rd International Symposium on Theoretical Aspects of Computer Science, Orléans, France, 17/02/16 . https://doi.org/10.4230/LIPIcs.STACS.2016.25
Dagstuhl Publishing

We study the question of testing structured properties (classes) of discrete distributions. Specifically, given sample access to an arbitrary distribution $D$ over $[n]$ and a property $\mathcal{P}$, the goal is to distinguish between $D\in\mathcal{P

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c48fc6df142a2c4c5ea9e6e451332410
https://www.pure.ed.ac.uk/ws/files/25120469/26.pdf