Research Experience

My research work at Stanford may be broadly classfied into two groups a) social choice and b) machine learing focussing on the prediction of multiple items in the context of differential privacy.

1. Machine Learning

In this work, we focus on prediction of multiple $k$ items that maybe useful for recommendation systems.

• Differential Privacy with Multiple Selections

  • Objective: We consider a scenario where a user sends a differentially private query to the server and propose a “multi-selection” architecture in which the server returns multiple items, allowing the user to choose the best fit. When the user’s feature is one-dimensional, we demonstrate that adding Laplace noise is an optimal mechanism, with the error decreasing inversely with the number of recommended items $k$.
  • Authors: Ashish Goel^*, Zhihao Jiang^*, Aleksandra Korolova^*, Kamesh Munagala^* and Sahasrajit Sarmasarkar^*
  • Paper submitted to ITCS 2025.

• Multi-Selection for Private Recommendation Systems

  • Objective We introduce a multi-selection model for a neural network-based movie recommendation system, trained on the MovieLens 25M dataset, where users send differentially private queries to the server. Additionally, we develop a local PCA model that enables users to choose a single item from the recommended set. Our empirical results indicate that, with “reasonable” privacy guarantees, our architecture provides utility closely matching that of the non-private scenario.

  • Authors: Sahasrajit Sarmasarkar, Zhihao Jiang, Ashish Goel, Aleksandra Korolova and Kamesh Munagala
  • Paper submitted to WSDM 2025

• A Characterization of List Learnability for Agnostic and Realizable Regression

  • Objective: In this work, we study the problem of list PAC learning (for both agnostic and realizable regression) where the aim of a learner is to learn to predict a set of $k$ labels with the loss being measured with respect to the closest label. We identify two dimensions of the hypothesis class—referred to as the $k$ fat-shattering dimension and the $k$ OIG dimension—whose finiteness is both necessary and sufficient for agnostic and realizable regression, respectively.

  • Authors: Chirag Pabbaraju^*, Sahasrajit Sarmasarkar^*
  • Paper submitted to ALT 2025

2. Social Choice

This area focuses on combining individual preferences to make collective decisions and measure social well-being.

• Metric Distortion under Probabilistic Voting

  • Objective: We extend the study of metric distortion in social choice, which evaluates the performance of voting rules, to the probabilistic voting framework that includes Plackett-Luce (PL). For example, in the PL model with candidate strength inversely proportional to the square of their metric distance, we show that Copeland’s distortion is at most 2, whereas that of Random Dictator (RD) scales with the square root of the number of candidates. However in the classical model, where RD beats Copeland with a distortion of 3 versus 5.

  • Authors: Sahasrajit Sarmasarkar^* and Mohak Goyal^*
  • Paper under review at Neurips 2024

• A Mechanism for Participatory Budgeting With Funding Constraints and Project Interactions

  • Objective: We investigate the challenge of participatory budgeting through menu-based preference elicitation, focusing on capturing project interactions, such as substitution and complementarity, from voters. We introduce an innovative preference elicitation approach that enables voters to express how their utilities from projects within specific ‘groups’ interact. In this context, we examine the property of strategy-proofness and present a fixed-parameter tractable (FPT) algorithm for maximizing social welfare.

  • Authors: Mohak Goyal^*, Sahasrajit Sarmasarkar^* and Ashish Goel
  • Paper presented at WINE 2023.

• Low sample complexity participatory budgeting

  • Objective: We study the problem of participatory budgeting where each voter votes for a preferred allocation of projects. We present a PB mechanism that attains a distortion of 1.66 when three votes are randomly sampled by the mechanism. This surpasses the distortion barrier of 2 achieved by the Randomized Dictator and Random Diarchy schemes, which select one and two voters at random from the set, respectively.

  • Authors: Mohak Goyal^*, Sukolsak Sakshuwong^*, Sahasrajit Sarmasarkar^* and Ashish Goel
  • Paper presented at ICALP 2023.