Publication

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Related publications (35)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Scalable and Secure Aggregation in Distributed Networks

Rachid Guerraoui, Anne-Marie Kermarrec, Hamza Harkous, Florian Huc

We consider the problem of computing an aggregation function in a \emph{secure} and \emph{scalable} way. Whereas previous distributed solutions with similar security guarantees have a communication cost of

O(n^3)

, we present a distributed protocol that r ...

CoRR2011

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

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

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

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

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

How to Safely Close a Discussion

Serge Vaudenay, Gildas Avoine

In the secure communication problem, we focus on safe termination. In applications such as electronic transactions, we want each party to be ensured that both sides agree on the same state: success or failure. This problem is equivalent to the well known c ...

2007

A profiling framework for high level design space exploration for memory and system architectures

In 1971, the first microprocessor produced in mass production had 2300 transistor and was able to compute 60'000 operations per second at 740 kHz. Nowadays, even a common gaming console uses a central unit including 243 millions of transistors running at 4 ...

EPFL2007

O(n^3)

, we present a distributed protocol that r ...

CoRR2011

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

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Graph Chatbot

Chat with Graph Search

Scalable and Secure Aggregation in Distributed Networks

Additive Combinatorics and Discrete Logarithm Based Range Protocols

Refined quorum systems

Fast Randomized Test-and-Set and Renaming

Silence-Based Communication

Chasing the Weakest System Model for Implementing Omega and Consensus

How to Safely Close a Discussion

A profiling framework for high level design space exploration for memory and system architectures

Refined Quorum Systems

Refined Quorum Systems

Scalable and Secure Aggregation in Distributed Networks

Additive Combinatorics and Discrete Logarithm Based Range Protocols

Refined quorum systems

Refined Quorum Systems

Silence-Based Communication

How to Safely Close a Discussion

Refined Quorum Systems

Chasing the Weakest System Model for Implementing Omega and Consensus

A profiling framework for high level design space exploration for memory and system architectures

Fast Randomized Test-and-Set and Renaming