BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Statistics
SUMMARY:Decoding from Pooled Data: Information-Theoretic b
ounds and a Message-Passing Algorithm - Ahmed El A
laoui (UC Berkeley)
DTSTART;TZID=Europe/London:20170616T160000
DTEND;TZID=Europe/London:20170616T170000
UID:TALK72033AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/72033
DESCRIPTION:Consider a population consisting of n individuals\
, each of whom has one of d types (e.g. their bloo
d type\, in which case d=4). \nWe are allowed to q
uery this database by specifying a subset of the p
opulation\, and in response we observe a noiseless
histogram \n(a d-dimensional vector of counts) of
types of the pooled individuals. \nThis measureme
nt model arises in practical situations such as po
oling of genetic data and may also be motivated by
privacy considerations. \nWe study this model in
the "random dense" setting where each query invol
ves a random subset of individuals of size proport
ional to n. \nWe are interested in the number of
queries one needs to unambiguously determine the t
ype of each individual\, \nboth information-theore
tically and in an algorithmically efficient way. \
nWe discuss the information-theoretic question and
present a message-passing algorithm for recoverin
g the signal from a minimal \nnumber of measuremen
ts and characterize its exact asymptotic behavior.
\nThe analysis reveals a gap between what is stat
istically possible and what is achieved by our alg
orithm. \n\nThis is joint work with Aaditya Ramdas
\, Florent Krzakala\, Lenka Zdeborova\, and Michae
l Jordan.\nPreprints: arxiv:1611.09981\, arxiv:170
2.02279
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge.
CONTACT:Quentin Berthet
END:VEVENT
END:VCALENDAR