Concept

Average-case complexity

Related publications (135)

Graph fragmentation problem: analysis and synthesis

Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to a network. The graph fragmentation problem (GFP) is the result of a worst-case analysis of a random attack. We can choose a fixed number of indivi ...

WILEY2019

String Matching: Communication, Circuits, and Learning

Mika Tapani Göös

String matching is the problem of deciding whether a given n-bit string contains a given k-bit pattern. We study the complexity of this problem in three settings. - Communication complexity. For small k, we provide near-optimal upper and lower bounds on th ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2019

Improving hydropower flexibility by synergizing independently managed utilities

Giovanni De Cesare, Pedro Filipe De Almeida Manso, Sabine Chamoun, Vincent Gaertner, Steve Crettenand

Increasing the flexibility of hydropower allows operators to produce at optimal time ranges, not only dependent on the demand flow but also on the price trends. However, the possibility to improve hydropower flexibility can be hindered when assets are mana ...

Hydropower&Dams, Aqua Media International2019

Coordinate-Descent Diffusion Learning by Networked Agents

Ali H. Sayed, Bicheng Ying, Chengcheng Wang

This paper examines the mean-square error performance of diffusion stochastic algorithms under a generalized coordinate-descent scheme. In this setting, the adaptation step by each agent is limited to a random subset of the coordinates of its stochastic gr ...

Ieee-Inst Electrical Electronics Engineers Inc2018

Meandering particle bunches and a link between averages of time series of particle counts and higher-order moments

Ambrogio Fasoli, Ivo Furno, Paolo Ricci, Marcelo Baquero Ruiz, Fabian Manke

Time-averaged spatially resolved measurements are used in many fields of physics to determine spatial distributions of a physical quantity. Although one could think that time averaging suppresses all information on time variation, there are some situations ...

2018

On flexible Green function methods for atomistic/continuum coupling

Max Ludwig Hodapp

Atomistic/continuum (A/C) coupling schemes have been developed during the past twenty years to overcome the vast computational cost of fully atomistic models, but have not yet reached full maturity to address many problems of practical interest. This work ...

EPFL2018

PDE-constrained optimal control problems with uncertain parameters using SAGA

Fabio Nobile, Matthieu Claude Martin

We consider an optimal control problem for an elliptic partial differential equation (PDE) with random coefficients. The control function is a deterministic, distributed forcing term that minimizes an expected quadratic regularized loss functional. We cons ...

2018

Personalized Anatomic Eye Model From T1-Weighted Volume Interpolated Gradient Echo Magnetic Resonance Imaging of Patients With Uveal Melanoma

Meritxell Bach Cuadra, Raphael Sznitman, Alessia Pica

Purpose: We present a 3-dimensional patient-specific eye model from magnetic resonance imaging (MRI) for proton therapy treatment planning of uveal melanoma (UM). During MRI acquisition of UM patients, the point fixation can be difficult and, together with ...

ELSEVIER SCIENCE INC2018

Fractal and Complexity Analysis of Crack Patterns of Masonry Walls

Katrin Beyer, Amir Rezaie

In order to develop automatic image-based methods for damage evaluation after earthquakes, crack maps need to be evaluated using computer-based algorithms. A common method to link the crack map to a damage state is to compute the fractal dimension of the c ...

2018

Comparison of L1 and L5 Bands GNSS Signals Acquisition

Cyril Botteron, Jérôme Leclère

Nowadays, civil Global Navigation Satellite System (GNSS) signals are available in both L1 and L5 bands. A receiver does not need to acquire independently the signals in both bands coming from a same satellite, since their carrier Doppler and code delay ar ...

2018

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.