Concept

Average-case complexity

Related publications (135)

Visual Focus of Attention Estimation from Head Pose Posterior Probability Distributions

We address the problem of recognizing the visual focus of attention (VFOA) of meeting participants from their head pose and contextual cues. The main contribution of the paper is the use of a head pose posterior distribution as a representation of the head ...

IDIAP2007

Multichannel thresholding with sensing dictionaries

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper shows introduces the use sensing dictionaries for p-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We do both a worst case and average case recovery analyses of this ...

2007

Three Algorithms for Interface Synthesis: A Comparative Study

Vasu Singh, Dirk Thilo Beyer

A temporal interface for a system component is a finite automaton that specifies the legal sequences of input events. We evaluate and compare three different algorithms for automatically extracting the temporal interface from the transition graph of a comp ...

2006

Reducing Time Complexity in RFID Systems

Gildas Avoine, Philippe Oechslin, Etienne Dysli

Radio frequency identification systems based on low-cost computing devices is the new plaything that every company would like to adopt. Its goal can be either to improve the productivity or to strengthen the security. Specific identification protocols base ...

2006

Fast Probabilistic Subsumption Checking for Publish/Subscribe Systems

Karl Aberer, Ivana Podnar, Oana Anca Jurca

Efficient subsumption checking, deciding whether a subscription or publication is subsumed (covered) by a set of previously defined subscriptions, is of paramount importance for publish/subscribe systems. It provides the core system functionality, and addi ...

2006

Keypoint Recognition using Randomized Trees

Pascal Fua, Vincent Lepetit

In many 3--D object-detection and pose-estimation problems, run-time performance is of critical importance. However, there usually is time to train the system, which we will show to be very useful. Assuming that several registered images of the target obje ...

2006

Toward Online Probabilistic Path Replanning

Roland Siegwart, Björn Jensen, Roland Philippsen

In this talk we present work on sensor-based motion planning in initially unknown dynamic environments. Motion detection and probabilistic motion modeling are combined with a smooth navigation function to perform on-line path planning and replanning in clu ...

2006

Evolving Neural Controllers for Collective Robotic Inspection

Alcherio Martinoli

In this paper, an automatic synthesis methodology based on evolutionary computation is applied to evolve neural controllers for a homogeneous team of miniature autonomous mobile robots. Both feed-forward and recurrent neural networks can be evolved with fi ...

2006

Lucky Read/Write Access to Robust Atomic Storage

Rachid Guerraoui, Marko Vukolic, Ron Levy

This paper establishes tight bounds on the best-case time-complexity of distributed atomic read/write storage implementations that tolerate worst-case conditions. We study asynchronous robust implementations where a writer and a set of reader processes (cl ...

2005

Computing with Reads and Writes in the Absence of Step Contention

Rachid Guerraoui

This paper studies implementations of concurrent objects that exploit the absence of step contention. These implementations use only reads and writes when a process is running solo. The other processes might be busy with other objects, swapped-out, failed, ...

2005

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.