Publication

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Publications associées (40)

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

Multi-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme

Boi Faltings, Immanuel Trummer

The goal of multi-objective quality-driven service selection (QDSS) is to find service selections for a workflow whose quality-of-service (QoS) values are Pareto-optimal. We consider multiple QoS attributes such as response time, cost, and reliability. A s ...

Institute of Electrical and Electronics Engineers2014

Socially-Aware Large-Scale Crowd Forecasting

Alexandre Massoud Alahi, Vignesh Ramanathan

In crowded spaces such as city centers or train stations, human mobility looks complex, but is often influenced only by a few causes. We propose to quantitatively study crowded environments by introducing a dataset of 42 million trajectories collected in t ...

IEEE2014

Constrained Binary Identification Problem

Amin Karbasi, Morteza Zadimoghaddam

We consider the problem of building a binary decision tree, to locate an object within a set by way of the least number of membership queries. This problem is equivalent to the “20 questions game” of information theory and is closely related to lossless so ...

2013

Fast Byzantine Agreement

Rachid Guerraoui, Florian Huc

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

2013

Computation in Multicast Networks: Function Alignment and Converse Theorems

Michael Christoph Gastpar, Naveen Goela

The classical problem in network coding theory considers communication over multicast networks. Multiple transmitters send independent messages to multiple receivers which decode the same set of messages. In this work, computation over multicast networks i ...

2012

Approximation Algorithms for Modern Multi-Processor Scheduling Problems

Martin Niemeier

This thesis is devoted to the design and analysis of algorithms for scheduling problems. These problems are ubiquitous in the modern world. Examples include the optimization of local transportation, managing access to concurrent resources like runways at a ...

EPFL2012

Hardness of Approximating Flow and Job Shop Scheduling Problems

Ola Nils Anders Svensson

We consider several variants of the job shop problem that is a fundamental and classical problem in scheduling. The currently best approximation algorithms have worse than logarithmic performance guarantee, but the only previously known inapproximability r ...

2011

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

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