Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > DVIR FALIK:
All reports by Author Dvir Falik:

TR05-163 | 19th December 2005
Dvir Falik, Alex Samorodnitsky

Edge-isoperimetric inequalities and influences

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 ... more >>>




ISSN 1433-8092 | Imprint