Welcome to my homepage


Contact Information

Prajakta Nimbhorkar
Associate Professor
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) Joint publication

Ph.D students

  1. Vishwa Prakash H. V. (2020-)Joint publication
  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 2022 Disjoint rank-maximal matchings in a bipartite graph
Sagnik Dasgupta 2022 Existence of possibly PROPx allocations

Research Interests

I am interested in complexity, algorithms.

Publications

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

    Vishwa Prakash H.V., Prajakta Nimbhorkar
    AAMAS 2024 (to appear)

  2. 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

  3. Critical Relaxed Stable Matchings with Two-Sided Ties

    Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan
    WG 2023

  4. Fair Healthcare Rationing to Maximize Dynamic Utilities

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

  5. 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.

  6. Popular Edges with Critical Nodes

    Kushagra Chatterjee, Prajakta Nimbhorkar
    ISAAC 2022

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

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

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

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

  9. Disjoint Stable Matchings in Linear Time

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

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

    Girija Limaye, Meghana Nasre, Prajakta Nimbhorkar
    SAGT 2020

  11. 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

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

    Meghana Nasre, Prajakta Nimbhorkar, and Nada Pulath
    WG 2019

  13. How good are popular matchings?


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

  14. Popular Matchings with Lower Quotas

    Meghana Nasre, and Prajakta Nimbhorkar
    FSTTCS 2017

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

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

  16. Dynamic Rank-maximal Matchings

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

  17. 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

  18. 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

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

    Vikraman Arvind and Partha Mukhopadhyay and Prajakta Nimbhorkar
    LATIN 2012.

  20. Pseudorandom Generators for Group Products

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

  21. Popularity at Minimum Cost

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

  22. 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.)

  23. 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.

  24. 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.

  25. 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.

  26. 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.