Siddharth Barman

Publications and Preprints

Packing Linear Programs and Fractional Knapsack using Comparison Oracles
With Ritabrata Barat, Nirjhar Das, and Sukruta Midigeshi
WINE 2026
arXiv
Equitable Colorings of Vertex-Weighted Graphs
With Vignesh Viswanathan
Preprint 2026
arXiv
Welfarist Formulations for Diverse Similarity Search
With Nirjhar Das, Shivam Gupta, and Kirankumar Shiragur
ICLR 2026
arXiv
Existence and Computation of Fair Allocations under Constraints
With Ioannis Caragiannis and Sudarshan Shyam
AAMAS 2026
arXiv
Introspectively Envy-Free and Efficient Allocation of Indivisible Mixed Manna
With Paritosh Verma
Preprint 2026
arXiv
Fair Division Beyond Monotone Valuations with Applications to Equitable Graph Partitioning
With Paritosh Verma
SODA 2026
arXiv
Compatibility of Fairness and Nash Welfare under Subadditive Valuations
With Mashbat Suzuki
SODA 2026
arXiv
Fair and Efficient Allocation of Indivisible Mixed Manna
With Vishwa Prakash HV, Aditi Sethia, and Mashbat Suzuki
WINE 2025
arXiv
Exact Maximin Share Fairness via Adjusted Supply
With Satyanand Rammohan and Aditi Sethia
Preprint 2025
arXiv
Fair Division with Market Values
With Soroush Ebadian, Mohamad Latifian, and Nisarg Shah
AAAI 2025
arXiv
Generalized Linear Bandits with Limited Adaptivity
With Ayush Sawarni, Nirjhar Das, and Gaurav Sinha
NeurIPS 2024
arXiv
Causal Contextual Bandits with Adaptive Context
With Rahul Madhavan, Aurghya Maiti, and Gaurav Sinha
RLC 2024
arXiv
Parameterized Guarantees for Almost Envy-Free Allocations
With Debajyoti Kar and Shraddha Pathak
AAMAS 2024
arXiv
Nearly Equitable Allocations Beyond Additivity and Monotonicity
With Umang Bhaskar, Yeshwant Pandit, and Soumyajit Pyne
AAAI 2024
arXiv
Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations
With Anand Krishna, Pooja Kulkarni, and Shivika Narang
ITCS 2024
arXiv
Nash Regret Guarantees for Linear Bandits
With Ayush Sawarni and Soumybrata Pal
NeurIPS 2023
arXiv
Learning Good Interventions in Causal Graphs via Covering
With Ayush Sawarni, Rahul Madhavan, and Gaurav Sinha
UAI 2023
arXiv
Guaranteeing Envy-Freeness under Generalized Assignment Constraints
With Arindam Khan, Sudarshan Shyam, and K.V.N. Sreenivas
EC 2023
arXiv
Approximation Algorithms for Envy-Free Cake Division with Connected Pieces
With Pooja Kulkarni
ICALP 2023
arXiv
Fair Chore Division under Binary Supermodular Costs
With Vishnu Narayan and Paritosh Verma
AAMAS 2023 (Extended Abstract)
arXiv
Fairness and Welfare Quantification for Regret in Multi-Armed Bandits
With Arindam Khan, Arnab Maiti, and Ayush Sawarni
AAAI 2023
arXiv
Finding Fair Allocations under Budget Constraints
With Arindam Khan, Sudarshan Shyam, and K.V.N. Sreenivas
AAAI 2023
arXiv
Nash Welfare Guarantees for Fair and Efficient Coverage
With Anand Krishna, Y. Narahari, and Soumyarup Sadhukhan
WINE 2022
arXiv
Achieving Envy-Freeness with Limited Subsidies under Dichotomous Valuations
With Anand Krishna, Y. Narahari, and Soumyarup Sadhukhan
IJCAI 2022
arXiv
Truthful and Fair Mechanisms for Matroid-Rank Valuations
With Paritosh Verma
AAAI 2022
arXiv
Universal and Tight Online Algorithms for Generalized-Mean Welfare
With Arindam Khan and Arnab Maiti
AAAI 2022
arXiv
Approximating Nash Social Welfare Under Binary XOS and Binary Subadditive Valuations
With Paritosh Verma
WINE 2021
arXiv
Optimal Algorithms for Range Searching over Multi-Armed Bandits
With Ramakrishnan K and Rahul Saladi
IJCAI 2021
arXiv
Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations
With Paritosh Verma
AAMAS 2021
arXiv
Tight Approximation Guarantees for Concave Coverage Problems
With Omar Fawzi and Paul Ferme
STACS 2021
arXiv
Optimal Bounds on the Price of Fairness for Indivisible Goods
With Umang Bhaskar and Nisarg Shah
WINE 2020
arXiv
Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations
With Umang Bhaskar, Anand Krishna, and Ranjani Sundaram
ESA 2020
arXiv
Fair Cake Division Under Monotone Likelihood Ratios
With Nidhi Rathi
EC 2020
arXiv
The Edgeworth Conjecture with Small Coalitions and Approximate Equilibria in Large Economies
With Federico Echenique
EC 2020
arXiv
Uniform Welfare Guarantees Under Identical Subadditive Valuations
With Ranjani Sundaram
IJCAI 2020
arXiv
Tight Approximation Bounds for Maximum Multi-Coverage
With Omar Fawzi, Suprovat Ghoshal, and Emirhan Gurpinar
IPCO 2020
arXiv
Inframarginality Audit of Group-Fairness
With Arpita Biswas, Amit Deshpande, and Amit Sharma
FORC 2020
arXiv
Fair and Efficient Cake Division with Connected Pieces
With Eshwar Ram Arunachaleswaran, Rachitesh Kumar, and Nidhi Rathi
WINE 2019
arXiv
Fair Division of Indivisible Goods Among Strategic Agents
With Ganesh Ghalme, Shweta Jain, Pooja Kulkarni, and Shivika Narang
AAMAS 2019 (Extended Abstract)
arXiv
On the Proximity of Markets with Integral Equilibria
With Sanath Kumar Krishnamurthy
AAAI 2019
arXiv
Fair Division with a Secretive Agent
With Eshwar Ram Arunachaleswaran and Nidhi Rathi
AAAI 2019
arXiv
Fully Polynomial-Time Approximation Schemes for Fair Rent Division
With Eshwar Ram Arunachaleswaran and Nidhi Rathi
SODA 2019
arXiv
Testing Sparsity over Known and Unknown Bases
With Arnab Bhattacharyya and Suprovat Ghoshal
ICML 2018
arXiv
Finding Fair and Efficient Allocations
With Sanath Kumar Krishnamurthy and Rohit Vaish
EC 2018
arXiv
Fair Division Under Cardinality Constraints
With Arpita Biswas
IJCAI 2018
arXiv
Greedy Algorithms for Maximizing Nash Social Welfare
With Sanath Kumar Krishnamurthy and Rohit Vaish
AAMAS 2018
arXiv
Groupwise Maximin Fair Allocation of Indivisible Goods
With Arpita Biswas, Sanath Kumar Krishnamurthy, and Y. Narahari
AAAI 2018
arXiv
Online Learning for Structured Loss Spaces
With Aditya Gopalan and Aadirupa Saha
AAAI 2018
arXiv
Approximation Algorithms for Maximin Fair Division.
With Sanath Kumar Krishnamurthy
EC 2017
arXiv
Algorithmic Aspects of Optimal Channel Coding
With Omar Fawzi
IEEE Transactions on Information Theory, 2018
arXiv
Empirical Distribution of Equilibrium Play and Its Testing Application
With Yakov Babichenko and Ron Peretz
Mathematics of Operations Research (MOR), 2017
arXiv
Algorithmic Aspects of Private Bayesian Persuasion
With Yakov Babichenko
ITCS 2017
arXiv
Approximating Nash Equilibria in Tree Polymatrix Games
With Katrina Ligett and Georgios Piliouras
SAGT 2015
arXiv
Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard
With Katrina Ligett
EC 2015
arXiv
Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem
STOC 2015
arXiv
Online Convex Optimization Using Predictions
With Niangjun Chen, Anish Agarwal, Adam Wierman, and Lachlan L. H. Andrew
SIGMETRICS 2015
arXiv
Query Complexity of Correlated Equilibrium
With Yakov Babichenko
Trans. on Economics and Computation, 2015
arXiv
Simple Approximate Equilibria in Large Games
With Yakov Babichenko and Ron Peretz
EC 2014
arXiv
Network Design with Coverage Costs
With Shuchi Chawla and Seeun Umboh
APPROX 2014
arXiv
On the Existence of Low-Rank Explanations for Mixed Strategy Behavior
With Umang Bhaskar, Federico Echenique, and Adam Wierman
WINE 2014
arXiv
On Load Shedding in Complex Event Processing
With Yeye He and Jeffery Naughton
ICDT 2014
arXiv
The Empirical Implications of Rank in Bimatrix Games
With Umang Bhaskar, Federico Echenique, and Adam Wierman
EC 2013
arXiv
Simultaneous Bounds on Competitiveness and Regret
With Lachlan L. H. Andrew, Katrina Ligett, Minghong Lin, Adam Meyerson, Alan Roytman, and Adam Wierman
COLT 2013
Decomposition Methods for Large Scale LP Decoding
With Xishuo Liu, Stark Draper, and Benjamin Recht
IEEE Transactions on Information Theory, 2013
arXiv
Traffic-Redundancy Aware Network Design
With Shuchi Chawla
SODA 2012
arXiv
A Bicriteria Approximation for the Reordering Buffer Problem
With Shuchi Chawla and Seeun Umboh
ESA 2012
arXiv
Secretary Problems with Convex Costs
With Shuchi Chawla, David Malec, and Seeun Umboh
ICALP 2012
arXiv
Approximate String Membership Checking: A Multiple Filter, Optimization-Based Approach
With Chong Sun and Jeffrey Naughton
ICDE 2012
On the Complexity of Privacy-Preserving Complex Event Processing
With Yeye He, Jeffrey Naughton, and Di Wang
PODS 2011
Preventing Equivalence Attacks in Updated, Anonymized Data
With Yeye He, and Jeffrey Naughton
ICDE 2011
Region Growing For Multi-Route Cuts
With Shuchi Chawla
SODA 2010
arXiv
Packing Multiway Cuts in Capacitated Graphs
With Shuchi Chawla
SODA 2009
arXiv