Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-163 | 19th December 2005 00:00

Edge-isoperimetric inequalities and influences

RSS-Feed




TR05-163
Authors: Dvir Falik, Alex Samorodnitsky
Publication: 23rd December 2005 20:03
Downloads: 3341
Keywords: 


Abstract:

We give a combinatorial proof of the result of Kahn, Kalai, and Linial, which states that every balanced boolean function on the n-dimensional boolean cube has a variable with influence of at least Omega(log(n)/n).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 and discuss their possible implications.



ISSN 1433-8092 | Imprint