Higher lower bounds on monotone size
Danny Harnik, Ran Raz · 2000
We prove a lower bound of 2fl((~)~) onthemonotone size of an explicit function in monotone-Af:P (where n is the number of input variables).This is higher than any previous lower bound on the monotone size of a function.The previous best being a lower bound of about 2 ~('~¼) for Andreev's function, proved in [A1Bo87].Our lower bound is proved by the symmetric version of Razborov's method of approximations.However, we present this method in a new and simpler way: Rather than building approximator functions for all the gates in a circuit, we use a gate elimination argument that is based on a Monotone Switching Lemma.The bound applies for a family of functions, each defined by a construction of a small probability space of c-wise independent random variables.