Sparse reconstruction for iid variables
Pál Galicza (Budapest)
Abstract: For a sequence of Boolean functions $f_n : \{-1,1\}^{V_n} \longrightarrow \{-1,1\}$, defined on increasing configuration spaces of random inputs, we say that there is sparse reconstruction if there is a sequence of subsets $U_n \subseteq V_n$ of the coordinates satisfying $|U_n| = o(|V_n|)$ such that knowing the coordinates in $U_n$ gives us a non-vanishing amount of information about the value of $f_n$.
We first show that, if the underlying measure is a product measure, then no sparse reconstruction is possible for any sequence of transitive functions. We discuss the question in different frameworks, measuring information content in $L^2$ and with entropy. We also highlight some interesting connections with cooperative game theory.
Using our results for transitive sequences of functions, we answer a question posed by Itai Benjamini and show that the left-right crossing event for critical planar percolation on the square lattice does not admit sparse reconstruction either. Joint work with Gábor Pete.
combinatorics
Audience: researchers in the topic
Series comments: This is the online combinatorics seminar at Warwick.
Organizers: | Jan Grebik, Oleg Pikhurko |
Curator: | Hong Liu* |
*contact for this listing |