Welcome to my homepage


Contact Information

Prajakta Nimbhorkar
Professor G
Chennai Mathematical Institute
Plot H1, SIPCOT IT Park
Padur PO, Siruseri 603103
India
Email: my first name % cmi % ac % in
(Replace % with appropriate characters and insert my first name)

Academic Background

Teaching


Post-doctoral fellows

Pratik Ghosal (Nov 2020-May 2023)

Ph.D students

  1. Vishwa Prakash H. V. (2020-)
  2. Harish Chandramouleeswaran (2023-)

M.Sc. students advised

Name Year Thesis title Publication (if any)
Nikhil Mande 2013 Spectral graph theory
Pratik Ghosal 2013 A survey on matchings with preferences Link
Biman Roy (Jointly with Prof. Meena Mahajan) 2013 Unified theory of pseudorandomness
Sayantan Sen 2018 A survey on rank-maximal matchings
Souvik Parial 2019 A survey on popular and dominant matchings
Vishwa Prakash H.V. (Joint with Dr. G.Philip) 2020 Disjoint stable matchings Link
Pratiksha Mondal 2020 Matchings with incentives and cheating strategies
Sagarika Shahane 2020 Approximation algorithms for uncapacitated facility location problem
Ankita Sarkar 2020 Popular Matchings under Lower Quotas and their relationship to Stability under Classifications Link
Saideep Bhosale 2021 Strongly stable matchings
Kushagra Chatterjee 2021 Popular edge problem with privileged men Link
Samiparna Biswas 2023 Disjoint rank-maximal matchings in a bipartite graph
Sagnik Dasgupta 2023 Existence of possibly PROPx allocations
Arghyadeep Chakraborty 2024 Capacity modification for many-to-one matching problems
Suneet Patil 2025 Envy-free house allocation
Deepro Sarkar 2025 Envy-freeness with subsidy (tentative title)

Research Interests

I am interested in complexity, algorithms.

