Sara Ahmadian — accepted AI-conference papers

2025

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility

Matthew Fahrbach, Srikumar Ramalingam, Morteza Zadimoghaddam, Sara Ahmadian, Gui Citovsky, Giulia DeSalvo

NeurIPS 2025poster

This work studies a novel subset selection problem called *max-min diversification with monotone submodular utility* (MDMS), which has a wide range of applications in machine learning, e.g., data sampling and feature selection. Given a set of points in a metric space, the goal of MDMS is to maximize…

Cited by 0 Source ↗Scholar ↗

2025

Generalized Top-k Mallows Model for Ranked Choices

Shahrzad Haddadan, Sara Ahmadian

NeurIPS 2025spotlight

The classic Mallows model is a foundational tool for modeling user preferences. However, it has limitations in capturing real-world scenarios, where users often focus only on a limited set of preferred items and are indifferent to the rest. To address this, extensions such as the top-$k$ Mallows mod…

Cited by 0 Source ↗Scholar ↗

2025

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation

Sara Ahmadian, Edith Cohen, Uri Stemmer

NeurIPS 2025poster

Dimensionality reduction via linear sketching is a powerful and widely used technique, but it is known to be vulnerable to adversarial inputs. We study the \emph{black-box adversarial setting}, where a fixed, hidden sketching matrix $A \in \mathbb{R}^{k \times n}$ maps high-dimensional vectors $\bol…

Cited by 0 Source ↗Scholar ↗

2024

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs

Sara Ahmadian, Edith Cohen

ICML 2024poster

Cardinality sketches are popular data structures that enhance the efficiency of working with large data sets. The sketches are randomized representations of sets that are only of logarithmic size but can support set merges and approximate cardinality (i.e., distinct count) queries. When queries are…

Cited by 3 Source ↗PDF ↗Scholar ↗

2023

Improved Approximation for Fair Correlation Clustering

Sara Ahmadian, Maryam Negahbani

AISTATS 2023poster

Correlation clustering is a ubiquitous paradigm in unsupervised machine learning where addressing unfairness is a major challenge. Motivated by this, we study fair correlation clustering where the data points may belong to different protected groups and the goal is to ensure fair representation of a…

Cited by 15 Source ↗PDF ↗code ↗Scholar ↗

2023

KwikBucks: Correlation Clustering with Cheap-Weak and Expensive-Strong Signals

Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachandran, Seyed Mehran Kazemi

ICLR 2023poster

The unprecedented rate at which the sizes of machine learning (ML) models are growing necessitates novel approaches to enable efficient and scalable solutions. We contribute to this line of work by studying a novel version of the Budgeted Correlation Clustering problem (\bcc) where along with a limi…

Cited by 23 Source ↗PDF ↗Scholar ↗

2021

Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT

Vaggos Chatziafratis, Mohammad Mahdian, Sara Ahmadian

AISTATS 2021poster

In this paper, we study a number of well-known combinatorial optimization problems that fit in the following paradigm: the input is a collection of (potentially inconsistent) local relationships between the elements of a ground set (e.g., pairwise comparisons, similar/dissimilar pairs, or ancestry s…

Cited by 13 Source ↗PDF ↗Scholar ↗

2020

Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection

Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ahmadian, Alessandro Epasto +1

AISTATS 2020poster

Hierarchical Clustering is an unsupervised data analysis method which has been widely used for decades. Despite its popularity, it had an underdeveloped analytical foundation and to address this, Dasgupta recently introduced an optimization viewpoint of hierarchical clustering with…

Cited by 20 Source ↗PDF ↗Scholar ↗

2020

Fair Correlation Clustering

Sara Ahmadian, Alessandro Epasto, Ravi Kumar, Mohammad Mahdian

AISTATS 2020poster

In this paper, we study correlation clustering under fairness constraints. Fair variants of $k$-median and $k$-center clustering have been studied recently, and approximation algorithms using a notion called fairlet decomposition have been proposed. We obtain approximation algorithms for fair corr…

Cited by 87 Source ↗PDF ↗code ↗Scholar ↗

2020

Fair Hierarchical Clustering

Sara Ahmadian, Alessandro Epasto, Marina Knittel, Ravi Kumar, Mohammad Mahdian, Benjamin Moseley +3

NeurIPS 2020poster

As machine learning has become more prevalent, researchers have begun to recognize the necessity of ensuring machine learning systems are fair. Recently, there has been an interest in defining a notion of fairness that mitigates over-representation in traditional clustering.

Cited by 66 Source ↗PDF ↗Scholar ↗