Կառուցվածքային արդյունքներ հաղորդակցման բարդության տեսությունում, մաս Ⅰ

Abstract: Հաղորդակցման բարդության տեսությունը բարդության տեսության ենթաբաժին է, որն ուսումնասիրում է Բուլյան ֆունկցիաների «բարդությունը» հետևյալ դրվածքում. ֆունկցիայի մուտքային բիթերը բաժանված են մի քանի կողմերի միջև, ում նպատակն է հաշվել ֆունկցիայի արժեքն այդ բիթերի վրա՝ հաղորդակցվելով ամենաքիչ քանակով բիթեր։ Այս զեկույցում կտրվի հաղորդակցման բարդության տեսության ներածություն և կքննարկվի նոր կառուվածքային արդյունքներ այն ֆունկցիաների համար, որոնք ունեն ցածր հաղորդակցման բարդություն։  Սա ներածական զեկույց է, և նախապես միայն պահանջվում է իմանալ թե ինչ է մատրիցը, մատրիցի կարգը և ինչ` նորմը։

Structural Results in Communication Complexity, part Ⅰ

Communication Complexity is a subfield of complexity theory that studies the “complexity” of Boolean functions in the following setting: the input is split amongst multiple parties, who want to compute the value of the function together while communicating to each other a minimum number of bits. In this talk, I will give an introduction to Communication Complexity and will discuss new structural results for Boolean functions having low communication complexity.  This is an introductory talk, no prior knowledge is necessary except knowing the notions of a matrix, matrix rank, and norm.

ArmenianMathematics

Audience: general audience

( slides )

---

Yerevan Mathematical Colloquium

Series comments: "Yerevan Mathematical Colloquium" invites survey talks aimed at a general mathematical audience, that emphasize proof methods, relations between branches of mathematics, possible applications, and open problems.

---