Concept

Communication complexity

Related publications (157)

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.

LPN in Cryptography

Sonia Mihaela Bogos

The security of public-key cryptography relies on well-studied hard problems, problems for which we do not have efficient algorithms. Factorization and discrete logarithm are the two most known and used hard problems. Unfortunately, they can be easily solv ...

EPFL2017

Enabling exact delay synthesis

Giovanni De Micheli, Mathias Soeken, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

Given (i) a Boolean function, (ii) a set of arrival times at the inputs, and (iii) a gate library with associated delay values, the exact delay synthesis problem asks for a circuit implementation which minimizes the arrival time at the output(s). The exact ...

IEEE2017

Jump-Penalized Least Absolute Values Estimation of Scalar or Circle-Valued Signals

Michaël Unser, Martin Kurt Storath

We study jump-penalized estimators based on least absolute deviations which are often referred to as Potts estimators. They are estimators for a parsimonious piecewise constant representation of noisy data having a noise distribution which has heavier tail ...

Oxford University Press2017

Complexity Certification of the Fast Alternating Minimization Algorithm for Linear MPC

Colin Neil Jones, Ye Pu, Melanie Nicole Zeilinger

In this technical note, the fast alternating minimization algorithm (FAMA) is proposed to solve model predictive control (MPC) problems with polytopic and second-order cone constraints. Two splitting strategies with efficient implementations for MPC proble ...

2017

How Fast can a Distributed Transaction Commit?

Rachid Guerraoui, Junxiong Wang

The atomic commit problem lies at the heart of distributed database systems. The problem consists for a set of processes (database nodes) to agree on whether to commit or abort a transaction (agreement property). The commit decision can only be taken if al ...

2017

How Fast can a Distributed Transaction Commit?

Rachid Guerraoui, Junxiong Wang

ACM Press2017

Aggregate route choice models

Evanthia Kazagli

Route choice analysis concerns the understanding, modeling and prediction of the itinerary of an individual who travels from one position to another. In this thesis we elaborate on aggregate route choice analysis. The objective is the development of a flex ...

EPFL2017

A Composition Theorem for Conical Juntas

Mika Tapani Göös

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2016

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

János Pach

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of ev ...

Society for Industrial and Applied Mathematics2016

Convex block-sparse linear regression with expanders - provably

Volkan Cevher, Quoc Tran Dinh, Anastasios Kyrillidis, Luca Baldassarre, Bubacarr Bah

Sparse matrices are favorable objects in machine learning and optimization. When such matrices are used, in place of dense ones, the overall complexity requirements in optimization can be significantly reduced in practice, both in terms of space and run-ti ...

2016