About

Kamesh Munagala is a professor in the Computer Science Department at Duke University. His research lies in the general area of theoretical computer science, with a particular focus on approximation algorithms, online algorithms, and computational economics. He develops models, algorithms, and markets aimed at solving resource allocation, decision making, and provisioning problems that arise in diverse applications such as data network design, facility location and clustering, data center scheduling, ad slot allocation, ride-share scheduling, and civic budgeting. His work addresses key challenges including computational efficiency, managing uncertainty in future inputs, pricing and incentives when allocating resources to selfish agents, and ensuring fairness to individuals and groups. Recently, his research has concentrated on persuading optimizers or learners towards specific objectives through information revelation and pricing, as well as promoting fairness to groups based on proportionality and stability in resource allocation and societal decision-making contexts.

Research topics

• Computer Science
• Artificial Intelligence
• Information Retrieval
• Sociology
• Mathematics
• Mathematical economics
• Machine Learning
• World Wide Web
• Business
• Internet privacy
• Advertising
• Demography
• Statistics
• Operations research
• Psychology
• Economics

Selected publications

• Beyond Polarization: Opinion Mixing and Social Influence in Deliberation

  arXiv (Cornell University) · 2026-01-20

  preprintOpen accessSenior author

  Deliberative processes are often discussed as increasing or decreasing polarization. This approach misses a different, and arguably more diagnostic, dimension of opinion change: whether deliberation reshuffles who agrees with whom, or simply moves everyone in parallel while preserving the pre-deliberation rank ordering. We introduce \opinion mixing, measured by Kendall's rank correlation (τ) between pre- and post-deliberation responses, as a complement to variance-based polarization metrics. Across two large online deliberative polls spanning 32 countries (MCF-2022: n=6,342; MCF-2023: n=1,529), deliberation increases opinion mixing relative to survey-only controls: treatment groups exhibit lower rank correlation on (97%) and (93%) of opinion questions, respectively. Polarization measures based on variance tell a more heterogeneous story: controls consistently converge, while treated groups sometimes converge and sometimes diverge depending on the issue. To probe mechanisms, we link transcripts and surveys in a third event (SOF: (n=617), 116 groups) and use LLM-assisted coding of 6,232 discussion statements. Expressed support in discussion statements strongly predicts subsequent group-level opinion shifts; this correlation is amplified by justification quality in the statements but not by argument novelty. To our knowledge, we are the first to observe how different notions of argument quality have different associations with the outcome of deliberation. This suggests that opinion change after deliberation is related to selective uptake of well-reasoned arguments, producing complex patterns of opinion reorganization that standard polarization metrics may miss.

  PublisherDOI

• Efficient Online Conformal Selection with Limited Feedback

  ArXiv.org · 2026-05-14

  articleOpen access

  We address the problem of conformal selection, where an agent must select a minimal subset of options to ensure that at least one ``success'' is identified with a pre-specified target probability $ϕ$. While traditional online conformal prediction focuses on maintaining validity for the observed sequence, minimizing the resource cost (efficiency) of such selections, especially under limited feedback, remains a significant challenge. In this work, we consider settings with the most limited ``bandit'' feedback, and demonstrate that the simple Adaptive Conformal Inference (ACI) update rule, when applied to the appropriate control parameter or dual variable, is both adversarially valid, ensuring the success target is met on average for any input sequence (and hence under distribution shifts), and stochastically efficient, achieving sublinear efficiency regret for $i.i.d.$ inputs against an appropriate stochastic benchmark. We show such guarantees under canonical models capturing bandit and semi-bandit feedback to the agent via a unifying algorithmic technique, and analytic framework involving Lyapunov functions. Our approach handles more complex settings than prior work, while requiring significantly less feedback, and our results provide a new theoretical bridge between efficient online learning with limited feedback and distribution-free uncertainty quantification.

  PublisherOA PDF

