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.
This work is concerned with the computational complexity of the recognition of \mboxLP2, the class of regions of the Euclidian space that can be classified exactly by a two-layered perceptron. Several subclasses of \mboxLP2 of particular interest ...
We present in this paper an approximative method for distributed combinatorial optimization problems based on dynamic programming. The algorithm is a utility propagation method and requires a linear number of messages. The largest message is in the worst c ...
A shared memory abstraction can be robustly emulated over an asynchronous message passing system where any process can fail by crashing and possibly recover (crash-recovery model), by having (a) the processes exchange messages to synchronize their read and ...
This paper investigates the time-complexity of the non-blocking atomic commit (NBAC) problem in a synchronous distributed model where t out of n processes may fail by crashing. We exhibit for t > 3 an inherent trade-off between the fast abort property of N ...
Many envisioned applications of ad hoc networks involve only small-scale networks that we term Vicinity Ad-hoc Groups (VAGs). Distributed coordination services, instead of pairwise communications, are the primary requirements of VAGs. Existing designs for ...
Linear cryptanalysis remains the most powerful attack against DES at this time. Given 243 known plaintext-ciphertext pairs, Matsui expected a complexity of less than 243 DES evaluations in 85% of the cases for recovering the key. In this paper, w ...
This paper establishes the first theorem relating resilience, round complexity and authentication in distributed computing. We give an exact measure of the time complexity of consensus algorithms that tolerate Byzantine failures and arbitrary long periods ...
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementations of this abstraction in the case of ...
