Neeldhara Misra

Use this for easy navigation to main pages. This is hidden on your site

Neeldhara Misra

Smt. Amba and Sri. V S Sastry Chair Associate Professor Computer Science and Engineering at IIT Gandhinagar Old homepage (The new website, i.e, this one, is work in progress, and the old one is dated. Sorry.)


My broad research interests include — in no particular order: algorithm design, computational social choice, combinatorial games. You can find out more about my work here.

If you enjoy reading content online, and are broadly interested in theoretical computer science, I would suggest subscribing to the TCS blog aggregator or simply following cstheory on Twitter.


Visualizing Baranyai's theorem with n=2.



Solo Chess
March 23, 2022
Joint work with N. R. Aravind and Harshil Mittal ⸱ To appear at FUN 2022 ⸱ Preprint available from ArXiV
We introduce a generalization of “Solo Chess”, a single-player variant of the game that can be played on We show that this version of the game is NP-complete even if played only by rooks with at most two captures left, or only by queens with exactly two captures left. On the other hand, solvable instances of rooks on 1D boards and pawns on 2D boards can efficiently characterized. Find out more on Twitter or at the blog.
CSE Open House
March 12, 2022
Members of the discipline of Computer Science and Engineering just concluded a virtual open house. You can now find out more about research directions in CSE at IIT Gandhinagar and the research opportunities that we offer. Please share these links with anyone that you think would find them useful!
Eternal Vertex Cover
March 11, 2022
Joint work with Saraswati Nanoti ⸱ To appear at CSR 2022 ⸱ Preprint available from ArXiV
Eternal Vertex Cover is a dynamic variant of the vertex cover problem. The complexity of the problem on bipartite graphs is open, as is the question of whether the problem admits a polynomial kernel. We settle both these questions by showing that Eternal Vertex Cover is NP-hard and does not admit a polynomial compression even on bipartite graphs of diameter six. We also show that the problem admits a polynomial time algorithm on the class of cobipartite graphs.
Imbalance Parameterized by Twin Cover
December 4, 2021
Joint work with Harshil Mittal ⸱ Published in Theoretical Computer Science (Dec 2021) ⸱ A shorter version was accepted at COCOON 2020 ⸱ Preprint available from ArXiV
Imbalance is a layout optimization problem, where we would like to order the vertices of a graph so that, roughly speaking, vertices have their neighbors split up as equally as possible on their left and right. We examine the parameterized complexity of the problem with respect to a structural parameter called twin cover.
Local Fair Division
November 22, 2021
Joint work with Debanuj Nayak ⸱ Accepted at CALDAM 2022 ⸱ Preprint available from ArXiV
These developments explore the complexity of finding envy-free allocations of indivisible items in settings where envy is only experienced between friends, the valuations over items are binary, and the social network over agents is given by an undirected graph.