• Compact Conformal Subgraphs

  arXiv (Cornell University) · 2026-02-07

  articleOpen access

  Conformal prediction provides rigorous, distribution-free uncertainty guarantees, but often yields prohibitively large prediction sets in structured domains such as routing, planning, or sequential recommendation. We introduce "graph-based conformal compression", a framework for constructing compact subgraphs that preserve statistical validity while reducing structural complexity. We formulate compression as selecting a smallest subgraph capturing a prescribed fraction of the probability mass, and reduce to a weighted version of densest $k$-subgraphs in hypergraphs, in the regime where the subgraph has a large fraction of edges. We design efficient approximation algorithms that achieve constant factor coverage and size trade-offs. Crucially, we prove that our relaxation satisfies a monotonicity property, derived from a connection to parametric minimum cuts, which guarantees the nestedness required for valid conformal guarantees. Our results on the one hand bridge efficient conformal prediction with combinatorial graph compression via monotonicity, to provide rigorous guarantees on both statistical validity, and compression or size. On the other hand, they also highlight an algorithmic regime, distinct from classical densest-$k$-subgraph hardness settings, where the problem can be approximated efficiently. We finally validate our algorithmic approach via simulations for trip planning and navigation, and compare to natural baselines.

  PublisherOA PDF

• Beyond Polarization: Opinion Mixing and Social Influence in Deliberation

  ArXiv.org · 2026-01-20

  articleOpen accessSenior author

  Deliberative processes are often discussed as increasing or decreasing polarization. This approach misses a different, and arguably more diagnostic, dimension of opinion change: whether deliberation reshuffles who agrees with whom, or simply moves everyone in parallel while preserving the pre-deliberation rank ordering. We introduce \opinion mixing, measured by Kendall's rank correlation (τ) between pre- and post-deliberation responses, as a complement to variance-based polarization metrics. Across two large online deliberative polls spanning 32 countries (MCF-2022: n=6,342; MCF-2023: n=1,529), deliberation increases opinion mixing relative to survey-only controls: treatment groups exhibit lower rank correlation on (97%) and (93%) of opinion questions, respectively. Polarization measures based on variance tell a more heterogeneous story: controls consistently converge, while treated groups sometimes converge and sometimes diverge depending on the issue. To probe mechanisms, we link transcripts and surveys in a third event (SOF: (n=617), 116 groups) and use LLM-assisted coding of 6,232 discussion statements. Expressed support in discussion statements strongly predicts subsequent group-level opinion shifts; this correlation is amplified by justification quality in the statements but not by argument novelty. To our knowledge, we are the first to observe how different notions of argument quality have different associations with the outcome of deliberation. This suggests that opinion change after deliberation is related to selective uptake of well-reasoned arguments, producing complex patterns of opinion reorganization that standard polarization metrics may miss.

  PublisherOA PDF

• Efficient Online Conformal Selection with Limited Feedback

  arXiv (Cornell University) · 2026-05-14

  preprintOpen access

  We address the problem of conformal selection, where an agent must select a minimal subset of options to ensure that at least one ``success'' is identified with a pre-specified target probability $ϕ$. While traditional online conformal prediction focuses on maintaining validity for the observed sequence, minimizing the resource cost (efficiency) of such selections, especially under limited feedback, remains a significant challenge. In this work, we consider settings with the most limited ``bandit'' feedback, and demonstrate that the simple Adaptive Conformal Inference (ACI) update rule, when applied to the appropriate control parameter or dual variable, is both adversarially valid, ensuring the success target is met on average for any input sequence (and hence under distribution shifts), and stochastically efficient, achieving sublinear efficiency regret for $i.i.d.$ inputs against an appropriate stochastic benchmark. We show such guarantees under canonical models capturing bandit and semi-bandit feedback to the agent via a unifying algorithmic technique, and analytic framework involving Lyapunov functions. Our approach handles more complex settings than prior work, while requiring significantly less feedback, and our results provide a new theoretical bridge between efficient online learning with limited feedback and distribution-free uncertainty quantification.

  PublisherDOI

• The Limits of Interval-Regulated Price Discrimination

  Lecture notes in computer science · 2026-01-01

  preprintOpen access1st author
  PublisherOA PDFDOI

