Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (32)

TimeEvolver: A program for time evolution with improved error bound

Sebastian Zell

We present TimeEvolver, a program for computing time evolution in a generic quantum system. It relies on well-known Krylov subspace techniques to tackle the problem of multiplying the exponential of a large sparse matrix iH, where His the Hamiltonian, with ...

ELSEVIER2022

On the robustness of the metric dimension of grid graphs to adding a single edge

Patrick Thiran, Gergely Odor, Satvik Mehul Mashkaria

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to t ...

2022

Inter-actions parallel execution on GPU from high-level dataflow synthesis

Marco Mattavelli, Simone Casale Brunet, Aurélien François Gilbert Bloch

Recent GPU architectures make available numbers of parallel processing units that exceed by orders of magnitude the ones offered by CPU architectures. Whereas programs written using dataflow programming languages are well suited for programming heterogeneo ...

IEEE2022

How to Match in Modern Computational Settings

Buddhima Ruwanmini Gamlath Gamlath Ralalage

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information. First, we consider two stochastic models called query-commit and price-of-information where the algo ...

EPFL2021

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Adam Teodor Polak

One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Adaptive majority problems for restricted query graphs and for weighted sets

Doemoetoer Palvoelgyi, Balázs Keszegh, Abhishek Methuku

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

ELSEVIER2021

Representation Learning for Multi-relational Data

Eda Bayram

Recent years have witnessed a rise in real-world data captured with rich structural information that can be better depicted by multi-relational or heterogeneous graphs. However, research on relational representation learning has so far mostly focused on th ...

EPFL2021

Atomic subgraphs and the statistical mechanics of networks

Sofia Charlotta Olhede

We develop random graph models where graphs are generated by connecting not only pairs of vertices by edges, but also larger subsets of vertices by copies of small atomic subgraphs of arbitrary topology. This allows for the generation of graphs with extens ...

2021

On Representation Learning for Scientific News Articles Using Heterogeneous Knowledge Graphs

Karl Aberer, Panagiotis Smeros, Angeliki Romanou

In the era of misinformation and information inflation, the credibility assessment of the produced news is of the essence. However, fact-checking can be challenging considering the limited references presented in the news. This challenge can be transcended ...

ASSOC COMPUTING MACHINERY2021

Propagation on Multi-relational Graphs for Node Regression

Eda Bayram

Recent years have witnessed a rise in real-world data captured with rich structural information that can be conveniently depicted by multi-relational graphs. While inference of continuous node features across a simple graph is rather under-studied by the c ...

Springer, Cham2022

Towards Tight Bounds for Spectral Sparsification of Hypergraphs

Mikhail Kapralov, Jakab Tardos

Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applicati ...

ASSOC COMPUTING MACHINERY2021

Holistic, Efficient, and Real-time Cleaning of Heterogeneous Data

Styliani Asimina Giannakopoulou

Data cleaning has become an indispensable part of data analysis due to the increasing amount of dirty data. Data scientists spend most of their time preparing dirty data before it can be used for data analysis. Existing solutions that attempt to automate t ...

EPFL2021

Page 2 sur 2