Reviewer for Journal: Discrete Applied Mathematics, Artificial Intelligence, Autonomous Agents and Multi-Agent Systems, Theoretical Computer Science, Journal of Computer and System Sciences
Ph.D. Students: Sipra Singh (2020 Jan - present), Koustav De (2020 Jul - present, jointly with Prof. Swagato Sanyal), Ashlesha Hota (2024 Jan - present), Narayan Sharma (2023 Jul - present, jointly with Prof. Sudeshna Kolay)
Prospective Students: My research primarily focuses on advanced algorithm design in theoretical computer science. If you are interested to work with me in a research project in algorithm design, have done some advanced algorithm courses (CLRS book plus approximation/parameterized algorithms), and okay to work for at least six months in an online mode without funding support, then please email me. I am looking for students who are genuinely interested in algorithmic research.
[C44] Maximizing Value in Challenge the Champ Tournaments
[ArXiv]
with Umang Bhaskar and Juhi Chaudhary AAMAS, 2025
[C43] Voter Participation Control in Online Polls
[ArXiv]
with Koustav De and Swagato Sanyal AAMAS, 2025 (extended abstract)
[J17] Parameterized Aspects of Distinct Kemeny Rank Aggregation
[ArXiv]
with Koustav De, Harshil Mittal, and Neeldhara Misra Acta Informatica, 2024.
Remark: Conference version appeared in CALDAM, 2024.
[C42] Knapsack with Vertex Cover, Set Cover, and Hitting Set
[ArXiv]
with Ashlesha Hota, Sudeshna Kolay and Sipra Singh ISAAC, 2024
[J16] Query Complexity of Tournament Solutions [ArXiv]
with Arnab Maiti Theoretical Computer Science, 2024
Remark: Conference version appeared in AAAI, 2017.
[J15] On Parameterized Complexity of Binary Networked Public Goods Game [ArXiv]
with Arnab Maiti Algorithmica, 2024
Remark: Conference version appeared in AAMAS, 2022.
[C41] Evaluating District-based Election Surveys with Synthetic Dirichlet Likelihood
[ArXiv]
with Adway Mitra AAMAS, 2024
[C40] Optimal Referral Auction Design
[ArXiv]
with Rangeet Bhattacharyya, Parvik Dave, and Swaprava Nath AAMAS, 2024
[C39] Knapsack: Connectedness, Path, and Shortest-Path
[ArXiv]
with Sudeshna Kolay and Sipra Singh LATIN, 2024
[C38] On Binary Networked Public Goods Game with Altruism
[ArXiv]
with Arnab Maiti LATIN, 2024
[C37] Parameterized Aspects of Distinct Kemeny Rank Aggregation
[ArXiv]
with Koustav De, Harshil Mittal, and Neeldhara Misra CALDAM, 2024
[J14] How Hard is Safe Bribery? [ArXiv]
with Neel Karia and Faraaz Mallick Theoretical Computer Sciences, 2023
Remark: Conference version appeared in AAMAS, 2022.
[J13] Priced Gerrymandering [ArXiv] Theoretical Computer Sciences, 2023
Remark: Conference version appeared in AAMAS, 2022.
[J12] On the Exact Amount of Missing Information that makes Finding Possible Winners Hard [ArXiv]
with Neeldhara Misra Journal of Computer and System Sciences, 2023
Remark: Conference version appeared in MFCS, 2017.
[C36] Sampling-Based Winner Prediction in District-Based Elections
[ArXiv]
with Debajyoti Kar and Swagato Sanyal AAMAS, 2023 (extended abstract)
[C35] Feature-based Individual Fairness in k-clustering
[ArXiv]
with Debajyoti Kar, Mert Kosan, Debmalya Mandal, Sourav Medya, Arlei Silva and Swagato Sanyal AAMAS, 2023 (extended abstract)
[C34] How Hard is Safe Bribery?
[ArXiv]
with Neel Karia and Faraaz Mallick AAMAS, 2022
[C33] On Parameterized Complexity of Binary Networked Public Goods Game
[ArXiv]
with Arnab Maiti AAMAS, 2022
[C32] Parameterized Algorithms for Kidney Exchange
[ArXiv]
with Arnab Maiti IJCAI, 2022 (full paper) and also AAMAS, 2022 (extended abstract)
[J11] Distance Restricted Manipulation in Voting [ArXiv]
with Aditya Anand Theoretical Computer Science, 2021
[J10] A Parameterized Perspective on Protecting Elections [ArXiv]
with Neeldhara Misra, Swaprava Nath and Garima Shakya Theoretical Computer Science, 2021
Remark: Conference version appeared in IJCAI, 2019.
[J9] Predicting Winner and Estimating Margin of Victory in Elections using Sampling
with Arnab Bhattacharyya Artificial Intelligence, 2021
Remark: Part of this work appeared in conferences AAMAS, 2015 and IJCAI, 2015.
[C30] Fair Partitioning of Public Resources: Redrawing District Boundary to Minimize Spatial Inequality in School Funding
with Nuno Mota, Negar Mohammadi, Krishna P. Gummadi and Abhijnan Chakraborty WWW, 2021
[C29] Network Robustness via Global k-cores
[ArXiv]
with Suman Kalyan Maity, Sourav Medya and Arlei Silva AAMAS, 2021
[J8] Local Distance Constrained Bribery in Voting
[ArXiv] Theoretical Computer Science, 2021
Remark: Conference version appeared in AAMAS, 2019 (as extended abstract).
[C28] On Parameterized Complexity of Liquid Democracy
[ArXiv]
with Arnab Maiti and Amatya Sharma CALDAM, 2021
[C27] Improved Explicit Data Structures in the Bit-probe Model using Error Correcting Codes [MFCS]
with Jaikumar Radhakrishnan and Santhoshini Velusamy MFCS, 2020
[C26] On the complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules [ArXiv]
with Neeldhara Misra and Chinmay Sonar IJCAI, 2020
[C25] Manipulating Node Similarity Measures in Networks [ArXiv]
with Sourav Medya AAMAS, 2020
[C24] Minimizing Margin of Victory for Fair Political and Educational Districting [ArXiv]
with Ana-Andreea Stoica, Abhijnan Chakraborty, and Krishna Gummadi AAMAS, 2020
[C23] A Parameterized Perspective on Protecting Elections [ArXiv]
with Neeldhara Misra, Swaprava Nath and Garima Shakya IJCAI, 2019
[J7] Parameterized Dichotomy of Choosing Committees Based on Approval Votes in the Presence of Outliers
[ArXiv]
with Neeldhara Misra and Yadati Narahari Theoretical Computer Science, 2019
Remark: Conference version appeared in AAMAS, 2017.
[C22] Testing Preferential Domains using Sampling
[ArXiv]
with Swaprava Nath and Garima Shakya AAMAS, 2019
[C21] Covert Networks: How Hard is It to Hide?
[ArXiv]
with Sourav Medya AAMAS, 2019
[C20] Local Distance Restricted Bribery in Voting
[ArXiv] AAMAS, 2019 (extended abstract)
[C19] The Social Network Effect on Surprise in Elections
[ArXiv]
with Pravesh Kothari and Swaprava Nath CODS-COMAD, 2019
[J6] An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems
[ArXiv]
with Arnab Bhattacharyya and David P. Woodruff ACM Transactions on Algorithms (TALG), 2019
Remark: Conference version appeared in PODS, 2016.
[J5] Manipulative Elicitation -- A New Attack on Elections with Incomplete Preferences
[ArXiv] Theoretical Computer Science, 2018
Remark: Conference version appeared in AAAI, 2018.
[J4] Complexity of Manipulation with Partial Information in Voting
[ArXiv]
with Neeldhara Misra and Yadati Narahari Theoretical Computer Science, 2018
Remark: Conference version appeared in IJCAI, 2016.
[C18] Manipulative Elicitation -- A New Attack on Elections with Incomplete Preferences
[ArXiv] AAAI, 2018
[J3] Frugal Bribery in Voting
[ArXiv]
with Neeldhara Misra and Yadati Narahari Theoretical Computer Science, 2017
Remark: Conference version appeared in AAAI, 2016.
[C17] Query Complexity of Tournament Solutions
[ArXiv] AAAI, 2017
[C16] On the Exact Amount of Missing Information that makes Finding Possible Winners Hard
[ArXiv]
with Neeldhara Misra MFCS, 2017
[C15] Parameterized Dichotomy of Choosing Committees Based on Approval Votes in the Presence of Outliers
[ArXiv]
with Neeldhara Misra and Yadati Narahari AAMAS, 2017
[C14] Proportional Representation in Vote Streams
[ArXiv]
with Nimrod Talmon and Otniel van Handel AAMAS, 2017
[J2] Kernelization Complexity of Possible Winner and Coalitional Manipulation Problems in Voting
[ArXiv]
with Neeldhara Misra and Yadati Narahari Theoretical Computer Science, 2016
Remark: Conference version appeared in AAMAS, 2015.
[C13] An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems
[ArXiv]
with Arnab Bhattacharyya and David P. Woodruff PODS, 2016
[C12] Preference Elicitation for Single Crossing Domain
[ArXiv]
with Neeldhara Misra IJCAI, 2016
[C11] Elicitation for Preferences Single Peaked on Trees
[ArXiv]
with Neeldhara Misra IJCAI, 2016
[C10] Complexity of Manipulation with Partial Information in Voting
[ArXiv]
with Neeldhara Misra and Yadati Narahari IJCAI, 2016
[C9] Frugal Bribery in Voting
[ArXiv]
with Neeldhara Misra and Yadati Narahari AAAI, 2016
Errata: The proof of Theorem 1 in the conference version of this paper is erroneous. The correct proof is available in the journal version.
[J1] Asymptotic Collusion-proofness of Voting Rules: The Case of Large Number of Candidates
[ArXiv]
with Yadati Narahari TStudies in Microeconomics, 2015
Remark: Conference version appeared in AAMAS, 2014 as an extended abstract.
[C8] Estimating the Margin of Victory of Elections using Sampling
[ArXiv]
with Yadati Narahari IJCAI, 2015
[C7] Sample Complexity for Winner Prediction in Elections
[ArXiv]
with Arnab Bhattacharyya AAMAS, 2015
Errata: Theorem 3 claims to prove lower bound for the k-approval voting rule for any value of k; however the proof only works for k < cm for any constant c in (0,1).
[C6] Detecting Possible Manipulators in Elections
[ArXiv]
with Neeldhara Misra and Yadati Narahari AAMAS, 2015
[C5] Kernelization Complexity of Possible Winner and Coalitional Manipulation Problems in Voting
[ArXiv]
with Neeldhara Misra and Yadati Narahari AAMAS, 2015
[C4] Computational Complexity of Fundamental Problems in Social Choice Theory (Doctoral Consortium) [AAMAS] AAMAS, 2015
[C3] Asymptotic Collusion-Proofness of Voting Rules: The Case of Large Number of Candidates
[ArXiv]
with Yadati Narahari AAMAS, 2014 (extended abstract)
[C2] UNO Gets Easier for a Single Player
[FUN]
with Prachi Goyal and Neeldhara Misra FUN, 2014
[C1] Dynamic Multipath Bandwidth Provisioning with Jitter, Throughput and SLA constraint in MPLS over WDM network
[ICDCN]
with A. Kundu, M. K. Naskar, A. Mukherjee, and A. Nasipuri ICDCN, 2010