کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428578 | 686825 | 2012 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Exponential lower bound for bounded depth circuits with few threshold gates
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We prove an exponential lower bound on the size of bounded depth circuits with O(logn) threshold gates computing an explicit function (namely, the parity function).Previously exponential lower bounds were known only for circuits with one threshold gate. Superpolynomial lower bounds are known for circuits with O(log2n) threshold gates.
► We study bounded depth circuits with small number of threshold gates.
► We are interested in exponential lower bounds on the size of such circuits.
► We prove a lower bound for circuits with O(logn) threshold gates computing parity.
► Previously such lower bounds were known only for circuits with one threshold gate.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 112, Issue 7, 31 March 2012, Pages 267–271
Journal: Information Processing Letters - Volume 112, Issue 7, 31 March 2012, Pages 267–271
نویسندگان
Vladimir V. Podolskii,