| Paper ID | D3-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.
|
