Lower Bounds in Communication Complexity: A Survey

دسته بندی: الگوریتم ها و ساختارهای داده
ویرایش:  
نویسندگان: Lee T.,  Shraibman A.  
سری:  
 
ناشر:  
سال نشر:  
تعداد صفحات: 127 
زبان: English 
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 943 کیلوبایت 

قیمت کتاب (تومان) : 28,000

Из серии مبانی و روندها در علوم کامپیوتر نظری издательства NOWPress, 2009, -127 pp. ما مرزهای پایین تری را در پیچیدگی ارتباطات بررسی می کنیم. تمرکز ما بر روی مرزهای پایین تر است که ابتدا با نمایش معیار پیچیدگی ارتباط در فضای اقلیدسی کار می کنند. به عبارت دیگر، اولین گام در این تکنیک‌های کران پایین، یافتن یک معیار پیچیدگی هندسی مانند رتبه، یا هنجار ردیابی است که به عنوان کران پایینی برای اندازه‌گیری پیچیدگی ارتباطات زیربنایی عمل می‌کند. سپس با استفاده از ابزارهای جبری و هندسی، مرزهای پایین‌تر در این اندازه‌گیری پیچیدگی هندسی یافت می‌شود.
پیچیدگی ارتباطات به منظور ارزیابی عملکردی که خروجی آن به اطلاعات توزیع شده بین دو یا چند طرف بستگی دارد، میزان ارتباط مورد نیاز را مطالعه می‌کند. یائو یک چارچوب ریاضی ظریف را برای مطالعه پیچیدگی ارتباطات معرفی کرد که در موقعیت‌های متعدد، از مکالمه ایمیل بین دو نفر گرفته تا پردازشگرهایی که روی یک تراشه ارتباط برقرار می‌کنند، قابل استفاده است. در واقع، کاربرد پیچیدگی ارتباطات در سایر زمینه‌ها، از جمله پیچیدگی مدار و فرمول، طراحی VLSI، پیچیدگی اثبات، و الگوریتم‌های جریان، یکی از دلایلی است که باعث شده تا این همه مطالعه را به خود جلب کند. برای جزئیات بیشتر در مورد این کاربردها و پیچیدگی ارتباطات به طور کلی به کتاب عالی کوشیلویتز و نیسان مراجعه کنید.
یکی دیگر از دلایل اینکه پیچیدگی ارتباطات یک مدل محبوب برای مطالعه است، این است که این مدل ریاضی جالب است. علاوه بر این، آن ترکیب نادری را در نظریه پیچیدگی مدلی دارد که در واقع می‌توانیم امیدوار باشیم که مرزهای پایینی محکمی برای آن نشان دهیم، با این حال این محدوده‌ها اغلب نیاز به توسعه تکنیک‌های بی‌اهمیت دارند و گاهی تنها پس از چندین سال تلاش مداوم به دست می‌آیند. مقدمه
پیچیدگی ارتباط قطعی
پیچیدگی ارتباط غیرقطعی
پیچیدگی ارتباط تصادفی
پیچیدگی ارتباط کوانتومی
نقش دوگانگی در اثبات مرزهای پایین
انتخاب شاهد
پیچیدگی ارتباطات چند جانبه
مرزهای بالایی در پیچیدگی ارتباطات چند جانبه

Из серии Foundations and Trends in Theoretical Computer Science издательства NOWPress, 2009, -127 pp. We survey lower bounds in communication complexity. Our focus is on lower bounds that work by first representing the communication complexity measure in Euclidean space. That is to say, the first step in these lower bound techniques is to find a geometric complexity measure such as rank, or the trace norm that serves as a lower bound to the underlying communication complexity measure. Lower bounds on this geometric complexity measure are then found using algebraic and geometric tools.
Communication complexity studies how much communication is needed in order to evaluate a function whose output depends on information distributed amongst two or more parties. Yao introduced an elegant mathematical framework for the study of communication complexity, applicable in numerous situations, from an email conversation between two people, to processors communicating on a chip. Indeed, the applicability of communication complexity to other areas, including circuit and formula complexity, VLSI design, proof complexity, and streaming algorithms, is one reason why it has attracted so much study. See the excellent book of Kushilevitz and Nisan for more details on these applications and communication complexity in general.
Another reason why communication complexity is a popular model for study is simply that it is an interesting mathematical model. Moreover, it has that rare combination in complexity theory of a model for which we can actually hope to show tight lower bounds, yet these bounds often require the development of nontrivial techniques and sometimes are only obtained after several years of sustained effort. Introduction
Deterministic communication complexity
Nondeterministic communication complexity
Randomized communication complexity
Quantum communication complexity
The role of duality in proving lower bounds
Choosing a witness
Multiparty communication complexity
Upper bounds on multiparty communication complexity