1 citations · 2 across the 6 of their papers we have counts for
3 papers · 1 filter
Quantum Advantage in Local Certification of Graph Properties
Benjamín Jáuregui, Masayuki Miyamoto
Local certification allows network vertices to verify global properties using certificates from an untrusted prover and communication with their neighbors. Its complexity is the ma…
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…