research
∙
09/09/2023
Local Certification of Some Geometric Intersection Graph Classes
In the context of distributed certification, the recognition of graph cl...
share
research
∙
09/04/2023
Dynamical Stability of Threshold Networks over Undirected Signed Graphs
In this paper we study the dynamic behavior of threshold networks on und...
research
∙
09/04/2023
Local Certification of Majority Dynamics
In majority voting dynamics, a group of n agents in a social network are...
research
∙
07/26/2023
Distributed Certification for Classes of Dense Graphs
A proof-labeling scheme (PLS) for a boolean predicate Π on labeled graph...
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
∙
12/06/2021
Distributed Interactive Proofs for the Recognition of Some Geometric Intersection Graph Classes
A graph G=(V,E) is a geometric intersection graph if every node v ∈ V is...
research
∙
12/06/2021
A Meta-Theorem for Distributed Certification
Distributed certification, whether it be proof-labeling schemes, locally...
research
∙
08/06/2021
On the complexity of the generalized Q2R automaton
We study the dynamic and complexity of the generalized Q2R automaton. We...
research
∙
07/30/2021
Generating Boolean Functions on Totalistic Automata Networks
We consider the problem of studying the simulation capabilities of the d...
research
∙
12/06/2020
Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
We present compact distributed interactive proofs for the recognition of...
research
∙
07/16/2020
Local Certification of Graphs with Bounded Genus
Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for aut...
research
∙
06/29/2020
Shared vs Private Randomness in Distributed Interactive Proofs
In distributed interactive proofs, the nodes of a graph G interact with ...
research
∙
05/24/2020
On the impact of treewidth in the computational complexity of freezing dynamics
An automata network is a network of entities, each holding a state from ...
research
∙
05/12/2020
Compact Distributed Certification of Planar Graphs
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the exist...
research
∙
12/06/2019
On the Complexity of the Stability Problem of Binary Freezing Totalistic Cellular Automata
In this paper we study the family of two-state Totalistic Freezing Cellu...
research
∙
10/24/2019
On the Complexity of Asynchronous Freezing Cellular Automata
In this paper we study the family of freezing cellular automata (FCA) in...
research
∙
04/22/2019
Computational Complexity of Biased Diffusion Limited Aggregation
Diffusion-Limited Aggregation (DLA) is a cluster growth model that consi...
research
∙
04/22/2019
Computational Complexity of Restricted Diffusion Limited Aggregation
We introduce a restricted version of the Diffusion Limited Aggregation (...
research
∙
10/30/2017
Finding Connected Secluded Subgraphs
Problems related to finding induced subgraphs satisfying given propertie...
research
∙
10/08/2015