Publications related to Analysis of algorithms

Practicality and time complexity of a sparsified RNA folding algorithm

Philipp Bucher, Slavica Dimitrieva Janeva

Commonly used RNA folding programs compute the minimum free energy structure of a sequence under the pseudoknot exclusion constraint. They are based on Zuker's algorithm which runs in time O(n^3). Recently, it has been claimed that RNA folding can be achie ...

2012

Real time multi-object tracking using multiple cameras

Michail Zervos

We build a real-time multi-people tracker, which is based on the Kalman Filter. The input to the software is a Probabilistic Occupancy Map of the observed area. The main goal of the project is to incorporate this tracker to the real-time detection software ...

2012

Thick Boundaries in Binary Space and Their Influence on Nearest-Neighbor Search

Pascal Fua, Vincent Lepetit, Tomasz Piotr Trzcinski

Binary descriptors allow faster similarity computation than real-valued ones while requiring much less storage. As a result, many algorithms have recently been proposed to binarize ﬂoating-point descriptors so that they can be searched for quickly. Unfortu ...

Elsevier2012

MPTCP is not Pareto-Optimal: Performance Issues and a Possible Solution

Jean-Yves Le Boudec, Nicolas Gabriel Gast, Ramin Khalili, Utkarsh Upadhyay, Miroslav Popovic

MPTCP has been proposed recently as a mechanism for sup- porting transparently multiple connections to the applica- tion layer. It is under discussion at the IETF. We show, however, that the current MPTCP suffers from two prob- lems: (P1) Upgrading some TC ...

2012

Privacy-Enhancing Technologies for Medical Tests Using Genomic Data

Jean-Pierre Hubaux, Erman Ayday, Jean Louis Raisaro

In this paper, we propose privacy-enhancing technologies for medical tests and personalized medicine methods, which utilize patients' genomic data. First, we highlight the potential privacy threats on genomic data and the challenges of providing privacy-pr ...

2012

Sub-Logarithmic Test-and-Set Against a Weak Adversary

Dan Alistarh

A randomized implementation is given of a test-and-set register with O(log log it) individual step complexity and O(n) total step complexity against an oblivious adversary. The implementation is linearizable and multi-shot, and shows an exponential complex ...

Springer-Verlag Berlin2011

The Complexity of Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of Omega(k) process steps for deterministic renaming into ...

Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa2011

Fast Speaker Verification on Mobile Phone data using Boosted Slice Classifiers

Sébastien Marcel, Anindya Roy

In this work, we investigate a novel computationally efficient speaker verification (SV) system involving boosted ensembles of simple threshold-based classifiers. The system is based on a novel set of features called “slice features”. Both the system and t ...

2011

Multi-Objective Airport Gate Assignment Problem

Michel Bierlaire, Prem Kumar

In this paper, we consider the gate assignment for a large airline at its hub airport. It is considered to be a highly complex problem with the possibility of application in both planning as well as operations mode. There are various considerations that ar ...

2011

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

Analysis of algorithms

Graph Chatbot

Chat with Graph Search

Practicality and time complexity of a sparsified RNA folding algorithm

Real time multi-object tracking using multiple cameras

Thick Boundaries in Binary Space and Their Influence on Nearest-Neighbor Search

MPTCP is not Pareto-Optimal: Performance Issues and a Possible Solution

Privacy-Enhancing Technologies for Medical Tests Using Genomic Data

Sub-Logarithmic Test-and-Set Against a Weak Adversary

The Complexity of Renaming

Fast Speaker Verification on Mobile Phone data using Boosted Slice Classifiers

Multi-Objective Airport Gate Assignment Problem

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Fast Speaker Verification on Mobile Phone data using Boosted Slice Classifiers

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Multi-Objective Airport Gate Assignment Problem

Sub-Logarithmic Test-and-Set Against a Weak Adversary

Thick Boundaries in Binary Space and Their Influence on Nearest-Neighbor Search

Practicality and time complexity of a sparsified RNA folding algorithm

Real time multi-object tracking using multiple cameras

MPTCP is not Pareto-Optimal: Performance Issues and a Possible Solution

Privacy-Enhancing Technologies for Medical Tests Using Genomic Data

The Complexity of Renaming