| Meno: | František
|
|---|
| Priezvisko: | Ďuriš
|
|---|
| Názov: | Multiparty Communication Complexity
|
|---|
| Vedúci: | prof. RNDr. Pavol Ďuriš, CSc.
|
|---|
| Rok: | 2011
|
|---|
| Blok: | INF
|
|---|
| Kľúčové slová: | communication complexity, bounds, hard functions
|
|---|
| Abstrakt: | In 1979 Yao proposed a simple model for studying communication complexity. In the first chapter we investigate the lower bound methods for this model - Fooling set method and Rank method. We prove the bounds on the number of functions with given communication complexity that can be exposed be these two methods. We give new proof that most of the functions are hard.\\
In the second chapter we focus on the multiparty extension of Yao's model, more precisely on the "number in the hand" model. Inspired by previous results concerned with communication complexity bounds for functions linked together with logic operators we fill the bounds for missing operators.\\
In the third chapter we propose a modification of this multiparty model and prove some results pointing at differences between the original and the modified model.
|
|---|