Welcome to my homepage

Contact Information

Teaching

Academic Background

• 2007-2010: Ph.D.(Computer Science) at The Institute of Mathematical Sciences, Chennai (... continued from TIFR)
  Thesis Advisor: Prof. Meena Mahajan
  Thesis Title: Complexity analysis of some problems in planar graphs, bounded tree-width graphs, and planar point sets
  
  
• 2005-2007: Ph.D.(Computer Science) at Tata Institute of Fundamental Research, Mumbai
  
  
• 2003-2005: M.Tech.(IT) from Kanwal Rekhi School of IT, IIT Bombay
  
  
• 1999-2003 : B.E. (CSE) from Govt. College of Engineering, Aurangabad
  
  
• 1999: H.S.C. from Saraswati Bhuwan College of Science, Aurangabad
  
  
• 1997: S.S.C. from Sharda Mandir Girls' School, Aurangabad
  

Research Interests

Publications

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

  Vikraman Arvind and Partha Mukhopadhyay and Prajakta Nimbhorkar
  LATIN 2012 (To appear).

• Pseudorandom Generators for Group Products

  Michal Koucký and Prajakta Nimbhorkar and Pavel Pudlák
  STOC 2011 (To appear).

• Popularity at Minimum Cost

  Telikepalli Kavitha and Meghana Nasre and Prajakta Nimbhorkar
  ISAAC 2010.

• Log-space Algorithms for Paths and Matchings in k-trees

  Samir Datta and Bireswar Das and Prajakta Nimbhorkar
  STACS 2010.

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

• Planar Graph Isomorphism is in Log-space

  Samir Datta and Nutan Limaye and Prajakta Nimbhorkar and Thomas Thierauf and Fabian Wagner
  CCC 2009.

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

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

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

Teaching

Links to some photo albums:

• New Zealand trip



• Russia trip



• Germany-France trip



• Israel trip



• Prague trip