Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-012 | 20th November 2007 00:00

A Note on the Distance to Monotonicity of Boolean Functions

RSS-Feed




TR08-012
Authors: Arnab Bhattacharyya
Publication: 25th February 2008 17:56
Downloads: 3562
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint