Seminario DISC: ¿Es computable un algoritmo local?

En este seminario del Doctorado en Ingeniería de Sistema Complejos (DISC) se explorará una pregunta fundamental sobre el modelo LOCAL: ¿qué ocurre cuando distinguimos entre algoritmos que utilizan funciones arbitrarias y aquellos que requieren funciones computables?

A partir del estudio de los problemas de etiquetado localmente verificables (LCL), se mostrará que esta distinción puede tener consecuencias importantes en la complejidad de los algoritmos, especialmente cuando los nodos no conocen el tamaño de la red en la que operan.

La presentación abordará la relación entre computabilidad, conocimiento del tamaño de la red y complejidad distribuida, mostrando cómo estas condiciones pueden cambiar significativamente el número de rondas necesarias para resolver un problema.

Expone:

• Augusto Modanese, CISPA Helmholtz Center for Information Security, Germany.