Edge-Isoperimetric Inequalities and Influences

Source abstract

We give a combinatorial proof of the result of Kahn, Kalai and Linial [16], which states that every balanced boolean function on the n -dimensional boolean cube has a variable with influence of at least $\Omega\bigl(\frac{\log n}{n}\bigr)$ . The methods of the proof are then used to recover additional isoperimetric results for the cube, with improved constants. We also state some conjectures about optimal constants.