Publications related to Deterministic algorithm

Local approximation of the Maximum Cut in regular graphs

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

Symplectic dynamical low rank approximation of wave equations with random parameters

Fabio Nobile, Eleonora Musharbash, Eva Vidlicková

In this paper we propose a dynamical low-rank strategy for the approximation of second order wave equations with random parameters. The governing equation is rewritten in Hamiltonian form and the approximate solution is expanded over a set of 2S dynamical ...

2020

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

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

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

Nicolas Macris, Clément Christian Javerzac-Galy, Marc-André Dupertuis, Kenichi Komagata, Chun Lam Chan, Fabien Gremion, Jarla Thiesbrummel, Romain Fournier

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

Robust Multidimensional Pricing: Separation without Regret

Daniel Kuhn, Napat Rujeerapaiboon, Cagil Kocyigit

We study a robust monopoly pricing problem with a minimax regret objective, where a seller endeavors to sell multiple goods to a single buyer, only knowing that the buyer's values for the goods range over a rectangular uncertainty set. We interpret this pr ...

2018

Dynamical Low Rank approximation of PDEs with random parameters

Eleonora Musharbash

In this work, we focus on the Dynamical Low Rank (DLR) approximation of PDEs equations with random parameters. This can be interpreted as a reduced basis method, where the approximate solution is expanded in separable form over a set of few deterministic b ...

EPFL2017

Symplectic Dynamical Low Rank approximation of wave equations with random parameters

Fabio Nobile, Eleonora Musharbash

In this paper we propose a dynamical low-rank strategy for the approximation of second order wave equations with random parameters. The governing equation is rewritten in Hamiltonian form and the approximate solution is expanded over a set of

2S

dynamica ...

2017

Deterministic algorithm

Graph Chatbot

Chat with Graph Search

Local approximation of the Maximum Cut in regular graphs

Cooperative Data Exchange and Private Information Retrieval

Symplectic dynamical low rank approximation of wave equations with random parameters

Local Approximation of the Maximum Cut in Regular Graphs

New Graph Algorithms via Polyhedral Techniques

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

Deterministic Algorithms for Submodular Maximization Problems

Robust Multidimensional Pricing: Separation without Regret

Dynamical Low Rank approximation of PDEs with random parameters

Symplectic Dynamical Low Rank approximation of wave equations with random parameters

Cooperative Data Exchange and Private Information Retrieval

Symplectic Dynamical Low Rank approximation of wave equations with random parameters

New Graph Algorithms via Polyhedral Techniques

Deterministic Algorithms for Submodular Maximization Problems

Symplectic dynamical low rank approximation of wave equations with random parameters

Dynamical Low Rank approximation of PDEs with random parameters

Robust Multidimensional Pricing: Separation without Regret

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

Local approximation of the Maximum Cut in regular graphs

Local Approximation of the Maximum Cut in Regular Graphs