Meena Mahajan
Professor
Theoretical Computer Science
2254 3307
meena @ imsc . res . in
307 New Building
Research Interests:
- Complexity Theory: algebraic complexity, counting classes, proof complexity, circuits, communication ...
- Combinatorial and Discrete Algorithms
Education:
- PhD, IIT Madras, 1993.
- MTech by Research (Computer Science & Engg), IIT Bombay, 1988.
- BTech (Computer Science & Engg), IIT Bombay, 1986.
Career History:
- Faculty at IMSc since 1994
- Post-doctoral fellow at IMSc during 1993
Courses Taught:
- Introduction to Computational Complexity
- Derandomization and PCPs
- Circuit Complexity
- Boolean Function Complexity
- Matchings in Graphs
- Linear Programming and Combinatorial Optimization
- Communication Complexity
- Concrete Lower Bounds
- Proof Complexity
- Discrete Mathematics
- Theory of Computation
- Data Structures and Algorithms
- Computational Geometry
- Combinatorial Geometry
Selected publications:
- Some Complete and Intermediate Polynomials in Algebraic Complexity TheoryMeena Mahajan and Nitin Saurabh.In Theory of Computing Systems (TOCS) 62(3):622-652, 2018, (special issue for CSR 2016). CSR 2016.
- Feasible Interpolation for QBF Resolution CalculiOlaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla.Logical Methods in Computer Science, June 8, 2017, Volume 13, Issue 2.
- Space-Efficient Approximations for Subset Sum.Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah.ACM Transactions on Computation Theory, Vol. 8, Issue 4, 16:1-28, June 2016.
- Counting paths in VPA is complete for #NC^1.Andreas Krebs and Nutan Limaye and Meena Mahajan.Algorithmica Volume 64, Issue 2, Page 279-294, 2012. special issue for COCOON 2010.
- Some perfect matchings and perfect half-integral matchings in NC. Raghav Kulkarni, Meena Mahajan and Kasturi R. Varadarajan.Chicago Journal of Theoretical Computer Science, Volume 2008 Article 4.
- Approximate Block Sorting.Meena Mahajan and R. Rama and Venkatesh Raman and S Vijayakumar.International Journal of Foundations of Computer Science Volume 17(2) (April 2006), pp. 337--355.
- Determinant: Old Algorithms, New Insights Meena Mahajan and V Vinay.SIAM Journal on Discrete Mathematics , 12(4), 474--490, 1999.
- Non-commutative arithmetic circuits: depth reduction and size lower bounds. Eric Allender, J. Jiao, Meena Mahajan and Vinay.Theoretical Computer Science , Vol. 209 (1,2) (1998), pp. 47-86.