Clustering is a fundamental task in machine learning and data analysis, but it frequently fails to provide fair representation for various marginalized communities defined by multiple protected attributes -- a shortcoming often caused by biases in the training data. As a result, there is a growing need to enhance the fairness of clustering outcomes, ideally by making minimal modifications, possibly as a post-processing step after conventional clustering. A recent work initiated the study of closest fair clustering, though in a restricted scenario where data points belong to only two groups. In practice, however, data points are typically characterized by many groups, reflecting diverse protected attributes such as age, ethnicity, gender, etc. In this work, we generalize the study of the closest fair clustering problem to settings with an arbitrary number (more than two) of groups. We begin by showing that the problem is NP-hard even when all groups are of equal size -- a stark contrast with the two-group case, for which an exact algorithm exists. Next, we propose near-linear time approximation algorithms that efficiently handle arbitrary-sized multiple groups. Leveraging our closest fair clustering algorithms, we further achieve improved approximation guarantees for the fair correlation clustering problem, advancing the state-of-the-art results. Additionally, we are the first to provide approximation algorithms for the fair consensus clustering problem involving multiple (more than two) groups.

The rank aggregation problem, seeks to combine multiple rank orderings of the same set of candidates into a single consensus ordering. Such problems arise in diverse domains, including web search, employment, college admissions, and voting. In this work we focus on the 1-median objective: given a set of m rankings over [n], the goal is to compute a ranking that minimizes the sum of its distances to all input rankings. We study rank aggregation under several classical distance metrics: Ulam distance, Spearman’s footrule, Hamming distance, and Kendall-tau, as well as their weighted variants. Our contributions begin with a novel unified framework that identifies a key structural property: it suffices to focus on a small subset of rankings (of size three or five), where the corresponding local one-median provides a good approximation to the global median. This principle extends across these distance measures, yielding a general algorithmic framework for weighted rank aggregation. Building on this, we present a new approximation algorithm for rank aggregation under the Ulam distance that scales in the Massively Parallel Computation (MPC) model. Our algorithm computes a (2-α)-approximation, for a constant α > 0, to the 1-median in a constant number of rounds, using local memory sublinear in n (the size of a ranking) and total memory near linear in n. We further design new MPC approximation algorithms for Spearman’s footrule and for the element-weighted variants of Hamming and Kendall-tau distances. For each metric, we obtain a (2-ζ)-approximation, for a constant ζ > 0 (which may differ across metrics), to the 1-median in a constant number of rounds, using local memory sublinear in n and total memory linear or near-linear in n. Moreover, for the Ulam distance, where computing the 1-median is NP-hard [Fischer et al., ESA, 2025], we simplify and strengthen the analysis of Chakraborty et al. [ITCS 2023], obtaining an improved 1.968-approximation that further extends to the weighted setting.

Consensus clustering, a fundamental task in machine learning and data analysis, aims to aggregate multiple input clusterings of a dataset, potentially based on different non-sensitive attributes, into a single clustering that best represents the collective structure of the data. In this work, we study this fundamental problem through the lens of fair clustering, as introduced by Chierichetti et al. [NeurIPS’17], which incorporates the disparate impact doctrine to ensure proportional representation of each protected group in the dataset within every cluster. Our objective is to find a consensus clustering that is not only representative but also fair with respect to specific protected attributes. To the best of our knowledge, we are the first to address this problem and provide a constant-factor approximation. As part of our investigation, we examine how to minimally modify an existing clustering to enforce fairness – an essential postprocessing step in many clustering applications that require fair representation. We develop an optimal algorithm for datasets with equal group representation and near-linear time constant factor approximation algorithms for more general scenarios with different proportions of two group sizes. We complement our approximation result by showing that the problem is NP-hard for two unequal-sized groups. Given the fundamental nature of this problem, we believe our results on Closest Fair Clustering could have broader implications for other clustering problems, particularly those for which no prior approximation guarantees exist for their fair variants.

