BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Decoding from Pooled Data: Information-Theoretic bounds and a Mess
 age-Passing Algorithm - Ahmed El Alaoui (UC Berkeley)
DTSTART:20170616T150000Z
DTEND:20170616T160000Z
UID:TALK72033@talks.cam.ac.uk
CONTACT:Quentin Berthet
DESCRIPTION:Consider a population consisting of n individuals\, each of wh
 om has one of d types (e.g. their blood type\, in which case d=4). \nWe ar
 e allowed to query this database by specifying a subset of the population\
 , and in response we observe a noiseless histogram \n(a d-dimensional vect
 or of counts) of types of the pooled individuals. \nThis measurement model
  arises in practical situations such as pooling of genetic data and may al
 so be motivated by privacy considerations. \nWe study this model in  the "
 random dense" setting where each query involves a random subset of individ
 uals of size proportional to n.  \nWe are interested in the number of quer
 ies one needs to unambiguously determine the type of each individual\, \nb
 oth information-theoretically and in an algorithmically efficient way. \nW
 e discuss the information-theoretic question and present a message-passing
  algorithm for recovering the signal from a minimal \nnumber of measuremen
 ts and characterize its exact asymptotic behavior. \nThe analysis reveals 
 a gap between what is statistically possible and what is achieved by our a
 lgorithm. \n\nThis is joint work with Aaditya Ramdas\, Florent Krzakala\, 
 Lenka Zdeborova\, and Michael Jordan.\nPreprints: arxiv:1611.09981\, arxiv
 :1702.02279
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge.
END:VEVENT
END:VCALENDAR