کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437950 | 690211 | 2009 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parameterized learnability of juntas
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We study the parameterized complexity of learning k-juntas and some variations of juntas. We show the hardness of learning k-juntas and subclasses of k-juntas in the PAC model by reductions from a -complete problem. On the other hand, as a consequence of a more general result, we show that k-juntas are exactly learnable with improper equivalence queries and access to a oracle.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 47–49, 6 November 2009, Pages 4928-4936
Journal: Theoretical Computer Science - Volume 410, Issues 47–49, 6 November 2009, Pages 4928-4936