|| Binary Maximal Correlation Bounds and Isoperimetric Inequalities via Anti-Concentration
||Dror Drach, Tel Aviv University, Israel; Or Ordentlich, Hebrew University of Jerusalem, Israel; Ofer Shayevitz, Tel Aviv University, Israel|
||D3-S5-T1: Topics in Shannon Theory
||Wednesday, 14 July, 23:20 - 23:40
||Wednesday, 14 July, 23:40 - 00:00
This paper establishes a dimension-independent upper bound on the maximal correlation between Boolean functions of dependent random variables, in terms of the second and third singular values in their spectral decomposition, and the anti-concentration properties of the second singular vectors. This result has notable consequences, among which are: A strengthening of Witsenhausen's lower bound on the probability of disagreement between Boolean functions; a Poincar\'e inequality for bounded-cardinality functions; and improved lower bounds on the isoperimetric constant of Markov chains.