Concept

Big O notation

Related publications (72)

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.

Dependence properties of spatial rainfall extremes and areal reduction factors

Anthony Christopher Davison, Sebastian Engelke

Areal reduction factors (ARFs) transform an estimate of extreme rainfall at a point to an estimate of extreme rainfall over a spatial domain, and are commonly used in flood risk estimation. For applications such as the design of large infrastructure, dam s ...

2018

Increasing Availability in Distributed Storage Systems via Clustering

Michael Christoph Gastpar, Saeid Sahraei

We introduce the Fixed Cluster Repair System (FCRS) as a novel architecture for Distributed Storage Systems (DSS) that achieves a small repair bandwidth while guaranteeing a high availability. Specifically, we partition the set of servers in a DSS into s c ...

2018

Exploiting Weak Supermodularity for Coalition-Proof Mechanisms

Maryam Kamgarpour, Orcun Karaca

Under the incentive-compatible Vickrey-Clarke-Groves mechanism, coalitions of participants can influence the auction to obtain higher collective profit. These manipulations were proven to be eliminated if and only if the market objective is supermodular. N ...

IEEE2018

Robust Bounds In Multivariate Extremes

Sebastian Engelke

Extreme value theory provides an asymptotically justified framework for estimation of exceedance probabilities in regions where few or no observations are available. For multivariate tail estimation, the strength of extremal dependence is crucial and it is ...

Institute of Mathematical Statistics2017

Combinatorial Penalties: Which structures are preserved by convex relaxations?

Volkan Cevher, Marwa El Halabi

We consider the homogeneous and the non-homogeneous convex relaxations for combinatorial penalty functions defined on support sets. Our study identifies key differences in the tightness of the resulting relaxations through the notion of the lower combinato ...

2017

Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer

Christoph Koch, Immanuel Trummer

The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA ...

Assoc Computing Machinery2016

A Composition Theorem for Conical Juntas

Mika Tapani Göös

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two ...

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

Two subtle convex nonlocal approximations of the BV-norm

Hoài-Minh Nguyên

Inspired by the BBM formula and by work of G. Leoni and D. Spector, we analyze the asymptotic behavior of two sequences of convex nonlocal functionals (Psi(n)(u)) and (Phi(n)(u)) which converge formally to the BV-norm of u. We show that pointwise convergen ...

Elsevier2016

Tracking residence times in hydrological systems: forward and backward formulations

Andrea Rinaldo, Paolo Benettin, Gianluca Botter

In recent years, several papers contributed to the development and clarification of key theoretical issues underlying the formulation of transport by travel time distributions in catchments. Such a formulation provides a robust description of the temporal ...

Wiley-Blackwell2015

Improving Christofides' Algorithm for the s-t Path TSP

Hyung Chan An

We present a deterministic (1+root 5/2)-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the t ...

Assoc Computing Machinery2015