Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Graph
Search

fr|en

Se Connecter

Concept

Complexité de la communication

Résumé

La complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique. Le dispositif abstrait classique est le suivant : Alice et Bob ont chacun un message, et ils veulent calculer un nouveau message à partir de leurs messages, en se transmettant un minimum d'information. Par exemple, Alice et Bob reçoivent un mot chacun, et ils doivent décider s'ils ont reçu le même mot ; ils peuvent bien sûr s'envoyer leur mot l'un à l'autre et comparer, mais la question est de minimiser le nombre de messages. Utiliser une ressources en communication est le fait d'envoyer une information à l'autre. Alice peut ainsi envoyer la première lettre de son mot à bob, ceci a un coût de 1. La théorie de la complexité de communication a donc pour but de calculer quelles sont les ressources en communication nécessaires pour effectuer certaines tâches dans un contexte de calcul distribué. Contrairement à la théorie de la complexité classique, on ne compte pas les res

Source officielle

https://fr.wikipedia.org/wiki/Complexit%C3%A9_de_la_communication

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (19)

Publications associées

Chargement

Personnes associées (1)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés (3)

Concepts associés

Chargement

Cours associés (5)

Cours associés

Chargement

Séances de cours associées (6)

Séances de cours associées

Chargement

Unambiguous DNFs and Alon-Saks-Seymour

Mika Tapani Göös, Siddhartha Jain

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which asks: How large a gap can there be between the chromatic number of a graph and its biclique partition number? Our result is also known to imply several other improved separations in query and communication complexity.

IEEE COMPUTER SOC2022

Chargement

This paper presents the first probabilistic Byzantine Agreement algorithm whose communication and time complexities are poly-logarithmic. So far, the most effective probabilistic Byzantine Agreement algorithm had communication complexity and time complexity. Our algorithm is based on a novel, unbalanced, almost everywhere to everywhere Agreement protocol which is interesting in its own right.

2013

Chargement

Additive Combinatorics and Discrete Logarithm Based Range Protocols

Rafik Chaabouni, Helger Lipmaa

We show how to express an arbitrary integer interval

I = [0, H]

as a sumset

I = \sum_{i=1}^\ell G_i * [0, u - 1] + [0, H']

of smaller integer intervals for some small values

\ell

u

, and

H' < u - 1

, where

b * A = \{b a : a \in A\}

and

A + B = \{a + b : a \in A \wedge b \in B\}

. We show how to derive such expression of

I

as a sumset for any value of

1 < u < H

, and in particular, how the coefficients

G_i

can be found by using a nontrivial but efficient algorithm. This result may be interesting by itself in the context of additive combinatorics. Given the sumset-representation of

I

, we show how to decrease both the communication complexity and the computational complexity of the recent pairing-based range proof of Camenisch, Chaabouni and shelat from ASIACRYPT 2008 by a factor of

2

. Our results are important in applications like e-voting where a voting server has to verify thousands of proofs of e-vote correctness per hour. Therefore, our new result in additive combinatorics has direct relevance in practice.

Springer2010

Chargement

Additive Combinatorics and Discrete Logarithm Based Range Protocols

Rafik Chaabouni, Helger Lipmaa

We show how to express an arbitrary integer interval

I = [0, H]

as a sumset

I = \sum_{i=1}^\ell G_i * [0, u - 1] + [0, H']

of smaller integer intervals for some small values

\ell

u

, and

H' < u - 1

, where

b * A = \{b a : a \in A\}

and

A + B = \{a + b : a \in A \wedge b \in B\}

. We show how to derive such expression of

I

as a sumset for any value of

1 < u < H

, and in particular, how the coefficients

G_i

can be found by using a nontrivial but efficient algorithm. This result may be interesting by itself in the context of additive combinatorics. Given the sumset-representation of

I

2

Springer2010