CINXE.COM

<html><head> <meta http-equiv="content-type" content="text/html; charset=UTF-8"> <title>Home Page of Palash Dey</title> </head> <body bgcolor=" #FAF1F3 " style="font-family:Palatino;"> <div style="position:fixed;top:90%;left:90%;padding:3px;box-shadow: 4px 4px 4px #888888; background:#CCC; color:#FFFFFF; text-decoration:none; text-align:center; font-size:20px; font-weight:bold;"><a href="#">Go Top</a></div> <table cellpadding="4"> <tbody> <tr> <td><img alt="" src="./Files/palash.jpg" height="250" width=auto></td> <td><h2>Palash Dey</h2> Assistant Professor <a href="http://cse.iitkgp.ac.in/"> Department of Computer Science and Engineering</a> <a href="http://www.iitkgp.ac.in/"> Indian Institute of Technology, Kharagpur</a> Office : A-204 Email : My first name "dot" my last name "at cse dot iitkgp dot ac dot in" Phone : (03222) 283464 Resume : <a href="./Files/resume.pdf" target="_blank">here</a> </td> </tr> </tbody></table> <hr> <center> <div id="nav-menu-wrapper"> <nav role="navigation" class="site-navigation main-navigation"> <div class="menu"> <a href="#interest">[ Research Interests ]</a> <a href="#publication">[ Publications ]</a> <a href="#teach">[ Teaching ]</a> <a href="#forstudents">[ For Students ]</a> <a href="#service">[ Services ]</a> </div> </nav> </div> </center><hr> <a id="interest"></a> Research Interests: I am broadly interested in Theoretical Computer Science. My current research focuses on Algorithmic Game Theory <hr> <a id="teach"></a> Teaching: Current: <a href="./Courses/2025SelectedTopicsInAlgorithms/2025SelectedTopics.html" target="_blank">CS60086 Selected Topics in Algorithms </a> CS19003 Programming and Data Structures Laboratory (with Prof. Ayan Chaudhury and Prof. Debaditya Roy) Past: <a href="./Courses/pastCourses.html" target="_blank">Courses on Web</a><hr> <a id="service"></a> Professional Services: <ul style="line-height:180%"> <li>Newsletter and Social Media Chair of IEEE Kharagpur Section</li> <li>Senior Program Committee Member: AAAI 2021-24</li> <li>Program Committee Member: AAAI 2019-20; IJCAI 2022-24, 2018-20, 2016; AAMAS 2021-24; COMSOC 2018,20,23</li> <li>Reviewer for Conference: AAAI, IJCAI, COMSOC, STOC, CSR, WINE, FSTTCS, PODS</li> <li>Reviewer for Journal: Discrete Applied Mathematics, Artificial Intelligence, Autonomous Agents and Multi-Agent Systems, Theoretical Computer Science, Journal of Computer and System Sciences</li> </ul> Workshops Organized: <ul style="line-height:180%"> <li>Fourth <a href="./Workshops/2024RTA.html" target="_blank">Recent Trends in Algorithms 2024</a> in IACS, Kolkata.</li> <li><a href="https://gtl.csa.iisc.ac.in/gamearts/" target="_blank">GAME-ARTS</a> in IISc, Bangalore.</li> <li>Fifth <a href="https://cse.iitkgp.ac.in/conf/CALDAM/" target="_blank">International Conference on Algorithms and Discrete Applied Mathematics (CALDAM) 2019</a> in IIT, Kharagpur.</li> </ul> <hr> <a id="forstudents"></a> Ph.D. Students: Sipra Singh (2020-present), Koustav De (2020-present, jointly with Prof. Swagato Sanyal) M.Tech. Students: Mahendra Singh Kanyal (2019-20), Pratik Rawat (2019-20), Animesh Panwar (2019-20) U.G. Students: Arnab Maiti (2020-22), Amatya Sharma (2020-22), Faraaz Mallick (2020-22), Neel Karia (2020-21), Madhusudan Reddy (2020-21), Aditya Anand (2019-21) For Prospective 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 Prospective Students outside IIT Kharagpur: <ul style="line-height:180%"> <li>Post-Doctoral Positions:   The Institute has a regularized procedure to appoint post-doctoral researchers. For details, please visit <a href="http://www.iitkgp.ac.in/academics-post-doc-fellowships" target="_blank">HERE</a>. To apply, please visit <a href="https://erp.iitkgp.ernet.in/PDFApplications/Login.jsp" target="_blank">HERE</a>. (Interested candidates may write to me with a copy of their recent resume and one letter of recommendation.)</li> <li>Ph.D. Positions:   The Institute has a centralized policy for PhD entrance. For details, please visit <a href="http://www.iitkgp.ac.in/phd" target="_blank">HERE</a>. To apply, please visit <a href="https://erp.iitkgp.ac.in/IITKGPApplications/index" target="_blank">HERE</a>. The syllabus for the PhD entrance test (in CSE-Dept) can be found <a href="http://cse.iitkgp.ac.in/?msphdenttest.html" target="_blank">HERE</a>.</li> <li>M.S. (by Research) Positions:   For M.S., you have to first get through some project. The institute project advertisements appear <a href="http://www.iitkgp.ac.in/temporary-jobs" target="_blank">HERE</a>. Once you are already a project staff, you can apply for MS. The syllabus for the MS entrance test (in CSE-Dept) can be found <a href="http://cse.iitkgp.ac.in/?msphdenttest.html" target="_blank">HERE</a>.</li> <li>Internship Positions:   We only offer summer internships and hence please do not apply for internships in winter/fall. For details, please visit <a href="http://cse.iitkgp.ac.in/?summerinterns.html" target="_blank">HERE</a>. To apply, please visit <a href="http://cse.iitkgp.ac.in/internship/" target="_blank">HERE</a>. (In general, your internship requests directly to my mail-box will never be acknowledged! Therefore, kindly apply <a href="http://cse.iitkgp.ac.in/internship/" target="_blank">ONLINE</a>.)</li></ul> <hr> <a id="publication"></a> Publication: [<a href="https://dblp.org/pers/hd/d/Dey:Palash" target="_blank">DBLP</a>] [<a href="https://scholar.google.co.in/citations?user=BkDCPiIAAAAJ&hl=en" target="_blank">Google Scholar</a>] [J17] Parameterized Aspects of Distinct Kemeny Rank Aggregation [<a href="https://arxiv.org/abs/2309.03517" target="_blank">ArXiv</a>] 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 [<a href="https://arxiv.org/abs/2406.01057" target="_blank">ArXiv</a>] with Ashlesha Hota, Sudeshna Kolay and Sipra Singh ISAAC, 2024 [J16] Query Complexity of Tournament Solutions [<a href="https://arxiv.org/abs/1611.06189" target="_blank">ArXiv</a>] with Arnab Maiti Theoretical Computer Science, 2024 Remark: Conference version appeared in AAAI, 2017. [J15] On Parameterized Complexity of Binary Networked Public Goods Game [<a href="https://arxiv.org/abs/2012.01880" target="_blank">ArXiv</a>] with Arnab Maiti Algorithmica, 2024 Remark: Conference version appeared in AAMAS, 2022. [C41] Evaluating District-based Election Surveys with Synthetic Dirichlet Likelihood [<a href="https://arxiv.org/abs/2312.15179" target="_blank">ArXiv</a>] with Adway Mitra AAMAS, 2024 [C40] Optimal Referral Auction Design [<a href="https://arxiv.org/abs/2208.09326" target="_blank">ArXiv</a>] with Rangeet Bhattacharyya, Parvik Dave, and Swaprava Nath AAMAS, 2024 [C39] Knapsack: Connectedness, Path, and Shortest-Path [<a href="https://arxiv.org/abs/2307.12547" target="_blank">ArXiv</a>] with Sudeshna Kolay and Sipra Singh LATIN, 2024 [C38] On Binary Networked Public Goods Game with Altruism [<a href="https://arxiv.org/abs/2205.00442" target="_blank">ArXiv</a>] with Arnab Maiti LATIN, 2024 [C37] Parameterized Aspects of Distinct Kemeny Rank Aggregation [<a href="https://arxiv.org/abs/2309.03517" target="_blank">ArXiv</a>] with Koustav De, Harshil Mittal, and Neeldhara Misra CALDAM, 2024 [J14] How Hard is Safe Bribery? [<a href="https://arxiv.org/abs/2201.10383" target="_blank">ArXiv</a>] with Neel Karia and Faraaz Mallick Theoretical Computer Sciences, 2023 Remark: Conference version appeared in AAMAS, 2022. [J13] Priced Gerrymandering [<a href="https://arxiv.org/abs/1909.01583" target="_blank">ArXiv</a>] 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 [<a href="https://arxiv.org/abs/1610.08407" target="_blank">ArXiv</a>] 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 [<a href="https://arxiv.org/abs/2203.00083" target="_blank">ArXiv</a>] with Debajyoti Kar and Swagato Sanyal AAMAS, 2023 (extended abstract) [C35] Feature-based Individual Fairness in k-clustering [<a href="https://arxiv.org/abs/2109.04554" target="_blank">ArXiv</a>] with Debajyoti Kar, Mert Kosan, Debmalya Mandal, Sourav Medya, Arlei Silva and Swagato Sanyal AAMAS, 2023 (extended abstract) [C34] How Hard is Safe Bribery? [<a href="https://arxiv.org/abs/2201.10383" target="_blank">ArXiv</a>] with Neel Karia and Faraaz Mallick AAMAS, 2022 [C33] On Parameterized Complexity of Binary Networked Public Goods Game [<a href="https://arxiv.org/abs/2012.01880" target="_blank">ArXiv</a>] with Arnab Maiti AAMAS, 2022 [C32] Parameterized Algorithms for Kidney Exchange [<a href="http://arxiv.org/abs/2112.10250" target="_blank">ArXiv</a>] with Arnab Maiti IJCAI, 2022 (full paper) and also AAMAS, 2022 (extended abstract) [C31] Priced Gerrymandering [<a href="https://arxiv.org/abs/1909.01583" target="_blank">ArXiv</a>] AAMAS, 2022 (extended abstract) [J11] Distance Restricted Manipulation in Voting [<a href="https://arxiv.org/abs/1909.03162" target="_blank">ArXiv</a>] with Aditya Anand Theoretical Computer Science, 2021 [J10] A Parameterized Perspective on Protecting Elections [<a href="https://arxiv.org/abs/1905.11838" target="_blank">ArXiv</a>] 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 [<a href="https://arxiv.org/abs/2012.10036" target="_blank">ArXiv</a>] with Suman Kalyan Maity, Sourav Medya and Arlei Silva AAMAS, 2021 [J8] Local Distance Constrained Bribery in Voting [<a href="https://arxiv.org/abs/1901.08711" target="_blank">ArXiv</a>] Theoretical Computer Science, 2021 Remark: Conference version appeared in AAMAS, 2019 (as extended abstract). [C28] On Parameterized Complexity of Liquid Democracy [<a href="https://arxiv.org/abs/2011.14192" target="_blank">ArXiv</a>] with Arnab Maiti and Amatya Sharma CALDAM, 2021 [C27] Improved Explicit Data Structures in the Bit-probe Model using Error Correcting Codes [<a href="https://drops.dagstuhl.de/opus/volltexte/2020/12696/pdf/LIPIcs-MFCS-2020-28.pdf" target="_blank">MFCS</a>] with Jaikumar Radhakrishnan and Santhoshini Velusamy MFCS, 2020 [C26] On the complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules [<a href="https://arxiv.org/abs/2004.13933" target="_blank">ArXiv</a>] with Neeldhara Misra and Chinmay Sonar IJCAI, 2020 [C25] Manipulating Node Similarity Measures in Networks [<a href="https://arxiv.org/abs/1910.11529" target="_blank">ArXiv</a>] with Sourav Medya AAMAS, 2020 [C24] Minimizing Margin of Victory for Fair Political and Educational Districting [<a href="https://arxiv.org/abs/1909.05583" target="_blank">ArXiv</a>] with Ana-Andreea Stoica, Abhijnan Chakraborty, and Krishna Gummadi AAMAS, 2020 [C23] A Parameterized Perspective on Protecting Elections [<a href="https://arxiv.org/abs/1905.11838" target="_blank">ArXiv</a>] 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 [<a href="https://arxiv.org/abs/1511.04190" target="_blank">ArXiv</a>] with Neeldhara Misra and Yadati Narahari Theoretical Computer Science, 2019 Remark: Conference version appeared in AAMAS, 2017. [C22] Testing Preferential Domains using Sampling [<a href="https://arxiv.org/abs/1902.08930" target="_blank">ArXiv</a>] with Swaprava Nath and Garima Shakya AAMAS, 2019 [C21] Covert Networks: How Hard is It to Hide? [<a href="https://arxiv.org/abs/1903.05832" target="_blank">ArXiv</a>] with Sourav Medya AAMAS, 2019 [C20] Local Distance Restricted Bribery in Voting [<a href="https://arxiv.org/abs/1901.08711" target="_blank">ArXiv</a>] AAMAS, 2019 (extended abstract) [C19] The Social Network Effect on Surprise in Elections [<a href="https://arxiv.org/abs/1801.10110" target="_blank">ArXiv</a>] with Pravesh Kothari and Swaprava Nath CODS-COMAD, 2019 [J6] An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems [<a href="https://arxiv.org/abs/1603.00213" target="_blank">ArXiv</a>] 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 [<a href="https://arxiv.org/abs/1711.03948" target="_blank">ArXiv</a>] Theoretical Computer Science, 2018 Remark: Conference version appeared in AAAI, 2018. [J4] Complexity of Manipulation with Partial Information in Voting [<a href="https://arxiv.org/abs/1604.04359" target="_blank">ArXiv</a>] 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 [<a href="https://arxiv.org/abs/1711.03948" target="_blank">ArXiv</a>] AAAI, 2018 [J3] Frugal Bribery in Voting [<a href="https://arxiv.org/abs/1504.08248" target="_blank">ArXiv</a>] with Neeldhara Misra and Yadati Narahari Theoretical Computer Science, 2017 Remark: Conference version appeared in AAAI, 2016. [C17] Query Complexity of Tournament Solutions [<a href="https://arxiv.org/abs/1611.06189" target="_blank">ArXiv</a>] AAAI, 2017 [C16] On the Exact Amount of Missing Information that makes Finding Possible Winners Hard [<a href="https://arxiv.org/abs/1610.08407" target="_blank">ArXiv</a>] with Neeldhara Misra MFCS, 2017 [C15] Parameterized Dichotomy of Choosing Committees Based on Approval Votes in the Presence of Outliers [<a href="https://arxiv.org/abs/1511.04190" target="_blank">ArXiv</a>] with Neeldhara Misra and Yadati Narahari AAMAS, 2017 [C14] Proportional Representation in Vote Streams [<a href="https://arxiv.org/abs/1702.08862" target="_blank">ArXiv</a>] with Nimrod Talmon and Otniel van Handel AAMAS, 2017 [J2] Kernelization Complexity of Possible Winner and Coalitional Manipulation Problems in Voting [<a href="https://arxiv.org/abs/1405.3865" target="_blank">ArXiv</a>] 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 [<a href="https://arxiv.org/abs/1603.00213" target="_blank">ArXiv</a>] with Arnab Bhattacharyya and David P. Woodruff PODS, 2016 [C12] Preference Elicitation for Single Crossing Domain [<a href="https://arxiv.org/abs/1604.05194" target="_blank">ArXiv</a>] with Neeldhara Misra IJCAI, 2016 [C11] Elicitation for Preferences Single Peaked on Trees [<a href="https://arxiv.org/abs/1604.04403" target="_blank">ArXiv</a>] with Neeldhara Misra IJCAI, 2016 [C10] Complexity of Manipulation with Partial Information in Voting [<a href="https://arxiv.org/abs/1604.04359" target="_blank">ArXiv</a>] with Neeldhara Misra and Yadati Narahari IJCAI, 2016 [C9] Frugal Bribery in Voting [<a href="https://arxiv.org/abs/1504.08248" target="_blank">ArXiv</a>] 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 [<a href="https://arxiv.org/abs/1305.5053" target="_blank">ArXiv</a>] 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 [<a href="https://arxiv.org/abs/1505.00566" target="_blank">ArXiv</a>] with Yadati Narahari IJCAI, 2015 [C7] Sample Complexity for Winner Prediction in Elections [<a href="https://arxiv.org/abs/1502.04354" target="_blank">ArXiv</a>] 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 [<a href="https://arxiv.org/abs/1404.2367" target="_blank">ArXiv</a>] with Neeldhara Misra and Yadati Narahari AAMAS, 2015 [C5] Kernelization Complexity of Possible Winner and Coalitional Manipulation Problems in Voting [<a href="https://arxiv.org/abs/1405.3865" target="_blank">ArXiv</a>] with Neeldhara Misra and Yadati Narahari AAMAS, 2015 [C4] Computational Complexity of Fundamental Problems in Social Choice Theory (Doctoral Consortium) [<a href="http://dl.acm.org/citation.cfm?id=2773532" target="_blank">AAMAS</a>] AAMAS, 2015 [C3] Asymptotic Collusion-Proofness of Voting Rules: The Case of Large Number of Candidates [<a href="https://arxiv.org/abs/1502.04354" target="_blank">ArXiv</a>] with Yadati Narahari AAMAS, 2014 (extended abstract) [C2] UNO Gets Easier for a Single Player [<a href="http://link.springer.com/chapter/10.1007%2F978-3-319-07890-8_13" target="_blank">FUN</a>] with Prachi Goyal and Neeldhara Misra FUN, 2014 [C1] Dynamic Multipath Bandwidth Provisioning with Jitter, Throughput and SLA constraint in MPLS over WDM network [<a href="http://link.springer.com/chapter/10.1007/978-3-642-11322-2_37" target="_blank">ICDCN</a>] with A. Kundu, M. K. Naskar, A. Mukherjee, and A. Nasipuri ICDCN, 2010 <hr> </body></html>