Support Size Estimation: The Power of Conditioning

Please use this identifier to cite or link to this item: https://doi.org/10.4230/LIPIcs.MFCS.2023.33

DC Field	Value
dc.title	Support Size Estimation: The Power of Conditioning
dc.contributor.author	Chakraborty, D
dc.contributor.author	Kumar, G
dc.contributor.author	Meel, KS
dc.date.accessioned	2024-04-01T01:05:31Z
dc.date.available	2024-04-01T01:05:31Z
dc.date.issued	2023-08-01
dc.identifier.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
dc.identifier.isbn	9783959772921
dc.identifier.issn	1868-8969
dc.identifier.uri	https://scholarbank.nus.edu.sg/handle/10635/247658
dc.description.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.
dc.source	Elements
dc.type	Conference Paper
dc.date.updated	2024-03-28T06:40:16Z
dc.contributor.department	DEPARTMENT OF COMPUTER SCIENCE
dc.contributor.department	DEPARTMENT OF COMPUTER SCIENCE
dc.description.doi	10.4230/LIPIcs.MFCS.2023.33
dc.description.volume	272
dc.published.state	Published
Appears in Collections:	Staff Publications Elements

File	Description	Size	Format	Access Settings	Version
2211.11967.pdf	Supporting information	505.79 kB	Adobe PDF	OPEN	None	View/Download

Check