Please use this identifier to cite or link to this item:
https://doi.org/10.4230/LIPIcs.MFCS.2023.33
| Title: | Support Size Estimation: The Power of Conditioning | Authors: | Chakraborty, D Kumar, G Meel, KS |
Issue Date: | 1-Aug-2023 | Citation: | Chakraborty, D, Kumar, G, Meel, KS (2023-08-01). Support Size Estimation: The Power of Conditioning 272. ScholarBank@NUS Repository. https://doi.org/10.4230/LIPIcs.MFCS.2023.33 | Abstract: | We consider the problem of estimating the support size of a distribution D. Our investigations are pursued through the lens of distribution testing and seek to understand the power of conditional sampling (denoted as COND), wherein one is allowed to query the given distribution conditioned on an arbitrary subset S. The primary contribution of this work is to introduce a new approach to lower bounds for the COND model that relies on using powerful tools from information theory and communication complexity. | URI: | https://scholarbank.nus.edu.sg/handle/10635/247658 | ISBN: | 9783959772921 | ISSN: | 1868-8969 | DOI: | 10.4230/LIPIcs.MFCS.2023.33 |
| Appears in Collections: | Staff Publications Elements |
Show full item record
Files in This Item:
| File | Description | Size | Format | Access Settings | Version | |
|---|---|---|---|---|---|---|
| 2211.11967.pdf | Supporting information | 505.79 kB | Adobe PDF | OPEN | None | View/Download |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.