research
∙
07/26/2023
Distributed Certification for Classes of Dense Graphs
A proof-labeling scheme (PLS) for a boolean predicate Π on labeled graph...
share
research
∙
04/25/2023
Anti-crossings occurrence as exponentially closing gaps in Quantum Annealing
This paper explores the phenomenon of avoided level crossings in quantum...
research
∙
04/05/2023
On the Power of Threshold-Based Algorithms for Detecting Cycles in the CONGEST Model
It is known that, for every k≥ 2, C_2k-freeness can be decided by a gene...
research
∙
01/27/2023
Energy-Efficient Distributed Algorithms for Synchronous Networks
We study the design of energy-efficient algorithms for the LOCAL and CON...
research
∙
08/04/2022
Computing Power of Hybrid Models in Synchronous Networks
During the last two decades, a small set of distributed computing models...
research
∙
06/30/2022
On graphs coverable by k shortest paths
We show that if the edges or vertices of an undirected graph G can be co...
research
∙
02/03/2022
On constant-time quantum annealing and guaranteed approximations for graph optimization problems
Quantum Annealing (QA) is a computational framework where a quantum syst...
research
∙
01/31/2022
Polynomial kernels for edge modification problems towards block and strictly chordal graphs
We consider edge modification problems towards block and strictly chorda...
research
∙
12/06/2021
A Meta-Theorem for Distributed Certification
Distributed certification, whether it be proof-labeling schemes, locally...
research
∙
05/18/2021
A cubic vertex-kernel for Trivially Perfect Editing
We consider the Trivially Perfect Editing problem, where one is given an...
research
∙
07/16/2020
Local Certification of Graphs with Bounded Genus
Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for aut...
research
∙
05/12/2020