[CS] Konstantinos Ameranis Candidacy Exam/Apr 17, 2025

[via cs]

This is an announcement of Konstantinos Ameranis's Candidacy Exam.
===============================================
Candidate: Konstantinos Ameranis

Date: Thursday, April 17, 2025

Time:  9 am CST

Remote Location: https://uchicago.zoom.us/j/93162763003?pwd=jAnHbTo1C9sXWAItxNoufQCEXeXW6N.1

Location: JCL 298

Title: From Theory to Practice: Designing and Implementing Fast First-Order Algorithms for Clustering and Learning over Networks

Abstract: Clustering problems over graphs have a long history with a variety of objective functions, heuristics and theoretical algorithms proposed. In this work we design and explore a class of algorithms that i) lend themselves to different objective formulations and different kinds of graphs, ii) possess strong theoretical approximation and convergence properties, and iii) perform well in practice even on large-scale instances. Formally, our max-flow-based framework achieves a provable $O(\log n)$ approximation for minimum ratio cut problems by employing a cut/matching game - a popular primal/dual algorithm originally designed for undirected  graphs. We show, both mathematically and empirically, how this framework can be extended to vertex-based cuts, directed graphs and hypergraphs. In this setting, we study an application of our framework to the detection of overlapping communities in social networks. Finally, we focus on practical experimentation on the cutting player strategies and how different parameters affect the quality and running time of our framework. Using a variety of real graphs from a multitude of domains, we explore how each formulation performs.

Advisor: Lorenzo Orecchia

Committee: Lorenzo Orecchia, Haotian Jiang, Mladen Kolar