My current projects on resource allocation and provisioning fall in two broad categories.
My research focuses on defining and achieving fairness across various societal decision making scenarios, including allocating resources, collective decision making through elections, and partitioning geographic areas fairly through redistricting. We aim to define novel fairness concepts, prove their existence, and explore their computational complexity. A central fairness concept we explore is proportionality or core-stability, which ensures groups of people receive resources or representation proportional to what they are entitled to.
Group fairness and multi-criteria optimization in school assignment. (with Santhini K. A., Meghana Nasre, and Govind S. Sankar) FORC '25
Fair division via the cake-cutting share (with Yannan Bai, Yiheng Shen, and Ian Zhang) AAAI '25
Individual fairness in graph decomposition. (with Govind S. Sankar) ICML '24
Fairness in the assignment problem with uncertain priorities (with Z. Shen, Z. Wang, X. Zhu, and B. Fain) AAMAS '23
Fair multiwinner elections with allocation constraints. (with Ivan-Aleksandar Mavrov and Yiheng Shen) EC '23
Auditing for core stability in Participatory Budgeting (with Yiheng Shen and Kangning Wang) WINE '22
Approximate core for committee selection via multilinear extension and market clearing (with Y. Shen, K. Wang, and Z.Wang) SODA '22
All politics is local: Redistricting via local fairness (with Shao-Heng Ko, Erin Taylor, and Pankaj Agarwal) NeurIPS '22
Approximately stable committee selection (with Zhihao Jiang and Kangning Wang) STOC '20
My research addresses the question: How do parties with incomplete and asymmetric information collaborate or compete to achieve their respective optimization objectives? This issue appears frequently in various practical contexts, for example, when ML models are used to make optimization decisions on settings they have not been trained on; when recruiters evaluate candidates without full knowledge of their capabilities; or when social planners make choices with incomplete preference information. A broad sub-theme is persuasion, which studies the behavior of an optimizer or learner (like language model or recruiter or social planner) when information is selectively revealed to it.
Combinatorial optimization via LLM-driven iterated fine-tuning. (with Pranjal Awasthi, Sreenivas Gollapudi, and Ravi Kumar).
The limits of interval-regulated price discrimination. (with Yiheng Shen and Renzhe Xu).
The price of competitive information disclosure (with S. Banerjee, Y. Shen, and K. Wang).
Metric distortion of small-group deliberation (with Ashish Goel and Mohak Goyal) STOC '25
Online distributed queue length estimation. (with A. Bhaskara, S. Gollapudi, S. Im, and K. Kollias) ACDA '25.
Differential privacy with multiple selections. (with A. Goel, Z. Jiang, A. Korolova, and S. Sarmasarkar) FORC '25 (empirical companion)
Majorized Bayesian persuasion and fair selection. (with S. Banerjee, Y. Shen, and K. Wang). SODA '25
Fair price discrimination. (with S. Banerjee, Y. Shen, and K. Wang). SODA '24
Data exchange markets via utility balancing. (with A. Bhaskara, S. Gollapudi, S. Im, K. Kollias, and G. S. Sankar) WWW '24
Online learning and bandits with queried hints. (with A. Bhaskara, S. Gollapudi, S. Im, and K. Kollias) ITCS '23
Optimal price discrimination for randomized mechanisms. (with Shao-Heng Ko) EC '22
The limits of an information intermediary in auction design (with R. Alijani, S. Banerjee, and K. Wang) EC '22
A complete list of my papers is available on DBLP and on Google Scholar.
Competing against adaptive strategies in online learning with hints. (with Aditya Bhaskara) AISTATS '23
Locally fair partitioning. (with Pankaj K. Agarwal, Shao-Heng Ko, and Erin Taylor) AAAI '22
Robust allocations with diversity constraints (with Zeyu Shen, Lodewijk Gelauff, Ashish Goel, and Aleksandra Korolova) NeurIPS '21
Fair for all: Best effort fairness in classification (with A. K. Krishnaswamy, Z. Jiang, K. Wang, and Y. Cheng) AISTATS '21
Optimal algorithms for multiwinner elections and the Chamberlin-Courant Rule (with Zeyu Shen and Kangning Wang) EC '21
Centrality with diversity (with Liang Lyu, Brandon Fain and Kangning Wang) WSDM '21.
Adaptive probing policies for shortest path routing (with A. Bhaskara, K. Kollias, and S. Gollapudi) NeurIPS '20.
Dynamic weighted fairness with minimal disruptions (with Sungjin Im, Ben Moseley, and Kirk Pruhs). SIGMETRICS '20.
Predict and match: Prophet inequalities with uncertain supply. (with R. Alijani, S. Banerjee, S. Gollapudi, and K. Wang) SIGMETRICS '20.
Concentration of distortion: The value of extra voters in randomized social choice (with B. Fain and W. Fan) IJCAI '20.
Improved metric distortion for deterministic social choice rules (with Kangning Wang) EC '19.
Iterative local voting for collective decision-making in continuous spaces (with N. Garg, V. Kamble, A. Goel, and D. Marn) JAIR '19 (also in WWW '17).
Random dictatorship with random referee: Constant sample complexity mechanisms for social choice (with B. Fain, A. Goel, and N. Prabhu) AAAI '19.
The segmentation-thickness tradeoff in online marketplaces (with R. Alijani, S. Banerjee, K. Kollias, and S. Gollapudi) SIGMETRICS '19.
Proportionally fair clustering (with Xingyu Chen, Brandon Fain, and Charles Lyu) ICML '19.
Group fairness in committee selection (with Yu Cheng, Zhihao Jiang, and Kangning Wang) EC '19.
Fair allocations of indivisible public goods (with Brandon Fain and Nisarg Shah) EC '18.
A simple mechanism for a budget constrained buyer (with Yu Cheng, Nick Gravin and Kangning Wang), WINE '18. (Best paper award)
Subtrajectory clustering: Models and algorithms. (with P. K. Agarwal, K. Fox, A. Nath, J. Pan, and E. Taylor) PODS '18.
Competitive algorithms from competitive equilibria (with Sungjin Im and Janardhan Kulkarni) J. ACM '18. (Also in STOC '14 and FOCS '15)
Segmenting two-sided markets (with Siddhartha Banerjee, Kostas Kollias, and Sreenivas Gollapudi), WWW '17.
Metric distortion of social choice rules: Lower bounds and fairness properties (with A. K. Krishnaswamy and A. Goel) EC '17.
Sequential deliberation for social choice (with Brandon Fain, Ashish Goel, and Sukolsak Sakshuwong) WINE '17.
ROBUS: Fair cache allocation for data parallel workloads (with Mayuresh Kunjir, Brandon Fain, and Shivnath Babu) SIGMOD '17.
Parallel algorithms for constructing range and nearest-neighbor search data structures (with P. K. Agarwal, K. Fox, and A. Nath) PODS '16.
Massively parallel algorithms for computing TIN DEMs and contour trees for large terrains (with P. K. Agarwal, K. Fox, and A. Nath) ACM GIS '16.
The core of the Participatory Budgeting problem (with Brandon Fain and Ashish Goel) WINE '16.
SELFISHMIGRATE: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors (with S. Im, J. Kulkarni, and K. Pruhs), FOCS '14.
Stochastic regret minimization via Thompson sampling (with Sudipto Guha) COLT '14. See this related blog post on our conjecture.
Coordination mechanisms from (almost) all scheduling policies (with Sayan Bhattacharya, Sungjin Im, and Janardhan Kulkarni) ITCS '14.
Modeling opinion dynamics in social networks (with Abhimanyu Das and Sreenivas Gollapudi), WSDM '14. Data sets used
Coevolutionary opinion formation games (with Kshipra Bhawalkar and Sreenivas Gollapudi), STOC '13.
On the precision of social and information networks (with Reza Bosagh Zadeh, Ashish Goel, and Aneesh Sharma), COSN '13.
Approximation algorithms for Bayesian multi-armed bandit problems (with Sudipto Guha) combines papers in STOC '07, ICALP '09, and APPROX '13.
Adaptive uncertainty resolution in Bayesian combinatorial optimization (with Sudipto Guha) TALG '12 (also in SODA '07).
Optimal auctions with positive network externalities (with Nima Haghpanah, Nicole Immorlica, and Vahab Mirrokni) EC '11.
Approximation algorithms for restless bandit problems (with Sudipto Guha and Peng Shi) J. ACM '10 (also in FOCS '07 and SODA '09).
Budget constrained auctions with heterogeneous items (with Sayan Bhattacharya, Gagan Goel, and Sreenivas Gollapudi) STOC '10.
Incentive compatible budget elicitation in multi-unit auctions (with Sayan Bhattacharya, Vincent Conitzer, and Lirong Xia) SODA '10.
Exceeding expectations and clustering uncertain data. (with Sudipto Guha), PODS '09.
Hybrid keyword search auctions (with Ashish Goel) WWW '09. (Winner of best paper award)
Optimization of continuous queries with shared expensive filters (with Utkarsh Srivastava and Jennifer Widom) PODS '07.
Energy efficient monitoring of extreme values in sensor networks (with Adam Silberstein and Jun Yang) SIGMOD '06.
Asking the right questions: Model driven optimization using probes (with Ashish Goel and Sudipto Guha), PODS '06.
Adaptive ordering of pipelined stream filters (with Shivnath Babu, Rajeev Motwani, Itaru Nishizawa, and Jennifer Widom) SIGMOD '04.
Cancer characterization and feature set extraction via discriminative margin clustering (with R. Tibshirani and P. O. Brown) BMC Bioinformatics 5:21, 2004.
Constant factor approximation for the single sink edge installation problem (with Sudipto Guha and Adam Meyerson) STOC '01.
Local search heuristics for k-medians and facility location problems (with V. Arya, N. Garg, R. Khandekar, A. Meyerson, and V. Pandit) STOC '01.
Cost-Distance: Two metric network design (with Adam Meyerson and Serge Plotkin) FOCS '00.
I/O-complexity of graph algorithms (with Abhiram Ranade) SODA '99.
Talk on Stochastic Optimization at the Algorithms and Uncertainty Boot Camp, Simons Institute, 2016
Talk on Multidimensional scheduling at the Optimization and Decision Making under Uncertainty Workshop, Simons Institute, 2016.
Slides from my tutorial on Prophet Inequalities and Stochastic Optimization. Based on my joint work with Sudipto Guha.