Algorithmic Fairness and Social Choice
Core Stability for Public Projects
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
Approximately stable committee selection (with Zhihao Jiang and Kangning Wang) STOC '20.
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.
The core of the Participatory Budgeting problem (with Brandon Fain and Ashish Goel) WINE '16.
Group Fairness in Data Science Applications
Fairness in the assignment problem with uncertain priorities (with Z. Shen, Z. Wang, X. Zhu, and B. Fain) AAMAS '23
All politics is local: Redistricting via local fairness (with Shao-Heng Ko, Erin Taylor, and Pankaj Agarwal) NeurIPS '22
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
Centrality with diversity (with Liang Lyu, Brandon Fain and Kangning Wang) WSDM '21.
Proportionally fair clustering (with Xingyu Chen, Brandon Fain, and Charles Lyu) ICML '19.
Mechanisms for Social Choice
Optimal algorithms for multiwinner elections and the Chamberlin-Courant Rule (with Zeyu Shen and Kangning Wang) EC '21.
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.
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.
Incentives and Planning in Resource Allocation
Auctions and Pricing
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.
Predict and match: Prophet inequalities with uncertain supply. (with R. Alijani, S. Banerjee, S. Gollapudi, and K. Wang) SIGMETRICS '20.
The segmentation-thickness tradeoff in online marketplaces (with R. Alijani, S. Banerjee, K. Kollias, and S. Gollapudi) SIGMETRICS '19.
A simple mechanism for a budget constrained buyer (with Yu Cheng, Nick Gravin and Kangning Wang), WINE '18. (Best paper award)
Segmenting two-sided markets (with Siddhartha Banerjee, Kostas Kollias, and Sreenivas Gollapudi), WWW '17.
Scheduling and Routing
Online learning and bandits with queried hints. (with A. Bhaskara, S. Gollapudi, S. Im, and K. Kollias) ITCS '23
Competing against adaptive strategies in online learning with hints. (with Aditya Bhaskara) AISTATS '23
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.
Subtrajectory clustering: Models and algorithms. (with P. K. Agarwal, K. Fox, A. Nath, J. Pan, and E. Taylor) PODS '18.
I have only placed a few representative publications below. A complete list of my papers is available on DBLP and on Google Scholar.
Competitive algorithms from competitive equilibria (with Sungjin Im and Janardhan Kulkarni) J. ACM '18. (Also in STOC '14 and FOCS '15)
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.
SELFISHMIGRATE: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors (with S. Im, J. Kulkarni, and K. Pruhs), FOCS '14.
Modeling opinion dynamics in social networks (with Abhimanyu Das and Sreenivas Gollapudi), WSDM '14. Data sets used
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.
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.
Slides and Videos
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.