<html>

<head>

<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">

</head>

<body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">

This is an announcement of Jafar Jafarov's Candidacy Exam.<br class="">

===============================================<br class="">

Candidate: Jafar Jafarov<br class="">

<br class="">

Date: Tuesday, March 08, 2022<br class="">

<br class="">

Time:  2 pm CST<br class="">

<br class="">

Remote Location: <a href="https://uchicago.zoom.us/j/99315816089?pwd=bjhvZGFFenlvYmI4bTlSRUU4Tzhodz09" class="">https://uchicago.zoom.us/j/99315816089?pwd=bjhvZGFFenlvYmI4bTlSRUU4Tzhodz09</a>  Meeting ID: 993 1581 6089 Passcode: 725555<br class="">

<br class="">

Title: Correlation Clustering with Local and Global Objectives<br class="">

<br class="">

Abstract: In the Correlation Clustering problem, we are given a graph with its edges labeled as "similar" and "dissimilar" by a noisy binary classifier, and the goal is to produce a clustering of the vertex set which matches with the edge labels as much as

 possible. Correlation Clustering has been mainly studied under two models where the input graph is (i) complete and unweighted, and (ii) arbitrary and weighted.<br class="">

<br class="">

In this thesis, we introduce a new model of Correlation Clustering that better captures real life instances. In this model the input graph is complete with bounded edge weights. We give an approximation algorithm and give a matching integrality gap instance.

 Moreover, we examine the model under a l_p objective which is a generalization of the standard Correlation Clustering objective, MinDisagree. We give an approximation algorithm and show an almost matching integrality gap for this objective.<br class="">

<br class="">

Advisors: Janos Simon and Yury Makarychev<br class="">

<br class="">

Committee Members: Yury Makarychev, Aaron Potechin, Konstantin Makarychev, and Janos Simon<br class="">

<br class="">

</body>

</html>