Concept

NP (complexity)

Related publications (324)

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.

Bayesian Early Mode Decision Technique for View Synthesis Prediction-enhanced Multiview Video Coding

Pascal Frossard, Thomas Maugey

View synthesis prediction (VSP) is a coding mode that predicts video blocks from synthesised frames. It is particularly useful in a multi-camera setup with large inter-camera distances. Adding a VSP-based SKIP mode to a standard Multiview Video Coding (MVC ...

Institute of Electrical and Electronics Engineers2013

Testing additive integrality gaps

Friedrich Eisenbrand, Gennady Shmonin

We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in ...

Springer Berlin Heidelberg2013

TCHo: A Code-Based Cryptosystem

Serge Vaudenay, Alexandre Raphaël Duc

TCHo is a public-key cryptosystem based on the hardness of finding a multiple polynomial with low weight and on the hardness of distinguishing between the output of an LFSR with noise and some random source. An early version was proposed in 2006 by Finiasz ...

Springer Berlin Heidelberg2013

Buffer optimization based on critical path analysis of a dataflow program design

Marco Mattavelli, Simone Casale Brunet

The trade-off between throughput and memory constraints is a common design problem in embedded systems, and especially for streaming applications, where the memory in question usually occurs in the form of buffers for streams of data. This paper presents a ...

IEEE2013

Fast encoding techniques for Multiview Video Coding

Pascal Frossard

Multiview Video Coding (MVC) is a technique that permits efficient compression of multiview video. MVC uses variable block size motion and disparity estimation for block matching. This requires an exhaustive search process that involves all possible macro- ...

Elsevier Science Bv2013

Tractability of interpretability via selection of group-sparse models

Volkan Cevher, Luca Baldassarre, Nirav Bhan

Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. A promise of these models is to lead to “interpretable” signals for which we identify i ...

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

Randomized recovery for boolean compressed sensing

Martin Vetterli, Mitra Fatemi

We consider the problem of boolean compressed sensing, which is alternatively known as group testing. The goal is to recover a small number of defective items in a large set from a few collective binary tests. This problem can be formulated as a binary lin ...

2013

Generating Fast Indulgent Algorithms

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficien ...

Springer Verlag2012

A reduced basis hybrid method for the coupling of parametrized domains represented by fluidic networks

Alfio Quarteroni, Gianluigi Rozza, Laura Iapichino

In this paper we propose a reduced basis hybrid method (RBHM) for the approximation of partial differential equations in domains represented by complex networks where topological features are recurrent. The RBHM is applied to Stokes equations in domains wh ...

Elsevier2012