Concept

Undecidable problem

Related publications (43)

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.

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

Probabilistic acoustic

Miranda Krekovic

During my doctoral project I studied probabilistic models for acoustics and time-of-flight setups. The project consisted of solving the simultaneous localization and mapping problem ─ building a map of acoustic sources from time-of-flight measures obtained ...

2015

Near-Optimally Teaching the Crowd to Classify

Andreas Krause, Amin Karbasi, Ilija Bogunovic

How should we present training examples to learners to teach them classification rules? This is a natural problem when training workers for crowdsourcing labeling tasks, and is also moti- vated by challenges in data-driven online educa- tion. We propose a ...

2014

Learning search polices from humans in a partially observable context

Aude Billard, Guillaume Pierre Luc De Chambrier

Decision making and planning for which the state information is only partially available is a problem faced by all forms of intelligent entities they being either virtual, synthetic or biological. The standard approach to mathematically solve such a decisi ...

2014

Extendability of Continuous Maps Is Undecidable

We consider two basic problems of algebraic topology: the extension problem and the computation of higher homotopy groups, from the point of view of computability and computational complexity. The extension problem is the following: Given topological space ...

Springer2014

Network Neutrality Inference

Ovidiu Sebastian Mara, Zhiyong Zhang

When can we reason about the neutrality of a network based on external observations? We prove conditions under which it is possible to (a) detect neutrality violations and (b) localize them to specific links, based on external observations. Our insight is ...

2014

Explicit non-local damage computations in dynamics: on the importance of the choice of the non-local variable.

Jean-François Molinari, Nicolas Richart, Cyprien Wolff

Traditional local approaches to continuum damage mechanics are known to lead to mesh dependency due to damage localization. Some corrections for this ill-posed problem exist through localization limiters. The integral non-local regularization is widely use ...

2012

24⨯24⨯24

Exercise The architectonic space is an exercise in architecture. It invites students to follow a particular approach to design that, for pedagogical purposes, limits the number of questions considered, in order to privilege a specific dimension of architec ...

UCLouvain.be2012

Laplacian Meshes for Monocular 3D Shape Recovery

Pascal Fua, Aydin Varol, Tien Dat Ngo, Jonas Olof Martin Östlund

We show that by extending the Laplacian formalism, which was first introduced in the Graphics community to regularize 3D meshes, we can turn the monocular 3D shape reconstruction of a deformable surface given correspondences with a reference image into a w ...

2012

Content Search Through Comparisons

Amin Karbasi

We study the problem of navigating through a database of similar objects using comparisons under heterogeneous demand, a problem strongly related to small-world network design. We show that, under heterogeneous demand, the small-world network design proble ...

2011