Name
Abstract | ||
|---|---|---|
. The sensitivity of a point is dist, i.e. the number of neighbors of the point in the discrete cube on which the value of differs. The average sensitivity of is the average of the sensitivity of all points in . (This can also be interpreted as the sum of the influences of the variables on , or as a measure of the edge boundary of the set which is the characteristic function of.) We show here that if the average sensitivity of is then can be approximated by a function depending on coordinates where is a constant depending only on the accuracy of the approximation but not on . We also present a more general version of this theorem, where the sensitivity is measured with respect to a product measure
which is not the uniform measure on the cube.
|
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/PL00009809 | Combinatorica |
Keywords | Field | DocType |
boolean function,characteristic function,functional dependency | Boolean network,Boolean function,Discrete mathematics,Combinatorics,Complexity index,Boolean expression,Mathematics | Journal |
Volume | Issue | ISSN |
18 | 1 | 0209-9683 |
Citations | PageRank | References |
47 | 4.02 | 2 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ehud Friedgut | 1 | 440 | 38.93 |