My
main research interest is in algorithm design and theoretical computer
science. I have worked on developing principled models and algorithms
for various application domains: Scheduling and resource allocation;
Data mining; Large-scale computing; Societal decision making;
Computational economics, and so on. My work builds on techniques in approximation and online algorithms; uses linear programming and duality in the analysis of algorithms; and uses game-theoretic techniques combined with data analysis for appropriate modeling.
I have placed a few representative publications below, grouped by application domain, which give a sampling
of my research interests and current directions.
A complete list of my papers is available on DBLP and on Google Scholar.
Most of my research has been funded by NSF through various awards. Some
of it has also been funded by the Sloan Foundation, Cisco, and the US Army.
Slides and Videos
Opinion Dynamics and Societal Decision Making
We develop game-theoretic models to reason about phenomena such as opinion formation, information
flow, and preference aggregation in society. We attempt to support the models by data
analysis and user experiments.
- Sequential deliberation for social choice (with Brandon Fain, Ashish Goel, and S. Sakshuwong), WINE '17.
- Collaborative optimization for collective decision-making in continuous spaces (with N. Garg, V. Kamble, A. Goel, and D. Marn) WWW '17.
- Modeling opinion dynamics in social networks (with Abhimanyu Das and Sreenivas Gollapudi), WSDM '14. Data sets used
-
On the precision of social and information networks (with Reza Bosagh Zadeh, Ashish Goel, and Aneesh Sharma), COSN '13.
-
Coevolutionary opinion formation games (with Kshipra Bhawalkar and Sreenivas Gollapudi), STOC '13.
Fair Allocations and Algorithmic Applications
We develop models for fair allocation
of resources, and polynomial time algoirthms for finding these
allocations. We show applications of such algorithms for
scheduling in data centers and multi-core architectures, as well as in social choice.
Pricing and Auction Design
We develop approximation algorithms and
mechanisms for auction design and pricing problems with side-constraints, such as
budgets and externalities. More recently, we have been developing models and algorithms for pricing in two-sided marketplaces.
- A simple mechanism for a budget constrained buyer (with Y. Cheng, N. Gravin and K. Wang), WINE '18. (Best paper award)
- Segmenting two-sided markets (with Siddhartha Banerjee, Kostas Kollias, and Sreenivas Gollapudi), WWW '17.
-
Optimal auctions with positive network externalities (with Nima Haghpanah, Nicole Immorlica, and Vahab Mirrokni) EC '11.
-
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.
-
Hybrid keyword search auctions (with Ashish Goel) WWW '09. (Winner of best paper award)
Stochastic Optimization and Bandit Problems
We develop approximation algorithms for
large classes of stochastic optimization and control-theoretic
problems, particularly the celebrated multi-armed bandit problems from
sequential decision theory.
Clustering and Network Design
We develop approximation algorithms for
several fundamental problems arising in clustering data and provisioning resources on a
network. We also develop practical clustering algorithms for problems
arising in gene expression and trajectory analysis.
- Subtrajectory clustering: Models and algorithms. (with P. K. Agarwal, K. Fox, A. Nath, J. Pan, and E.Taylor) PODS '18.
- Exceeding expectations and clustering uncertain data. (with Sudipto Guha), PODS '09.
- Constant factor approximation for the single sink edge installation problem (with Sudipto Guha and Adam Meyerson) STOC '01.
-
Cost-Distance: Two metric network design (with Adam Meyerson and Serge Plotkin) FOCS '00.
- Local search heuristics for k-medians and facility location problems (with V. Arya, N. Garg, R. Khandekar, A. Meyerson, and V. Pandit) STOC '01.
- Cancer characterization and feature set extraction via discriminative margin clustering (with R. Tibshirani and P. O. Brown) BMC Bioinformatics 5:21, 2004.
Algorithms for Efficient Data Processing
We develop efficient algorithms in
various large-scale computing models -- parallel and distributed
computing, sensor networks, continuous query optimization (data
streams), and I/O efficiency.
Copyright Notice:
Since most of these papers are published, the copyright has been
transferred to the respective publishers. The following is ACM's
copyright notice; other publishers have similar ones.
Copyright
© 20xx by the Association for Computing Machinery, Inc. Permission to
make digital or hard copies of part or all of this work for personal or
classroom use is granted without fee provided that copies are not made
or distributed for profit or commercial advantage and that new copies
bear this notice and the full citation on the first page. Copyrights
for components of this work owned by others than ACM must be honored.
Abstracting with credit is permitted.