BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Pál Galicza (Budapest)
DTSTART:20210115T140000Z
DTEND:20210115T150000Z
DTSTAMP:20260423T021050Z
UID:WCS/15
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/WCS/15/">Spa
 rse reconstruction for iid variables</a>\nby Pál Galicza (Budapest) as pa
 rt of Warwick Combinatorics Seminar\n\n\nAbstract\nFor a sequence of Boole
 an functions $f_n : \\{-1\,1\\}^{V_n} \\longrightarrow \\{-1\,1\\}$\, defi
 ned on increasing configuration spaces of random inputs\, we say that ther
 e is sparse reconstruction if there is a sequence of subsets $U_n \\subset
 eq V_n$ of the coordinates satisfying $|U_n| = o(|V_n|)$  such that knowin
 g the coordinates in $U_n$ gives us a non-vanishing amount of information 
 about the value of $f_n$.\n\nWe first show that\, if the underlying measur
 e is a product measure\, then no sparse reconstruction is possible for any
  sequence of transitive functions. We discuss the question in different fr
 ameworks\, measuring information content in $L^2$ and with entropy. We als
 o highlight some interesting connections with cooperative game theory.\n\n
 Using our results for transitive sequences of functions\,  we answer a que
 stion posed by Itai Benjamini and show that the left-right crossing event 
 for critical planar percolation on the square lattice does not admit spars
 e reconstruction either. Joint work with Gábor Pete.\n
LOCATION:https://researchseminars.org/talk/WCS/15/
END:VEVENT
END:VCALENDAR