Research Projects

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.

Older Publications

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.