Concept

Average-case complexity

Related publications (135)

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.

Matrix Recipes for Hard Thresholding Methods

Volkan Cevher, Anastasios Kyrillidis

In this paper, we present and analyze a new set of low-rank recovery algorithms for linear inverse problems within the class of hard thresholding methods. We provide strategies on how to set up these algorithms via basic ingredients for different configura ...

Springer Verlag2014

Tight Bounds for Asynchronous Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual ...

Association for Computing Machinery2014

Time–Data Tradeoffs by Aggressive Smoothing

Volkan Cevher

This paper proposes a tradeoff between sample complexity and computation time that applies to statistical estimators based on convex optimization. As the amount of data increases, we can smooth optimization problems more and more aggressively to achieve ac ...

2014

A sieve algorithm based on overlattices

Anja Annemone Becker

In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie ...

Cambridge Univ Press2014

A Polynomial-Time Solution Scheme for Quadratic Stochastic Programs

Daniel Kuhn

We consider quadratic stochastic programs with random recourse—a class of problems which is perceived to be computationally demanding. Instead of using mainstream scenario tree-based techniques, we reduce computational complexity by restricting the space o ...

2013

Learning a Real Time Grasping Strategy

Aude Billard, Sahar El Khoury, Miao Li

Real time planning strategy is crucial for robots working in dynamic environments. In particular, robot grasping tasks require quick reactions in many applications such as human-robot interaction. In this paper, we propose an approach for grasp learning th ...

2013

On some coloring problems in grids

Dominique de Werra

We study complexity issues related to some coloring problems in grids: we examine in particular the case of List coloring, of Precoloring extension and of (p, q)-List coloring, the case of List coloring in bipartite graphs where lists in the first part of ...

2013

A hybrid on-chip optonanomechanical transducer for ultra-sensitive force measurements

Tobias Kippenberg, Emanuel Gavartin

We realize an integrated hybrid optonanomechanical transducer for the detection of weak forces. We propose and demonstrate with our system that dissipative feedback dramatically decreases the averaging time necessary to detect an incoherent force. (C) 2011 ...

Ieee2012

Randomized versus Deterministic Implementations of Concurrent Data Structures

Dan Alistarh

One of the key trends in computing over the past two decades has been increased distribution, both at the processor level, where multi-core architectures are now the norm, and at the system level, where many key services are currently distributed overmulti ...

EPFL2012

Practicality and time complexity of a sparsified RNA folding algorithm

Philipp Bucher, Slavica Dimitrieva Janeva

Commonly used RNA folding programs compute the minimum free energy structure of a sequence under the pseudoknot exclusion constraint. They are based on Zuker's algorithm which runs in time O(n^3). Recently, it has been claimed that RNA folding can be achie ...

2012