• Compact Conformal Subgraphs

  Open MIND · 2026-02-07

  preprint

  Conformal prediction provides rigorous, distribution-free uncertainty guarantees, but often yields prohibitively large prediction sets in structured domains such as routing, planning, or sequential recommendation. We introduce "graph-based conformal compression", a framework for constructing compact subgraphs that preserve statistical validity while reducing structural complexity. We formulate compression as selecting a smallest subgraph capturing a prescribed fraction of the probability mass, and reduce to a weighted version of densest $k$-subgraphs in hypergraphs, in the regime where the subgraph has a large fraction of edges. We design efficient approximation algorithms that achieve constant factor coverage and size trade-offs. Crucially, we prove that our relaxation satisfies a monotonicity property, derived from a connection to parametric minimum cuts, which guarantees the nestedness required for valid conformal guarantees. Our results on the one hand bridge efficient conformal prediction with combinatorial graph compression via monotonicity, to provide rigorous guarantees on both statistical validity, and compression or size. On the other hand, they also highlight an algorithmic regime, distinct from classical densest-$k$-subgraph hardness settings, where the problem can be approximated efficiently. We finally validate our algorithmic approach via simulations for trip planning and navigation, and compare to natural baselines.

  DOI

• Balanced Spanning Tree Distributions Have Separation Fairness

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapter
  PublisherDOI

• Balanced Spanning Tree Distributions Have Separation Fairness

  ArXiv.org · 2025-09-18

  preprintOpen access

  Sampling-based methods such as ReCom are widely used to audit redistricting plans for fairness, with the balanced spanning tree distribution playing a central role since it favors compact, contiguous, and population-balanced districts. However, whether such samples are truly representative or exhibit hidden biases remains an open question. In this work, we introduce the notion of separation fairness, which asks whether adjacent geographic units are separated with at most a constant probability (bounded away from one) in sampled redistricting plans. Focusing on grid graphs and two-district partitions, we prove that a smooth variant of the balanced spanning tree distribution satisfies separation fairness. Our results also provide theoretical support for popular MCMC methods like ReCom, suggesting that they maintain fairness at a granular level in the sampling process. Along the way, we develop tools for analyzing loop-erased random walks and partitions that may be of independent interest.

  PublisherOA PDFDOI

• Online Distributed Queue Length Estimation

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01

  book-chapterSenior author

  Queue length monitoring is a commonly arising problem in numerous applications such as queue management systems, scheduling, and traffic monitoring. Motivated by such applications, we formulate a queue monitoring problem, where there is a FIFO queue with arbitrary arrivals and departures, and a server needs to monitor the length of a queue by using decentralized pings from packets in the queue. Packets can send pings informing the server about the number of packets ahead of them in the queue. Via novel online policies and lower bounds, we tightly characterize the trade-off between the number of pings sent and the accuracy of the server’s real time estimates. Our work studies the trade-off under various arrival and departure processes, including constant-rate, Poisson, and adversarial processes.

  PublisherDOI

Recent grants

• AitF: Collaborative Research: Fair and Efficient Societal Decision Making via Collaborative Convex Optimization

  NSF · $333k · 2016–2021

• AF: Small: Algorithm and Incentive Design for Modern Resource Allocation Platforms

  NSF · $505k · 2021–2025

• AF: Small: Auction Design in Constrained Settings

  NSF · $515k · 2010–2015

• CAREER: Light-weight Near-optimal Stochastic Control Policies for Information Acquisition and Exploitation

  NSF · $412k · 2008–2015

• CCF:AF:EAGER Algorithmic Paradigms for Computation on MapReduce

  NSF · $100k · 2013–2015

Frequent coauthors

• Sudipto Guha

  University of Pennsylvania

  41 shared

• Ashish Goel

  32 shared

• Sreenivas Gollapudi

  Google (United States)

  32 shared

• Nikhil Garg

  Cornell University

  28 shared

• Vijay Kamble

  28 shared

• David Marn

  University of California, Berkeley

  28 shared

• Kangning Wang

  Tianjin University of Science and Technology

  27 shared

• Ashish Goel

  25 shared