Concept

Nondeterministic algorithm

Publications associées (23)

A PCP Theorem for Interactive Proofs and Applications

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Optimal provision of concurrent primary frequency and local voltage control from a BESS considering variable capability curves: Modelling and experimental assessment

Mario Paolone, Sidi-Rachid Cherkaoui, Fabrizio Sossan, Antonio Zecchino, Zhao Yuan

This paper proposes a control method for battery energy storage systems (BESSs) to provide concurrent primary frequency and local voltage regulation services. The actual variable active and reactive power capability of the converter, along with the state-o ...

Elsevier2020

Local approximation of the Maximum Cut in regular graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...

ELSEVIER2020

Cooperative Data Exchange and Private Information Retrieval

Su Li

Coding techniques have been well studied and used for improving communication quality by combating noise and mitigating interference. Recently, it has been shown that the same coding techniques can also be exploited to further improve communication perform ...

EPFL2020

Local Approximation of the Maximum Cut in Regular Graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

Efficient Quantum Algorithms for GHZ and W States, and Implementation on the IBM Quantum Computer

Nicolas Macris, Marc-André Dupertuis, Clément Christian Javerzac, Chun Lam Chan, Alix Sébastien Thibaut Jeannerot

Efficient deterministic algorithms are proposed with logarithmic step complexities for the generation of entangled GHZ(N) and W-N states useful for quantum networks, and an implementation on the IBM quantum computer up to N = 16 is demonstrated. Improved q ...

WILEY2019

Deterministic Algorithms for Submodular Maximization Problems

Moran Feldman

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all c ...

ASSOC COMPUTING MACHINERY2018

Sequential Proximity: Towards Provably Scalable Concurrent Search Algorithms

Rachid Guerraoui, Vasileios Trigonakis, Karolos Antoniadis, Julien Michel Stainer

Establishing the scalability of a concurrent algorithm a priori, before implementing and evaluating it on a concrete multi-core platform, seems difficult, if not impossible. In the context of search data structures however, according to all practical work ...

Springer International Publishing2017

Just Sort It! A Simple and Effective Approach to Active Preference Learning

Matthias Grossglauser, Lucas Maystre

We address the problem of learning a ranking by using adaptively chosen pairwise comparisons. Our goal is to recover the ranking accurately but to sample the comparisons sparingly. If all comparison outcomes are consistent with the ranking, the optimal sol ...

2017

Efficient Algorithms for the Data Exchange Problem

Michael Christoph Gastpar

In this paper, we study the data exchange problem, where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Assuming that the file is broken into packets, the side-inform ...

Institute of Electrical and Electronics Engineers2016

Deriving a load model for the braking force on road bridges: Comparison between a deterministic and a probabilistic approach

Katrin Beyer, André-Gilles Dumont, Marc-Antoine Fénart

The current provisions for the braking force in the Eurocodes are much more demanding than previously enforced national codes from most European countries. Hence, safety assessments of existing bridges may show a lack of compliance with the new safety requ ...

Springer International Publishing2016

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

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

Inferring Scalability from Program Pseudocode

Mihai Letia

Recent trends have led hardware manufacturers to place multiple processing cores on a single chip, making parallel programming the intended way of taking advantage of the increased processing power. However, bringing concurrency to average programmers is c ...

EPFL2014

A Dual Algorithm for $ L _{ 1 } $ -Regularized Reconstruction of Vector Fields

Michaël Unser, Emrah Bostan, Pouya Dehghani Tafti

Recent advances in vector-field imaging have brought to the forefront the need for efficient denoising and reconstruction algorithms that take the physical properties of vector fields into account and can be applied to large volumes of data. With these req ...

IEEE2012

Randomized versus Deterministic Implementations of Concurrent Data Structures

Dan Alistarh

One of the key trends in computing over the past two decades has been increased distribution, both at the processor level, where multi-core architectures are now the norm, and at the system level, where many key services are currently distributed overmulti ...

EPFL2012

Sorting signed permutations by inversions in O(nlogn) time

Bernard Moret, Yu Lin, Krister Swenson, Vaibhav Rajan

The study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. After the initial breakthrough of Hannenhalli and Pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inv ...

2010

Model checking transactional memories

Rachid Guerraoui

Model checking transactional memories (TMs) is difficult because of the unbounded number, length, and delay of concurrent transactions, as well as the unbounded size of the memory. We show that, under certain conditions satisfied by most TMs we know of, th ...

Springer Verlag2010

Towards Global Bilevel Dynamic Optimization

Benoît Chachuat

The global solution of bilevel dynamic optimization problems is discussed. An overview of a deterministic algorithm for bilevel programs with nonconvex functions participating is given, followed by a summary of deterministic algorithms for the global solut ...

2009

Robust Non-Coherent Timing Acquisition in IEEE 802.15.4a IR-UWB Networks

Jean-Yves Le Boudec, Ruben Merz

Non-coherent energy-detection receivers are an attractive choice for IEEE 802.15.4a networks. They can exploit the ranging capabilities and the multipath resistance of impulse-radio ultra-wide band (IR-UWB) at a low complexity. However, IEEE 802.15.4a rece ...

2009