Academic Journal
Higher Lower Bounds On Monotone Size
| العنوان: | Higher Lower Bounds On Monotone Size |
|---|---|
| المؤلفون: | Danny Harnik, Ran Raz |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://www.wisdom.weizmann.ac.il/~ranraz/./publications/Pdani.ps. |
| سنة النشر: | 2000 |
| المجموعة: | CiteSeerX |
| الوصف: | We prove a lower bound of 2\Omega i ( n log n ) 1 3 j 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 \Omega\Gamma 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. 1 Introduction 1.1 Background and Previous Work A monotone function is one that can be computed by a monotone circuit i.e., a circuit with only AND and OR gates. The monoton. |
| نوع الوثيقة: | text |
| وصف الملف: | application/postscript |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.8241; http://www.wisdom.weizmann.ac.il/~ranraz/./publications/Pdani.ps |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.8241 http://www.wisdom.weizmann.ac.il/~ranraz/./publications/Pdani.ps |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.9AF151CD |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |