Conditional Sampling for Distribution Testing
summary
Shows that access to conditional samples yields testers whose query complexity is poly(1/ε) testers and largely domain-size independent, giving algorithms for uniformity, identity, and closeness with exponentially fewer samples than classical sampling. Constructs explicit adaptive and nonadaptive procedures using bucketing, random partitioning and simulators for conditional oracles, and proves matching lower bounds for several problems. Demonstrates worked implementations on synthetic distributions and reports concrete constants and sample counts that beat standard bounds.
AI-written summary · about