TY - GEN

T1 - Higher lower bounds on monotone size

AU - Harnik, Danny

AU - Raz, Ran

PY - 2000

Y1 - 2000

N2 - We prove a lower bound of 2Ω((n/log n)1/3) on the monotone size of an explicit function in monotone-NP (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 Ω(n 1/4) for Andreev's function, proved in [AlBo87]. 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.

AB - We prove a lower bound of 2Ω((n/log n)1/3) on the monotone size of an explicit function in monotone-NP (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 Ω(n 1/4) for Andreev's function, proved in [AlBo87]. 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.

UR - http://www.scopus.com/inward/record.url?scp=0033718007&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033718007&partnerID=8YFLogxK

U2 - 10.1145/335305.335349

DO - 10.1145/335305.335349

M3 - Conference contribution

AN - SCOPUS:0033718007

SN - 1581131844

SN - 9781581131840

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 378

EP - 387

BT - Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000

T2 - 32nd Annual ACM Symposium on Theory of Computing, STOC 2000

Y2 - 21 May 2000 through 23 May 2000

ER -