Publication

Randomized versus Deterministic Implementations of Concurrent Data Structures

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.

On solving LPN using BKW and variants Implementation and Analysis

Serge Vaudenay, Sonia Mihaela Bogos, Florian Tramèr

The Learning Parity with Noise problem (LPN) is appealing in cryptography as it is considered to remain hard in the post-quantum world. It is also a good candidate for lightweight devices due to its simplicity. In this paper we provide a comprehensive anal ...

Springer2016

Multi-index Stochastic Collocation for random PDEs

Fabio Nobile, Lorenzo Tamellini

In this work we introduce the Multi-Index Stochastic Collocation method (MISC) for computing statistics of the solution of a PDE with random data. MISC is a combination technique based on mixed differences of spatial approximations and quadratures over the ...

2016

A Dichotomy for Real Weighted Holant Problems

Sangxia Huang

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks can ...

Springer Basel Ag2016

SHAPE: Linear-Time Camera Pose Estimation With Quadratic Error-Decay

Martin Vetterli, Adam James Scholefield, Alireza Ghasemi

We propose a novel camera pose estimation or perspective-n-point (PnP) algorithm, based on the idea of consistency regions and half-space intersections. Our algorithm has linear time-complexity and a squared reconstruction error that decreases at least qua ...

Ieee2016

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

Worst-case execution time analysis for many-core architectures with NoC

Alena Simalatsar, Stefanos Skalistis

The optimal deployment of data streaming applications onto multi-/many-core platform providing real-time guarantees requires to solve the application partitioning and placement, buffer allocation and task mapping and scheduling optimisation problem using t ...

Springer Int Publishing Ag2016

A Composition Theorem for Conical Juntas

Mika Tapani Göös

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2016

Fast and Robust Memory Reclamation for Concurrent Data Structures

Rachid Guerraoui, Mihail Igor Zablotchi, Oana Maria Balmau

In concurrent systems without automatic garbage collection, it is challenging to determine when it is safe to reclaim memory, especially for lock-free data structures. Existing concurrent memory reclamation schemes are either fast but do not tolerate proce ...

2016

Fast and Robust Memory Reclamation for Concurrent Data Structures

Rachid Guerraoui, Mihail Igor Zablotchi, Oana Maria Balmau

2016

A Thrifty Universal Construction

Rachid Guerraoui, Cheng Wang

A universal construction is an algorithm which transforms any sequential implementation of an object into a concurrent implementation of that same object in a linearizable and wait-free manner. Such constructions require underlying low-level universal shar ...

2015