Publications related to Average-case complexity

Average case analysis of multichannel thresholding

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper introduces p-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latter ...

2007

Average case analysis of multichannel sparse approximations using p- thresholding

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper introduces

p

-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latte ...

2007

Performance of Averaging Algorithms in Time-Varying Networks

Patrick Denantes

We study averaging algorithms in time-varying networks, and means tomeasure their performance. We present sufficient conditions on these algorithms, which ensure they lead to computation at each node, of the global average of measurements provided by each ...

2007

Algorithms for Interface Synthesis

Vasu Singh, Dirk Thilo Beyer

A temporal interface for a software component is a ﬁnite automaton that speciﬁes the legal sequences of calls to functions that are provided by the component. We compare and evaluate three different algorithms for automatically extracting temporal interfac ...

Springer2007

The Perfectly-Synchronized Round-based Model of Distributed Computing

Rachid Guerraoui, Bastian Pochon

The perfectly-synchronized round-based model provides the powerful abstraction of crash-stop failures with atomic and synchronous message delivery. This abstraction makes distributed programming very easy.We describe a technique to automatically transform ...

2007

The medial axis of the union of inner Voronoi balls in the plane

Mark Pauly

Consider a dense sampling S of the smooth boundary of a planar shape O, i.e., an open subset of R-2. We show that the medial axis of the union of Voronoi balls centered at Voronoi vertices inside O has a particularly simple structure: it is the union of al ...

2007

A profiling framework for high level design space exploration for memory and system architectures

In 1971, the first microprocessor produced in mass production had 2300 transistor and was able to compute 60'000 operations per second at 740 kHz. Nowadays, even a common gaming console uses a central unit including 243 millions of transistors running at 4 ...

EPFL2007

Analytical Modeling of Large-Signal Cyclo-Stationary Low-Frequency Noise With Arbitrary Periodic Input

Christian Enz, Ananda Sankar Roy

Low-frequency (LF) noise under cyclo-stationary excitation has received considerable attention recently. Until now, only semiempirical models for cyclo-stationary random telegraph signal (RTS) and flicker noise have been reported in the literature. In this ...

2007

Asymmetric Gaussian Multiple Descriptions and Asymmetric Multilevel Diversity Coding

Suhas Diggavi

We consider multiple description source coding problem with Gaussian source and mean squared error, for

K=3

descriptions. We obtain an outer bound for the rate region of the problem. We also derive an inner bound for the problem based on successively ref ...

2007

Average Performance Analysis for Thresholding

Pierre Vandergheynst, Karin Schnass

In this article is shown that with high probability the thresholding algorithm can recover signals that are sparse in a redundant dictionary as long as the {\it 2-Babel function} is growing slowly. This implies that it can succeed for sparsity levels up to ...

2007

Average-case complexity

Graph Chatbot

Chat with Graph Search

Average case analysis of multichannel thresholding

Average case analysis of multichannel sparse approximations using p- thresholding

Performance of Averaging Algorithms in Time-Varying Networks

Algorithms for Interface Synthesis

The Perfectly-Synchronized Round-based Model of Distributed Computing

The medial axis of the union of inner Voronoi balls in the plane

A profiling framework for high level design space exploration for memory and system architectures

Analytical Modeling of Large-Signal Cyclo-Stationary Low-Frequency Noise With Arbitrary Periodic Input

Asymmetric Gaussian Multiple Descriptions and Asymmetric Multilevel Diversity Coding

Average Performance Analysis for Thresholding

A profiling framework for high level design space exploration for memory and system architectures

Average case analysis of multichannel sparse approximations using p- thresholding

Average case analysis of multichannel thresholding

Algorithms for Interface Synthesis

Performance of Averaging Algorithms in Time-Varying Networks

The medial axis of the union of inner Voronoi balls in the plane

The Perfectly-Synchronized Round-based Model of Distributed Computing

Asymmetric Gaussian Multiple Descriptions and Asymmetric Multilevel Diversity Coding

Average Performance Analysis for Thresholding

Analytical Modeling of Large-Signal Cyclo-Stationary Low-Frequency Noise With Arbitrary Periodic Input