skip to content

Department of Computer Science and Technology

Thursday, 16 January, 2020 - 11:00 to 12:00
Jasper Lee (Brown University)
Computer Laboratory, Room FW09

Given a mixture between two populations of coins: "positive" coins that have (unknown and potentially different) probabilities of heads at least 1/2+Δ and "negative" coins with probabilities at most 1/2-Δ, we consider the task of estimating the fraction ρ of coins of each type to within additive error ε, with a constant probability of success.

In this talk, we will focus on the construction of an algorithm with sample complexity O((ρ/ε²Δ²)(1+ρ log 1/ε)), which matches the fully-adaptive lower bound of Ω(ρ/ε²Δ²) shown in our paper, except for the regime where ρ = ω(1/log 1/ε).

The fine-grained adaptive flavour of both our algorithm and lower bound contrasts with much previous work in distributional testing and learning.

Joint work with Paul Valiant, available on arXiv at

Cambridge Algorithms talks

Upcoming seminars