کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874172 | 1441026 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The direct sum of universal relations
ترجمه فارسی عنوان
مجموع مستقیم روابط جهانی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we prove a direct sum theorem for the universal relation, namely, we prove that solving m independent instances of the universal relation is m times harder than solving a single instance. More specifically, it is known that the deterministic communication complexity of the universal relation is at least n. We prove that the deterministic communication complexity of solving m independent instances of the universal relation is at least mâ
(nâO(logâ¡m)).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 136, August 2018, Pages 105-111
Journal: Information Processing Letters - Volume 136, August 2018, Pages 105-111
نویسندگان
Or Meir,