Mathematics – Combinatorics
Scientific paper
2005-12-29
Mathematics
Combinatorics
Scientific paper
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(\frac{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
Falik Dvir
Samorodnitsky Alex
No associations
LandOfFree
Edge-isoperimetric inequalities and influences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Edge-isoperimetric inequalities and influences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Edge-isoperimetric inequalities and influences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-701110