Publication View

The Influence of Variables on Boolean Functions (Extended Abstract) (2007)

Abstract

This paper applies methods from harmonic analysis to prove some general theorems on boolean functions. The result that is easiest to describe says that "Boolean functions always have small dominant sets of variables." The exact definitions will be given shortly, but let us be more specific: Let f be an n variable boolean function taking the value zero for half of the 2^n variable assignments. Then there is a set of o(n) variables such that almost surely the value of f is undetermined as long as these variables are not assigned values. This proves some of the conjectures made in [BL]. These new connections with...

Publication details

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.4105
Source	http://www.ma.huji.ac.il/~kalai/kkl.ps
Contributors	CiteSeerX
Repository	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Type	text
Language	English
Relation	10.1.1.24.2834, 10.1.1.1.8787, 10.1.1.101.8611, 10.1.1.53.5068, 10.1.1.28.9419, 10.1.1.3.7975, 10.1.1.29.1715, 10.1.1.32.629, 10.1.1.130.3650, 10.1.1.37.5552, 10.1.1.17.5345, 10.1.1.11.1195, 10.1.1.104.2928, 10.1.1.3.1753, 10.1.1.3.8684, 10.1.1.39.2422, 10.1.1.104.3928, 10.1.1.36.8615, 10.1.1.121.3854, 10.1.1.24.4264, 10.1.1.125.4125, 10.1.1.36.8392, 10.1.1.56.715, 10.1.1.125.837, 10.1.1.134.9651, 10.1.1.35.5658, 10.1.1.120.699, 10.1.1.10.1921, 10.1.1.105.6271, 10.1.1.74.1290, 10.1.1.137.9283, 10.1.1.32.8126, 10.1.1.123.5666, 10.1.1.24.6383, 10.1.1.122.535, 10.1.1.119.3118, 10.1.1.53.284, 10.1.1.125.2382, 10.1.1.4.4154, 10.1.1.8.7398, 10.1.1.5.2839, 10.1.1.51.1797, 10.1.1.129.9837, 10.1.1.37.2237, 10.1.1.39.1857, 10.1.1.17.9325, 10.1.1.34.2286, 10.1.1.133.7756, 10.1.1.102.7928, 10.1.1.53.6729, 10.1.1.50.2047, 10.1.1.115.8053, 10.1.1.7.1212, 10.1.1.132.2631, 10.1.1.113.7569, 10.1.1.110.9407, 10.1.1.42.3798, 10.1.1.107.4217, 10.1.1.25.2505, 10.1.1.32.5711, 10.1.1.101.4452, 10.1.1.94.4564, 10.1.1.132.5732, 10.1.1.103.4362, 10.1.1.103.5883, 10.1.1.104.4403, 10.1.1.96.6104, 10.1.1.40.2066, 10.1.1.6.5141, 10.1.1.63.8330, 10.1.1.124.2522, 10.1.1.63.9542, 10.1.1.66.8848, 10.1.1.69.2372, 10.1.1.71.8115, 10.1.1.73.7887, 10.1.1.75.3213, 10.1.1.75.3377, 10.1.1.137.2733, 10.1.1.75.9666, 10.1.1.76.5800, 10.1.1.77.2545, 10.1.1.79.3852, 10.1.1.124.3810, 10.1.1.85.7736, 10.1.1.104.8663, 10.1.1.87.2862, 10.1.1.90.8411, 10.1.1.91.2403, 10.1.1.92.3298, 10.1.1.93.8012, 10.1.1.94.8442, 10.1.1.97.8753, 10.1.1.97.8949, 10.1.1.98.1747, 10.1.1.98.6351, 10.1.1.110.4384, 10.1.1.110.6156, 10.1.1.111.2771, 10.1.1.112.3397, 10.1.1.115.5997, 10.1.1.118.143, 10.1.1.118.1601, 10.1.1.118.7438, 10.1.1.121.9498, 10.1.1.122.4932, 10.1.1.123.899, 10.1.1.135.3386, 10.1.1.125.334, 10.1.1.125.4890, 10.1.1.126.3195, 10.1.1.127.9917, 10.1.1.130.3256, 10.1.1.131.202, 10.1.1.133.2908, 10.1.1.134.2553, 10.1.1.134.3122, 10.1.1.134.4343, 10.1.1.135.1901, 10.1.1.135.6883, 10.1.1.135.7631, 10.1.1.137.2671, 10.1.1.137.8320, 10.1.1.34.7459, 10.1.1.44.4655, 10.1.1.44.4249, 10.1.1.39.3215, 10.1.1.41.233, 10.1.1.41.5232, 10.1.1.43.4359, 10.1.1.29.3718, 10.1.1.29.4345, 10.1.1.15.5858, 10.1.1.15.8642, 10.1.1.6.5088, 10.1.1.7.5597, 10.1.1.4.560, 10.1.1.4.1082