کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653413 | 1632770 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fooling-sets and rank
ترجمه فارسی عنوان
فریب مجموعه و رتبه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
An n×nn×n matrix MM is called a fooling-set matrix of size nn if its diagonal entries are nonzero and Mk,ℓMℓ,k=0Mk,ℓMℓ,k=0 for every k≠ℓk≠ℓ. Dietzfelbinger, Hromkovič, and Schnitger (1996) showed that n≤(rkM)2n≤(rkM)2, regardless of over which field the rank is computed, and asked whether the exponent on rkMrkM can be improved.We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size n=(rkM+12). In nonzero characteristic, we construct an infinite family of matrices with n=(1+o(1))(rkM)2n=(1+o(1))(rkM)2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 48, August 2015, Pages 143–153
Journal: European Journal of Combinatorics - Volume 48, August 2015, Pages 143–153
نویسندگان
Mirjam Friesen, Aya Hamed, Troy Lee, Dirk Oliver Theis,