Shared randomness is a valuable resource in distributed computing, but what
happens when the shared random string can affect the inputs to the system?
Consider the class of distributed graph problems where the correctness of
solutions can be checked locally, known as Locally Checkable Labelings (LCL).
LCL problems have been extensively studied in the LOCAL model, where nodes
operate in synchronous rounds and have access only to local information. This
has led to intriguing insights regarding the power of private randomness. E.g.,
for certain round complexity classes, derandomization does not incur an
overhead (asymptotically).
This work considers a setting where the randomness is public. Recently, an
LCL problem for which shared randomness can reduce the round complexity was
discovered by Balliu et al. (2024). This result applies to inputs set
obliviously of the shared randomness, which may not always be a plausible
assumption.
We define a model where the inputs can be adversarially chosen, even based on
the shared randomness, which we now call preset public coins. We study LCL
problems in the preset public coins model, under assumptions regarding the
computational power of the adversary that selects the input. We show
connections to hardness in the class TFNP. Our results are:
1. Assuming the existence of a hard-on-average problem in TFNP (which follows
from fairly benign cryptographic assumptions), we show an LCL problem that, in
the preset public coins model, demonstrates a gap in the round complexity
between polynomial-time adversaries and unbounded ones.
2. If there exists an LCL problem for which the error probability is
significantly higher when facing unbounded adversaries, then a hard-on-average
problem in TFNP/poly must exist.

Este artículo explora los viajes en el tiempo y sus implicaciones.

Descargar PDF: