Reproduce “Support Size Estimation: The Power of Conditioning” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Diptarka Chakraborty, Gunjan Kumar, Kuldeep S. Meel
Researchers at the National University of Singapore developed a novel framework combining information theory and communication complexity to establish tighter lower bounds for support size estimation in conditional sampling models. This work nearly closes a long-standing gap for the COND-PR model by providing an Ω(log log n + 1/ε^2 log(1/ε)) lower bound and presents the first non-trivial Ω(log log log n) lower bound for the more powerful COND-EVAL model.
Key insights
- Information theory and communication complexity provide a robust and powerful analytical toolkit for proving lower bounds in adaptive conditional sampling models, going beyond prior decision tree-based methods.
- Revealing probabilities (COND-PR) offers only marginal additional power for multiplicative support size estimation compared to basic conditional sampling (COND), as their lower bounds are nearly identical.
- More powerful conditional models, particularly COND-EVAL, exhibit significantly reduced query complexity for various distribution testing problems (e.g., equivalence testing, L2 norm estimation) compared to weaker conditional models or standard sampling.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.