Run length limited (RLL) sequences and codes have been studied extensively in coding theory for a long time. Several kinds of weight constrained RLL codes have gained attentions recently owing to their applications, especially in DNA-based data storage. In this work, we revisit the old problem of constant weight RLL codes and provide new efficient encoding/decoding algorithms of these optimal codes. In particular, we rank/unrank all constant weight RLL sequences in a certain order, called$d$-Gray order, where the Hamming distance between two consecutive sequences in the list is at most$d$. The list of all constant weight RLL sequences is called a constant weight RLL$d$-Gray code.

Window Weight Limited (WWL) strings and codes have been studied recently owing to their various applications, including DNA based storage and energy-harvesting. In this work, we proposed to study a new coding scheme, called WWL Gray code. This is a list of WWL strings in Gray order, that is, the Hamming distance of two consecutive strings in the list is one. We are the first to investigate the WWL Gray codes with efficient rankinglunranking algorithms. We show that the WWL Gray codes are useful in designing robust positioning sequences. Note that the robust positioning sequences have attracted a lot of attentions recently owing to their numerous applications, including quantum communications and robot localization. In this work, using the WWL Gray codes, we obtain robust positioning sequences with less redundancy compared to the best known results.

Finding dense subgraphs from a large graph is a fundamental graph mining task with many applications. The notion is recently formulated of locally densest subgraph (LDS) is recently formulated to identify multiple dense subgraphs that cover different regions of a large graph. Informally, an LDS is a subgraph with the highest density in its local region. The state-of-the-art algorithm for computing top-k LDSes with the highest densities is LDS. It iteratively computes the densest subgraph and removes it from the graph, where all the computed densest subgraphs form the candidates of LDSes. Then, each candidate is verified through a costly maximum flow computation. Although advanced pruning techniques are proposed in LDS, the verification step is still time consuming especially for not-so-small k values. In this paper, we aim to improve the efficiency of finding top-k LDSes by designing verification-free approaches. Our algorithms are based on our observation that the set of maximal λ-compact subgraphs for all possible λ values form a hierarchical structure, and LDSes are simply leaves in the hierarchical structure. Thus, we propose a divide-and-conquer algorithm LDS-DC as well as an optimized algorithm LDS-Opt to efficiently identify top-k LDSes without constructing the entire hierarchical structure. Both of our algorithms have lower time complexities than LDS. Extensive empirical studies on real graphs show that our optimized algorithm LDS-Opt outperforms LDS for all k values, and the improvement is up-to several orders of magnitude.

The run length limited de Bruijn (RLLdB) sequences have been studied recently owing to their application in communication systems. In each RLLdB sequence, all length-k substrings are distinct and each substring is a run length limited sequence, where there are at most s consecutive symbol 0’s. In previous work, the maximal length RLLdB sequence was designed only for the case s = 1.In this work, we propose to study a more generalised problem of constrained de Bruijn sequence, called weight bounded run length limited de Bruijn (WRdB) sequence. In each WRdB sequence, all length-k substrings are distinct and each length-k substring satisfies both constraints: the number of consecutive symbol 0’s is at most s, and the number of symbol 1’s is at least l. We aim to design a WRdB sequence with maximal length in all cases.Firstly, we build a constrained de Bruijn graph that represents a WRdB sequence and use some properties of the graph to show an upper bound on the maximal length of the sequence. Next, using Lyndon words, we present a construction of a WRdB sequence. Finally, we compute the length of the constructed WRdB sequence and show that it has the maximal length.

The de Bruijn based timing and synchronization (dBTS) system has been proposed and studied recently for some channels require reliable synchronization, such as quantum communication. To avoid a long period of no-pulse in the dBTS system, we propose to study the run length limited de Bruijn sequences which not only are run length limited sequences but also can be used to locate the location of any sub-string. Such subjects are expected to have various applications and they also present some interesting theoretical questions in combinatorics, algorithms and coding theory.In this paper, we are the first to provide an explicit formula of the maximal length of the run length limited de Bruijn sequences. Besides that, using Lyndon words, we present an efficient construction of a run length limited de Bruijn sequence with the maximal length. Furthermore, we also provide a sub-linear decoding algorithm which can locate the position of an arbitrary sub-string.