Meena Mahajan
- Complexity Theory: algebraic complexity, counting classes, proof complexity, circuits, communication ...
- Combinatorial and Discrete Algorithms
- PhD, IIT Madras, 1993.
- MTech by Research (Computer Science & Engg), IIT Bombay, 1988.
- BTech (Computer Science & Engg), IIT Bombay, 1986.
- Faculty at IMSc since 1994
- Post-doctoral fellow at IMSc during 1993
- 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
- Discrete Mathematics
- Theory of Computation
- Data Structures and Algorithms
- Computational Geometry
- Combinatorial Geometry
-
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory
Meena 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 Calculi
Olaf 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.