Paraguay cuenta con nuevo Master en Ciencias de la Computación
Fabricio Mendoza realizó la defensa de su tesis “Optimality of Spectral Sparsification in Distributed Systems with Applications to Data Clustering” de la Maestría en Ciencias de la Computación de la Facultad Politécnica de la Universidad Nacional de Asunción (FP – UNA). La técnica de Dispersión Espectral es utilizada en una variedad de aplicaciones tales como resolución de Sistemas Laplacianos y búsqueda de multicortes en un grafo mediante sus propiedades espectrales.
El trabajo demuestra que la dispersión espectral funciona bajo la suposición de que los datos de entrada están distribuidos en diferentes sitios. Para lograr eso, se introdujo una herramienta matemática que captura la noción de solapamiento de datos entre diferentes sitios en un sistema distribuido.
Los grafos son objetos matemáticos utilizados en distintas áreas de las ciencias para modelar relaciones discretas entre entidades de un sistema. Los grafos están compuestos por vértices, los cuales representan las entidades del sistema que se desea modelar, y aristas las cuales representan la relación existente en las entidades.
La gran cantidad de datos que se producen hoy en día llevan a la construcción de grafos densos, los cuales poseen una enorme cantidad de aristas. Razón por la cual existen técnicas para construir aproximaciones de grafos con una menor cantidad de aristas, también llamados grafos dispersos. Una de estas técnicas es la dispersión espectral.
Además, la tesis analiza los modelos de comunicación, los cuales funcionan como herramientas teóricas para estudiar algoritmos que trabajan con datos distribuidos. En particular, se enfoca en el modelo Number-On-Forehead, el cual es una poderosa herramienta con aplicaciones teóricas en complejidad de circuitos.
Finalmente, la investigación desarrolló un protocolo que computa el algoritmo de agrupamiento espectral, el cual se fundamenta en el multicorte de un grafo, en el modelo Number-On-Forehead bajo la suposición de que existen datos solapados.
El postgrado fue financiado por el Consejo Nacional de Ciencia y Tecnología (CONACYT) a través del Programa PROCIENCIA con apoyo del FEEI.
