All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD3-S5-T1.3
Paper Title Binary Maximal Correlation Bounds and Isoperimetric Inequalities via Anti-Concentration
Authors Dror Drach, Tel Aviv University, Israel; Or Ordentlich, Hebrew University of Jerusalem, Israel; Ofer Shayevitz, Tel Aviv University, Israel
Session D3-S5-T1: Topics in Shannon Theory
Chaired Session: Wednesday, 14 July, 23:20 - 23:40
Engagement Session: Wednesday, 14 July, 23:40 - 00:00
Abstract 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.