论文标题
旋转系统中的稀疏重建I：IID旋转
Sparse reconstruction in spin systems I: iid spins
论文作者
论文摘要
对于一系列布尔函数$ f_n：\ { - 1,1 \}^{v_n} \ longrightArrow \ { - 1,1 \} $，在随机输入的增加配置空间上定义，我们说如果有一个$ u_n $ u_n $ seeeq v_n $ u_n \ subsition $ u_n \ subsition $ u_n \ subsition $ u_n \ seeeq v_ s $ $ | u_n | = o（| v_n |）$，使得了解$ u_n $中的坐标为我们提供了有关$ f_n $的值的不变信息。 我们首先表明，如果基础度量是一种产品度量，那么任何一系列及物函数序列都不可能进行稀疏重建。我们在不同的框架中讨论了这个问题，以$ l^2 $和熵来测量信息内容。我们还强调了与合作游戏理论的一些有趣的联系。除了传递函数之外，我们还表明，在平方晶格上进行关键平面渗透的左右越野事件也不承认稀疏的重建。其中一些结果回答了Itai Benjamini提出的问题。
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. Beyond transitive functions, we show that the left-right crossing event for critical planar percolation on the square lattice does not admit sparse reconstruction either. Some of these results answer questions posed by Itai Benjamini.
