Much of my research is captured by the following ongoing projects. On the theoretical computer science side, my focus is primarily on matching, clustering, and string algorithms with a special interest in stochastic problems. I consider these problems in the context of several application areas including e-commerce, democratic systems, fairness, accountability, and transparency, mechanism design for social good, and bioinformatics.



Redistricting and gerrymandering

I study many important problems surrounding political redistricting and gerrymandering. My work targets three broad areas:

  1. Evaluating the effects and longterm consequences of measuring gerrymandering and regulated redistricting (e.g., effects on voter incentives).
  2. Designing algorithmic solutions to generate "fairer" district maps with an eye toward fairness to individuals and communities rather than political parties.
  3. Designing alternative district-based systems (e.g., multi-member districts) and exploring what can be achieved in these systems.

Representative work

  • Centralized Fairness for Redistricting
    Seyed Esmaeili, Hayley Grape, and Brian Brubach
    (arxiv version)
  • Meddling Metrics: the Effects of Measuring and Constraining Partisan Gerrymandering on Voter Incentives
    Brian Brubach, Aravind Srinivasan, and Shawn Zhao
    ACM Conference on Economics and Computation (EC), 2020 (conference version)
    Also presented at Harvard CRCS Workshop on AI for Social Good, 2020 (abridged EC 2020 paper)
  • A Pairwise Fair and Community-preserving Approach to k-Center Clustering
    Brian Brubach, Darshan Chakrabarti, John P. Dickerson, Samir Khuller, Aravind Srinivasan, and Leonidas Tsepenekas
    International Conference on Machine Learning (ICML), 2020 (conference version)



Online matching and e-commerce

Online matching problem are ubiquitous in e-commerce. I study mostly stochastic variants of these problems that capture the uncertainty in the real world and making decisions based on predictions. Variants include random vertex arrival models and stochastic rewards (graph edges that only exist with some estimated probability).

Representative work

  • Follow your star: New frameworks for online stochastic matching with known and unknown patience
    Brian Brubach, Nathaniel Grammel, Will Ma, and Aravind Srinivasan
    International Conference on Artificial Intelligence and Statistics (AISTATS), 2021
  • Attenuate Locally, Win Globally: An Attenuation-based Framework for Online Stochastic Matching with Timeouts
    Brian Brubach, Karthik A. Sankararaman, Aravind Srinivasan, and Pan Xu
    Algorithmica, 2019
  • Online stochastic matching: New algorithms and bounds
    Brian Brubach, Karthik A. Sankararaman, Aravind Srinivasan, and Pan Xu
    Algorithmica, 2020 (update of our ESA 2016 paper)



Clustering

A lot of my work, including applications to redistricting and bioinformatics as well as approximation algorithms, falls under the broad category of clustering. I am especially interested in various definitions of fairness in clustering and stochastic problems. Much of my focus has been on the k-center problem and related radius-based approaches.

Representative work

  • Fair Labeled Clustering
    Seyed Esmaeili, Sharmila Duppala, John P. Dickerson, and Brian Brubach
    SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2022
  • Fair clustering under a bounded cost
    Seyed Esmaeili, Brian Brubach, Aravind Srinivasan, and John P. Dickerson
    Conference on Neural Information Processing Systems (NeurIPS), 2021
  • Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints
    Brian Brubach, Darshan Chakrabarti, John P. Dickerson, Aravind Srinivasan, and Leonidas Tsepenekas
    AAAI Conference on Artificial Intelligence (AAAI), 2021
  • Probabilistic Fair Clustering
    Seyed Esmaeili, Brian Brubach, Leonidas Tsepenekas, and John P. Dickerson
    Conference on Neural Information Processing Systems (NeurIPS), 2020
  • A Pairwise Fair and Community-preserving Approach to k-Center Clustering
    Brian Brubach, Darshan Chakrabarti, John P. Dickerson, Samir Khuller, Aravind Srinivasan, and Leonidas Tsepenekas
    International Conference on Machine Learning (ICML), 2020 (conference version)
  • Better Greedy Sequence Clustering with Fast Banded Alignment
    Brian Brubach, Jay Ghurye, Aravind Srinivasan, and Mihai Pop
    International Workshop on Algorithms in Bioinformatics (WABI), 2017 (conference version)



Emerging democratic systems and e-democracy

I study computational/algorithmic components of emerging democratic systems such as liquid democracy. This includes designing new algorithms for these systems as well as evaluating existing algorithms from a fairness, accountability, and transparency perspective.

Representative work

  • Characterizing Properties and Trade-offs of Centralized Delegation Mechanisms in Liquid Democracy
    Brian Brubach, Audrey Ballarin, and Heeba Nazeer
    ACM Conference on Fairness, Accountability, and Transparency (FAccT), 2022



Sequence comparison and clustering in metagenomics/genomics

I design and implement algorithms for metagenomics and genomics. My applied work has been in the area of 16S rRNA sequence clustering. On the theortical side, I am broadly interested in string algorithms for problems such as computing edit distance. I am also fascinated by measures of rearrangements between two strings and in particular, the Maximum Duo-preservation String Mapping (MPSM) problem.

Representative work

  • Better Greedy Sequence Clustering with Fast Banded Alignment
    Brian Brubach, Jay Ghurye, Aravind Srinivasan, and Mihai Pop
    International Workshop on Algorithms in Bioinformatics (WABI), 2017 (conference version)
  • A Succinct Four Russians Speedup for Edit Distance Computation and One-against-many Banded Alignment
    Brian Brubach and Jay Ghurye
    Symposium on Combinatorial Pattern Matching (CPM), 2018 (conference version)
  • Fast Matching-based Approximations for Maximum Duo-preservation String Mapping and its Weighted Variant
    Brian Brubach
    Symposium on Combinatorial Pattern Matching (CPM), 2018 (conference version)
  • Further Improvement in Approximating the Maximum Duo-Preservation String Mapping Problem
    Brian Brubach
    International Workshop on Algorithms in Bioinformatics (WABI), 2016 (slides)