Concept

Complexité de la communication

Publications associées (157)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Silence-Based Communication

Christina Fragouli

Communication complexity---the minimum amount of communication required---of computing a function of data held by several parties is studied. A communication model where silence is used to convey information is introduced. For this model the worst-case and ...

2010

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 = ...

Springer2010

Fast Randomized Test-and-Set and Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh, Hagit Albo Attiya, Andrei Giurgiu

Most people believe that renaming is easy: simply choose a name \emph{at random}; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write ...

2010

Refined quorum systems

Rachid Guerraoui, Marko Vukolic

It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contenti ...

2010

Lumpability Abstractions of Rule-based Systems

Tatjana Petrov

The induction of a signaling pathway is characterized by transient complex formation and mutual posttranslational modification of proteins. To faithfully capture this combinatorial process in a mathematical model is an important challenge in systems biolog ...

2010

Collision Attacks against the Knudsen-Preneel Compression Functions

Martijn Stam, Onur Özen

Knudsen and Preneel (Asiacrypt'96 and Crypto'97) introduced a hash function design in which a linear error-correcting code is used to build a wide-pipe compression function from underlying blockciphers operating in Davies-Meyer mode. Their main design goal ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

Chasing the Weakest System Model for Implementing Omega and Consensus

Martin Hutle

Aguilera et al. and Malkhi et al. presented two system models, which are weaker than all previously proposed models where the eventual leader election oracle Omega can be implemented, and thus, consensus can also be solved. The former model assumes unicast ...

2009

Performance Analysis of a Hybrid Incremental and Cyclic A/D Conversion Principle

Pierre-André Farine, Luca Rossi, Steve Tanner

This paper presents a new hybrid A/D conversion principle based on the combination of an incremental conversion for the most significant part of the result and on a cyclic conversion for the least significant part. The proposed approach exhibits a resoluti ...

2009

Real-time input-constrained MPC using fast gradient methods

Colin Neil Jones

Linear quadratic model predictive control (MPC) with input constraints leads to an optimization problem that has to be solved at every instant in time. Although there exists computational complexity analysis for current online optimization methods dedicate ...

IEEE2009

Combining robustness and recovery for airline schedules

Niklaus Eggenberg

In this thesis, we address different aspects of the airline scheduling problem. The main difficulty in this field lies in the combinatorial complexity of the problems. Furthermore, as airline schedules are often faced with perturbations called disruptions ...

EPFL2009

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 = ...

Springer2010