Publications related to Average-case complexity

Incremental View Maintenance for Collection Programming

Christoph Koch, Daniel Lupei, Val Tannen

In the context of incremental view maintenance (IVM), delta query derivation is an essential technique for speeding up the processing of large, dynamic datasets. The goal is to generate delta queries that, given a small change in the input, can update the ...

ACM2016

MATHICSE Technical Report : Fast computation of the matrix exponential for a Toeplitz matrix

Daniel Kressner, Robert Gerhard Jérôme Luce

The computation of the matrix exponential is a ubiquitous operation in numerical mathematics, and for a general, unstructured n×n matrix it can be computed in O(n3) operations. An interesting problem arises if the input matrix is a Toeplitz matrix, for exa ...

MATHICSE2016

Learning-Based Compressive Subsampling

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Yen-Huan Li, Luca Baldassarre, Baran Gözcü

The problem of recovering a structured signal

\mathbf{x} \in \mathbb{C}^p

from a set of dimensionality-reduced linear measurements

\mathbf{b} = \mathbf {A}\mathbf {x}

arises in a variety of applications, such as medical imaging, spectroscopy, Fourier o ...

Ieee-Inst Electrical Electronics Engineers Inc2016

Synthesizing efficient systems in probabilistic environments

Barbara Jobstmann, David Parker

We present a formalism, algorithms and tools to synthesise reactive systems that behave efficiently, i.e., which achieve an optimal trade-off between a given cost and reward model. Synthesis aims to automatically generate a program from a specification. Mo ...

Springer2016

A Low-Power Correlator for Wakeup Receivers with Algorithm Pruning through Early Termination

Andreas Peter Burg, Adam Shmuel Teman, Reza Ghanaatian Jahromi, Jeremy Hugues-Felix Constantin

A low-complexity, low-power digital correlator for wakeup receivers is presented. With the proposed algorithm, unnecessary computational cycles are dynamically pruned from the correlation using an early threshold check. For the algorithm, we provide a rigo ...

Ieee2016

Worst-case execution time analysis for many-core architectures with NoC

Alena Simalatsar, Stefanos Skalistis

The optimal deployment of data streaming applications onto multi-/many-core platform providing real-time guarantees requires to solve the application partitioning and placement, buffer allocation and task mapping and scheduling optimisation problem using t ...

Springer Int Publishing Ag2016

Online Auctions for Dynamic Assignment: Theory and Empirical Evaluation

Boi Faltings, Sujit Prakash Gujar

Dynamic resource assignment is a common problem in multi-agent systems. We consider scenarios in which dynamic agents have preferences about assignments and the resources that can be assigned using online auctions. We study the trade-off between the follow ...

Ios Press2016

A new mathematical formulation to integrate supply and demand within a choice-based optimization framework

Michel Bierlaire, Shadi Sharif Azadeh, Meritxell Pacheco Paneque

During the last decade, there has been an increasing trend to combine customer behavior models in optimization, since it provides a better understanding of the preferences of clients to policy makers while planning for their systems. These preferences are ...

2016

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.

Learning-Based Compressive Subsampling

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Yen-Huan Li, Luca Baldassarre, Baran Gözcü

The problem of recovering a structured signal

\mathbf{x} \in \mathbb{C}^p

from a set of dimensionality-reduced linear measurements

\mathbf{b} = \mathbf {A}\mathbf {x}

arises in a variety of applications, such as medical imaging, spectroscopy, Fourier o ...

Ieee-Inst Electrical Electronics Engineers Inc2016

Average-case complexity

Control-Quality Driven Design of Embedded Control Systems with Stability Guarantees

Multi-index Stochastic Collocation for random PDEs

Incremental View Maintenance for Collection Programming

MATHICSE Technical Report : Fast computation of the matrix exponential for a Toeplitz matrix

Learning-Based Compressive Subsampling

Synthesizing efficient systems in probabilistic environments

A Low-Power Correlator for Wakeup Receivers with Algorithm Pruning through Early Termination

Worst-case execution time analysis for many-core architectures with NoC

Online Auctions for Dynamic Assignment: Theory and Empirical Evaluation

A new mathematical formulation to integrate supply and demand within a choice-based optimization framework

Graph Chatbot

Chat with Graph Search

MATHICSE Technical Report : Fast computation of the matrix exponential for a Toeplitz matrix

Synthesizing efficient systems in probabilistic environments

Control-Quality Driven Design of Embedded Control Systems with Stability Guarantees

Incremental View Maintenance for Collection Programming

Learning-Based Compressive Subsampling

A Low-Power Correlator for Wakeup Receivers with Algorithm Pruning through Early Termination

Worst-case execution time analysis for many-core architectures with NoC

Online Auctions for Dynamic Assignment: Theory and Empirical Evaluation

A new mathematical formulation to integrate supply and demand within a choice-based optimization framework

Multi-index Stochastic Collocation for random PDEs