Recherche

Afficher tous les résultats pour

Accueil

Concept

Réseau de tri

Science formelle
Informatique théorique
Algorithme
Analyse de la complexité de...

Publications associées (21)

À propos
Confidentialité
Mentions légales

Graph Chatbot

Tight Bounds for Asynchronous Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual ...

Association for Computing Machinery2014

Cracking The Complexity Of Fixed-Point Refinement In Complex Wireless Systems

Paolo Ienne, David Novo Bruna

Fixed-point arithmetic leads to efficient implementations. However, the optimization process required to size each of the implementation signals can be prohibitively complex. In this paper, we introduce a new divide-and-conquer method that is able to appro ...

Ieee2013

Randomized versus Deterministic Implementations of Concurrent Data Structures

Dan Alistarh

One of the key trends in computing over the past two decades has been increased distribution, both at the processor level, where multi-core architectures are now the norm, and at the system level, where many key services are currently distributed overmulti ...

EPFL2012

Sorting Live Stem Cells Based on Sox2 mRNA Expression

Matthias Lütolf, Peter Frey, Jeffrey Alan Hubbell, Hans Mattias Larsson, Seung Tae Lee

While cell sorting usually relies on cell-surface protein markers, molecular beacons (MBs) offer the potential to sort cells based on the presence of any expressed mRNA and in principle could be extremely useful to sort rare cell populations from primary i ...

Public Library of Science2012

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Seth Gilbert, Dan Alistarh, Morteza Zadimoghaddam

We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of

n

processes with step complexity $ ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011

Sorting signed permutations by inversions in O(nlogn) time

Bernard Moret, Yu Lin, Vaibhav Rajan, Krister Swenson

The study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. After the initial breakthrough of Hannenhalli and Pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inv ...

2010

A Weighting Scheme for Enhancing Community Detection in Networks

Martin Hasler, Alireza Khadivi

Many algorithms have recently been proposed for finding communities in networks. By definition, a community is a subset of vertices with a high number of connections among the vertices, but only few connections with other vertices. The worst drawback of mo ...

IEEE2010

Sorting signed permutations by inversions in O(nlogn) time

Bernard Moret, Yu Lin, Vaibhav Rajan, Krister Swenson

Springer2009

Controlled entrapment of cells in hydrogels on chip and cell sorting by dielectrophoresis using liquid electrodes

Thomas Michael Braschler

Alginate gel formation on-chip is presented in the first part of this thesis. The technique allows immobilization, and release, of biological cells on-chip. Furthermore, via layer by layer deposition, a locally heterogeneous environment can be generated at ...

EPFL2009

Efficient Broadcasting Using Network Coding

Jean-Yves Le Boudec, Christina Fragouli, Jörg Widmer

We consider the problem of broadcasting in an ad-hoc wireless network, where all nodes of the network are sources that want to transmit information to all other nodes. Our figure of merit is energy efficiency, a critical design parameter for wireless netwo ...

2008

Page 2 sur 3

n