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
Analysis of Randomized Selection 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