ECCC-Report TR08-012https://eccc.weizmann.ac.il/report/2008/012Comments and Revisions published for TR08-012en-usMon, 25 Feb 2008 17:56:13 +0200
Paper TR08-012
| A Note on the Distance to Monotonicity of Boolean Functions |
Arnab Bhattacharyya
https://eccc.weizmann.ac.il/report/2008/012Given a boolean function, let epsilon_M(f) denote the smallest distance between f and a monotone function on {0,1}^n. Let delta_M(f) denote the fraction of hypercube edges where f violates monotonicity. We give an alternative proof of the tight bound: delta_M(f) >= 2/n eps_M(f) for any boolean function f. This was already shown by Raskhodnikova earlier.
Mon, 25 Feb 2008 17:56:13 +0200https://eccc.weizmann.ac.il/report/2008/012