5 papers · 1 filter
A Simple Construction of Locally Checkable Problems Filling the LOCAL Complexity Gaps in Graphs with Arbitrary Large Degrees
Filippo Casagrande, Pierre Fraigniaud, Benjamin Jauregui +1
We show that the complexity gaps in the round complexities of locally checkable labeling (LCL) problems are not due to the fact that solutions to LCL problems must be locally check…
Distributed Statistical Zero-Knowledge Proofs via Sumcheck
Benjamin Jauregui, Masayuki Miyamoto
We study distributed zero-knowledge proofs, introduced by Bick, Kol, and Oshman (SODA 2022). While distributed interactive proofs have advanced rapidly, general-purpose techniques…
Deterministic Distributed DFS and Other Problems via Cycle Separators in Planar Graphs
Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport
One of the most basic techniques in algorithm design consists of breaking a problem into subproblems and then proceeding recursively. In the case of graph algorithms, one way to im…
Strong and Hiding Distributed Certification of Bipartiteness
Benjamin Jauregui, Augusto Modanese, Pedro Montealegre +1
In this paper, we study the problem of certifying whether a graph is bipartite (i.e. -colorable) with a locally checkable proof (LCP) that is able to hide a -coloring from th…
Local Certification of Some Geometric Intersection Graph Classes
Benjamín Jauregui, Pedro Montealegre, Diego Ramírez-Romero +1
In the context of distributed certification, the recognition of graph classes has started to be intensively studied. For instance, different results related to the recognition of p…