Zobrazeno 1 - 10
of 1 215
pro vyhledávání: '"Balliu A"'
Autor:
Balliu, Alkida, Brandt, Sebastian, Coiteux-Roy, Xavier, d'Amore, Francesco, Equi, Massimo, Gall, François Le, Lievonen, Henrik, Modanese, Augusto, Olivetti, Dennis, Renou, Marc-Olivier, Suomela, Jukka, Tendick, Lucas, Veeren, Isadora
We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prior work, such a separation was known only for an artificial graph probl
Externí odkaz:
http://arxiv.org/abs/2411.03240
We study the awake complexity of graph problems that belong to the class O-LOCAL, which includes a subset of problems solvable by sequential greedy algorithms, such as $(\Delta+1)$-coloring and maximal independent set. It is known from previous work
Externí odkaz:
http://arxiv.org/abs/2410.20499
In the past few years, a successful line of research has lead to lower bounds for several fundamental local graph problems in the distributed setting. These results were obtained via a technique called round elimination. On a high level, the round el
Externí odkaz:
http://arxiv.org/abs/2410.20224
Publikováno v:
IEEE Secure Development Conference 2024
Many applications benefit from computations over the data of multiple users while preserving confidentiality. We present a solution where multiple mutually distrusting users' data can be aggregated with an acceptable overhead, while allowing users to
Externí odkaz:
http://arxiv.org/abs/2410.10574
Autor:
Balliu, Alkida, Fraigniaud, Pierre, Lambein-Monette, Patrick, Olivetti, Dennis, Rabie, Mikael
We revisit asynchronous computing in networks of crash-prone processes, under the asynchronous variant of the standard LOCAL model, recently introduced by Fraigniaud et al. [DISC 2022]. We focus on the vertex coloring problem, and our contributions c
Externí odkaz:
http://arxiv.org/abs/2408.10971
Prototype pollution is a recent vulnerability that affects JavaScript code, leading to high impact attacks such as arbitrary code execution. The vulnerability is rooted in JavaScript's prototype-based inheritance, enabling attackers to inject arbitra
Externí odkaz:
http://arxiv.org/abs/2407.10812
Autor:
Balliu, Alkida, Ghaffari, Mohsen, Kuhn, Fabian, Modanese, Augusto, Olivetti, Dennis, Rabie, Mikaël, Suomela, Jukka, Uitto, Jara
By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is locally checkable labeling problems (LCLs), introduced by Naor and Stockme
Externí odkaz:
http://arxiv.org/abs/2407.05445
Autor:
Balliu, Alkida, Brandt, Sebastian, Kuhn, Fabian, Nowicki, Krzysztof, Olivetti, Dennis, Rotenberg, Eva, Suomela, Jukka
Algorithms with advice have received ample attention in the distributed and online settings, and they have recently proven useful also in dynamic settings. In this work we study local computation with advice: the goal is to solve a graph problem $\Pi
Externí odkaz:
http://arxiv.org/abs/2405.04519
The node-averaged complexity of a problem captures the number of rounds nodes of a graph have to spend on average to solve the problem in the LOCAL model. A challenging line of research with regards to this new complexity measure is to understand the
Externí odkaz:
http://arxiv.org/abs/2405.01366
We study the complexity of fundamental distributed graph problems in the recently popular setting where information about the input graph is available to the nodes before the start of the computation. We focus on the most common such setting, known a
Externí odkaz:
http://arxiv.org/abs/2405.00825