Go Top

Palash Dey

Assistant Professor
Department of Computer Science and Engineering
Indian Institute of Technology, Kharagpur

Office : A-204
Email : My first name "dot" my last name "at cse dot iitkgp dot ac dot in"
Phone : (03222) 283464
Resume : here
Research Interests: I am broadly interested in Theoretical Computer Science. My current research focuses on Parameterized Algorithms, Approximation Algorithms, and Algorithmic Game Theory
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.

Teaching:

Upcoming: CS31005 Algorithms II (with Prof. Sudeshna Kolay)
CS60029 Randomized Algorithm Design (with Prof. Somindu Chaya Ramanna)

Past: Courses on Web

My Notes:
Lecture Notes Algorithmic Game Theory here
Randomized Algorithms here
Selected Topics in Algorithms here
Short Notes Amortized Analyis of Fibonacci Heap Using Accounting Method here
Professional Services: Workshops Organized:
Publication: [DBLP] [Google Scholar]

[J18] Recognizing and Eliciting Weakly Single Crossing Profiles on Trees [ArXiv]
Theoretical Computer Science, 2025

[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)

[C31] Priced Gerrymandering [ArXiv]
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