Sparse reconstruction for iid variables

Pál Galicza (Budapest)

15-Jan-2021, 14:00-15:00 (3 years ago)

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


Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.

Organizers: Jan Grebik, Oleg Pikhurko
Curator: Hong Liu*
*contact for this listing

Export talk to