Concept

BPP (complexity)

Related publications (73)

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.

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

In-Network View Synthesis for Interactive Multiview Video Systems

Pascal Frossard, Laura Toni

In multiview applications, camera views can be used as reference views to synthesize additional virtual viewpoints, allowing users to freely navigate within a 3D scene. However, bandwidth constraints may restrict the number of reference views sent to clien ...

Ieee-Inst Electrical Electronics Engineers Inc2016

Fast Robust PCA on Graphs

Pierre Vandergheynst, Gilles Puy, Nathanaël Perraudin, Nauman Shahid, Vasilis Kalofolias

Mining useful clusters from high dimensional data has received significant attention of the computer vision and pattern recognition community in the recent years. Linear and non-linear dimensionality reduction has played an important role to overcome the c ...

Ieee-Inst Electrical Electronics Engineers Inc2016

Exploring stabilisation techniques for the reduced basis approximation of avection-diffusion PDEs

Christèle Marie Zbinden

In this thesis, we explore possible stabilisation methods for the reduce basis approximation of advection-diffusion problems, for which the advection term is dominating. The options we consider are mainly inspired by the Variational Multiscale method (VMS) ...

2016

Optimized Coding Strategies for Interactive Multiview Video

Ana Karina De Abreu Goes

The natural next step in improving the realistic experience in multimedia services is interactive multiview video (IMV). IMV promises to enable the users to freely navigate through a scene by selecting their preferred viewpoints from any view position for ...

EPFL2015

Unlabeled Sensing

Golnooshsadat Elhami

Like other data sensing problems, in unlabeled sensing, the target is to solve the equation y = Φx by finding vector x given a set of sample values in vector y as well as the matrix Φ. However, the main challenge in unlabeled sensing is that the correct or ...

2015

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regevproved that the problem is NP-hard to approximate within a factor2 - ∈, assuming the Unique Games Conjecture (UGC). This is tig ...

IEEE Computer Society2015

Compute-and-Forward: Finding the Best Equation

Michael Christoph Gastpar, Saeid Sahraei

Compute-and-Forward is an emerging technique to deal with interference. It allows the receiver to decode a suitably chosen integer linear combination of the transmitted messages. The integer coefficients should be adapted to the channel fading state. Optim ...

2014

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

Ramsey-Type Results For Semi-Algebraic Relations

János Pach

A k-ary semi-algebraic relation E on R-d is a subset of R-kd, the set of k-tuples of points in R-d, which is determined by a finite number of polynomial inequalities in kd real variables. The description complexity of such a relation is at most t if d, k < ...

Amer Mathematical Soc2014