Displaying similar documents to “Construction of Very Hard Functions for Multiparty Communication Complexity”

One-way communication complexity of symmetric Boolean functions

Jan Arpe, Andreas Jakoby, Maciej Liśkiewicz (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in...

Communication Complexity And Linearly Ordered Sets

Mieczysław Kula, Małgorzata Serwecińska (2015)

Annales Mathematicae Silesianae

Similarity:

The paper is devoted to the communication complexity of lattice operations in linearly ordered finite sets. All well known techniques ([4, Chapter 1]) to determine the communication complexity of the infimum function in linear lattices disappoint, because a gap between the lower and upper bound is equal to O(log2 n), where n is the cardinality of the lattice. Therefore our aim will be to investigate the communication complexity of the function more carefully. We consider a family of...

One-way communication complexity of symmetric boolean functions

Jan Arpe, Andreas Jakoby, Maciej Liśkiewicz (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in any case...

The Communication Hierarchy of Time and Space Bounded Parallel Machines

Norbert Popély (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.

Scheduling an interval ordered precedence graph with communication delays and a limited number of processors

Alix Munier Kordon, Fadi Kacem, Benoît Dupont de Dinechin, Lucian Finta (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

We consider the scheduling of an interval order precedence graph of unit execution time tasks with communication delays, release dates and deadlines. Tasks must be executed by a set of processors partitioned into classes; each task requires one processor from a fixed class. The aim of this paper is to study the extension of the Leung–Palem–Pnueli (in short LPP) algorithm to this problem. The main result is to prove that the LPP algorithm can be extended to dedicated processors and monotone...

The communication hierarchy of time and space bounded parallel machines

Norbert Popély (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.