Concept

Oracle (machine de Turing)

Publications associées (35)

Hardness Of Precedence Constrained Scheduling On Identical Machines

In 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. To date this has remained the best algori ...

2011

Compression with Graphical Constraints: An Interactive Browser

Amin Karbasi, Morteza Zadimoghaddam

We study the problem of navigating/searching through a database of objects with potentially different popularities using a membership oracle. The membership oracle, given a subset of objects

A

, and a target object

t

, determines whether

A

contains

t

...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011

Conditional hardness of precedence constrained scheduling on identical machines

Ola Nils Anders Svensson

Already in 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. Till this date it has remained th ...

ACM2010

Obfuscation for Cryptographic Purposes

Martijn Stam

Loosely speaking, an obfuscation O of a function f should satisfy two requirements: firstly, using O, it should be possible to evaluate f; secondly, O should not reveal anything about f that cannot be learnt from oracle access to f alone. Several definitio ...

Springer Verlag2010

Fast Randomized Test-and-Set and Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh, Hagit Albo Attiya, Andrei Giurgiu

Most people believe that renaming is easy: simply choose a name \emph{at random}; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write ...

2010

Fast Randomized Test-and-Set and Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh, Hagit Albo Attiya, Andrei Giurgiu

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

EPnP: An Accurate O(n) Solution to the PnP Problem

Pascal Fua, Vincent Lepetit

We propose a non-iterative solution to the PnP problem-the estimation of the pose of a calibrated camera from n 3D-to-2D point correspondences-whose computational complexity grows linearly with n. This is in contrast to state-of-the-art methods that are O( ...

Springer Verlag2009

Development of divertor tungsten coatings for the JET ITER-like wall

Richard Pitts

The main objectives of the JET ITER-like Wall Project are to provide a beryllium main wall and tungsten divertor with at least a 4 year lifetime to allow full evaluation of the materials and related plasma scenarios for ITER. Tungsten coatings will be used ...

Elsevier2009

Mutual Authentication in RFID: Security and Privacy

Serge Vaudenay, Radu-Ioan Paise

In RFID protocols, tags identify and authenticate themselves to readers. At Asiacrypt 2007, Vaudenay studied security and privacy models for these protocols. We extend this model to protocols which offer reader authentication to tags. Whenever corruption i ...

ACM Press2008

Accurate Non-Iterative O(n) Solution to the PnP Problem

Pascal Fua, Vincent Lepetit

We propose a non-iterative solution to the PnP problem---the estimation of the pose of a calibrated camera from n 3D-to-2D point correspondences---whose computational complexity grows linearly with n. This is in contrast to state-of-the-art method that are ...

2007

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search