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 Algorithmic Game Theory

Teaching:
Upcoming: CS60025 Algorithmic Game Theory in winter 2019
CS60047 Advanced Graph Theory in winter 2019 (with Prof. Bhargab B. Bhattacharya)

Past: Courses on Web
Professional Services:

For Students of IIT Kharagpur: I am broadly interested in Theoretical Computer Science (TCS). If you wish to work in TCS with me, please send me an email. I am actively looking for interested students in TCS.

For Students outside IIT Kharagpur:
Publication: [DBLP] [Google Scholar]

[C23] A Parameterized Perspective on Protecting Elections
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