Concept

Analyse de la complexité des algorithmes

Publications associées (197)

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

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

Recipes on Hard Thresholding Methods

Volkan Cevher, Anastasios Kyrillidis

Compressive sensing (CS) is a data acquisition and recovery technique for finding sparse solutions to linear inverse problems from sub-Nyquist measurements. CS features a wide range of computationally efficient and robust signal recovery methods, based on ...

2011

Cognitive Radio Through Primary Control Feedback

Michael Christoph Gastpar

A fundamental problem in dynamic frequency reuse is that the cognitive radio is ignorant of the amount of interference it inflicts on the primary license holder. Policies that attempt to limit interference without the active participation of the primary ar ...

2011

Computational analysis of protein-DNA interactions from ChIP-seq data

Felix Naef, Jacques Rougemont

Chromatin immunoprecipitation experiments followed by ultra-high-throughput sequencing (ChIP-seq) is becoming the method of choice to identify transcription factor binding sites in prokaryotes and eukaryotes in vivo. Here, we review the computational steps ...

2011

An Information Theoretic Approach to Speaker Diarization of Meeting Recordings

Deepu Vijayasenan

In this thesis we investigate a non parametric approach to speaker diarization for meeting recordings based on an information theoretic framework. The problem is formulated using the Information Bottleneck (IB) principle. Unlike other approaches where the ...

EPFL2010

Fast Randomized Test-and-Set and Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh, Hagit Albo Attiya, Andrei Giurgiu

Most people believe that renaming is easy: simply choose a name \emph{at random}; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

Spatial Fringe Analysis Methods and their Application to Holographic Interferometry and Fringe Projection Techniques

Sai Siva Gorthi

To date, no fringe analysis technique has the capability to provide simultaneous and direct estimation of the continuous distributions corresponding to the interference phase and its first and second-order derivatives within the framework of a single inter ...

EPFL2010

3D finite element model of semi-solid permeability in an equiaxed granular structure

Roland Logé

A multi-domain finite element formulation has been applied to determine the semi-solid permeability of an equiaxed granular structure. The granular model was constructed from a Voronoï tessellation algorithm. The liquid-solid interface is represented impli ...

2010

Polytopic Approximation of Explicit Model Predictive Controllers

Colin Neil Jones

A model predictive control law (MPC) is given by the solution to a parametric optimization problem that can be pre-computed offline, which provides an explicit map from state to input that can be rapidly evaluated online. However, the primary limitations o ...

2010

The Improbable Differential Attack: Cryptanalysis of Reduced Round CLEFIA

Cihangir Tezcan

In this paper we present a new statistical cryptanalytic technique that we call improbable differential cryptanalysis which uses a differential that is less probable when the correct key is used. We provide data complexity estimates for this kind of attack ...

Springer2010