Publications

  1. EFX Exists for Three Types of Agents

    Vishwa Prakash H. V., Pratik Ghosal, Prajakta Nimbhorkar, Nithin Varma (To appear at EC 2025)

  2. Optimal Capacity Modification for Stable Matchings with Ties

    Keshav Ranjan, Meghana Nasre, Prajakta Nimbhorkar (To appear at IJCAI 2025)

  3. Fair Division in a Variable Setting

    Harish Chandramouleeswaran, Prajakta Nimbhorkar, Nidhi Rathi (To appear at AAMAS 2025)

  4. Almost EFX for Three Types of Agents

    Pratik Ghosal, Vishwa Prakash H V, Prajakta Nimbhorkar, Nithin Varma (To appear at AAAI 2025)

  5. Individual Fairness under Group Fairness Constraints in Bipartite Matching - One Framework to Approximate Them All

    Atasi Panda, Anand Louis, Prajakta Nimbhorkar (IJCAI 2024)

  6. Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings

    Vishwa Prakash H.V., Prajakta Nimbhorkar
    AAMAS 2024 and 6th GAIW workshop at AAMAS 2024

  7. Online Algorithms for Matchings with Proportional Fairness Constraints and Diversity Constraints(the arxiv version is older)

    Anand Louis, Meghana Nasre, Prajakta Nimbhorkar, Govind S. Sankar
    ECAI 2023

  8. Critical Relaxed Stable Matchings with Two-Sided Ties

    Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan
    WG 2023

  9. Fair Healthcare Rationing to Maximize Dynamic Utilities

    Aadityan Ganesh, Pratik Ghosal, Vishwa Prakash HV, Prajakta Nimbhorkar
    PAKDD 2023

  10. Planar Graph Isomorphism is in Log-space

    Samir Datta and Nutan Limaye and Prajakta Nimbhorkar and Thomas Thierauf and Fabian Wagner
    ACM ToCT 2022, and a preliminary version in CCC 2009.

  11. Popular Edges with Critical Nodes

    Kushagra Chatterjee, Prajakta Nimbhorkar
    ISAAC 2022

  12. Popular Matchings in the Hospital-Residents Problem with Two-sided Lower Quotas

    Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, Ankita Sarkar
    FSTTCS 2021

  13. Matchings with Group Fairness Constraints: Online and Offline Algorithms

    Govind Sankar, Anand Louis, Meghana Nasre, Prajakta Nimbhorkar
    IJCAI 2021

  14. Disjoint Stable Matchings in Linear Time

    Aadityan Ganesh, Vishwa Prakash H V, Prajakta Nimbhorkar, Geeverghese Philip
    WG 2021

  15. Envy-freeness and Relaxed Stability: Hardness and Approximation Algorithms

    Girija Limaye, Meghana Nasre, Prajakta Nimbhorkar
    SAGT 2020

  16. Many-to-one Popular Matchings with Two-sided Preferences and One-sided Ties

    Kavitha Gopal, Meghana Nasre, Prajakta Nimbhorkar and T Pradeep Reddy
    COCOON 2019

  17. Classified Rank-Maximal Matchings and Popular Matchings -- Algorithms and Hardness

    Meghana Nasre, Prajakta Nimbhorkar, and Nada Pulath
    WG 2019

  18. How good are popular matchings?


    Krishnapriya A M, Meghana Nasre, Prajakta Nimbhorkar, and Amit Rawat
    SEA 2018

  19. Popular Matchings with Lower Quotas

    Meghana Nasre, and Prajakta Nimbhorkar
    FSTTCS 2017

  20. Computing the maximum using (min,+) formulas

    Meena Mahajan, and Prajakta Nimbhorkar, and Anuj Tawari
    MFCS 2017

  21. Dynamic Rank-maximal Matchings

    Prajakta Nimbhorkar and Arvind Rameshwar V.
    Journal of combinatorial optimization (2019)
    A preliminary version appeared in COCOON 2017

  22. Rank-maximal Matchings: Structure and Algorithms

    Pratik Ghosal and Meghana Nasre and Prajakta Nimbhorkar
    Theoretical Computer Science (2019)
    A preliminary version appeared in ISAAC 2014

  23. Near-Optimal Expanding Generating Sets for Solvable Permutation Groups

    Vikraman Arvind and Partha Mukhopadhyay and Prajakta Nimbhorkar and Yadu Vasudev SIAM journal of discrete mathematics (2018)
    MFCS 2012

  24. Erdős-Rényi Sequences and Deterministic construction of Expanding Cayley Graphs

    Vikraman Arvind and Partha Mukhopadhyay and Prajakta Nimbhorkar
    LATIN 2012.

  25. Pseudorandom Generators for Group Products

    Michal Koucký and Prajakta Nimbhorkar and Pavel Pudlák
    STOC 2011.

  26. Popularity at Minimum Cost

    Telikepalli Kavitha and Meghana Nasre and Prajakta Nimbhorkar
    Journal of Combinatorial Optimization, 2012. (A preliminary version appeared in ISAAC 2010.)

  27. Log-space Algorithms for Paths and Matchings in k-trees

    Samir Datta and Bireswar Das and Prajakta Nimbhorkar
    Theory of Computing Systems. (A preliminary version appeared in STACS 2010.)

  28. Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space

    Samir Datta and Prajakta Nimbhorkar and Thomas Thierauf and Fabian Wagner
    FSTTCS 2009.

  29. The planar k-means problem is NP-hard

    Meena Mahajan and Prajakta Nimbhorkar and Kasturi R. Varadarajan.
    To appear in Theoretical Computer Science, special issue for WALCOM 2009. A preliminary version appeared in Proceedings of 3rd Annual Workshop on Algorithms and Computation WALCOM, 18-20 Feb 2009, Kolkata.

  30. Longest Paths in Planar DAGs in Unambiguous Logspace

    Nutan Limaye and Meena Mahajan and Prajakta Nimbhorkar.
    In Chicago Journal of Theoretical Computer Science CATS 2009 special issue, 2010(8), 2010.
    A preliminary version appeared in Computing: The Australasian Theory Symposium CATS , January 2009, New Zealand.

    A preliminary version with a subset of these results appears as a technical report on the Computing Research Repository:arXiv:0802.1699v1, 2008.

  31. 3-connected planar graph isomorphism is in Logspace

    Samir Datta and Nutan Limaye and Prajakta Nimbhorkar.
    In Proceedings of Foundations of Software Technology and Theoretical Computer Science, FST & TCS, 2008.