Research Publications of Meena Mahajan

Papers and Reports:

• Small-space analogues of Valiant's classes.

  Meena Mahajan and B. V. Raghavendra Rao.
  Proceedings of 17th International Symposium on Fundamentals of Computation Theory FCT, 2-4 Sep 2009, Wroclaw, Poland.
  Springer-Verlag Lecture Notes in Computer Science series Volume 5699 pp.250--261.

• Membership testing: Removing extra stacks from multi-stack pushdown automata.

  Nutan Limaye and Meena Mahajan.
  Proceedings of 3rd International Conference on Language and Automata Theory and Applications LATA, April 2009, Tarragona, Spain. .
  Springer-Verlag Lecture Notes in Computer Science series Volume 5457 pp.493--504.

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

  Meena Mahajan and Prajakta Nimbhorkar and Kasturi R. Varadarajan.
  Proceedings of 3rd Annual Workshop on Algorithms and Computation WALCOM, 18-20 Feb 2009, Kolkata.
  Springer-Verlag Lecture Notes in Computer Science series Volume 5431 pp.274--285.

• Longest Paths in Planar DAGs in Unambiguous Logspace

  Nutan Limaye and Meena Mahajan and Prajakta Nimbhorkar.

  To appear in Chicago Journal of Theoretical Computer Science, special issue for CATS 2009.
  

  A preliminary version appeared in Computing: The Australasian Theory Symposium CATS , January 2009, New Zealand.
  CRPIT Series Volume 94, pp. 99--105.

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

• Parameterizing Above or Below Guaranteed Values.

  Meena Mahajan and Venkatesh Raman and Somnath Sikdar.
  Journal of Computer and System Sciences.
  Vol 75 (2), pp. 137--153, 2009.
  (This includes and extends the work reported in the paper "Parameterizing MAXSNP problems above Guaranteed Value"; see below.)

• Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae

  Meena Mahajan and B. V. Raghavendra Rao.
  
  Proceedings of 33rd International Symposium on Mathematical Foundations of Computer Science MFCS, Aug 25--29, 2008, Torun .
  Springer-Verlag Lecture Notes in Computer Science series Volume 5162 pp.455--466.
  The full version is a Technical report of the ECCC: TR08-048, 2008.
  

• Rigidity of a simple extended lower triangular matrix.

  Meena Mahajan and Jayalal Sarma M. N .
  Information Processing Letters .
  Volume 107(5), pp. 149--153, 2008.
  
  

• On the complexity of membership and counting in height-deterministic pushdown automata.

  Nutan Limaye and Meena Mahajan and Antoine Meyer.
  Submitted.
  A preliminary version appeared in Proceedings of 3rd International Computer Science Symposium in Russia CSR, June 7--12, 2008, Moscow . Springer-Verlag Lecture Notes in Computer Science series Volume 5010 pp.240--251.
  

• Upper Bounds for Monotone Planar Circuit Value and Variants.

  Nutan Limaye and Meena Mahajan and Jayalal Sarma M. N
  Computational Complexity.
  Volume 18(3), pp. 377--412, Oct 2009.
  
  (This includes and extends the work reported in the paper "Evaluating Monotone Circuits on Cylinders, Planes and Tori"; see below.)

• Planarity, Determinants, Permanents, and (Unique) Perfect Matchings.

  Samir Datta, Raghav Kulkarni, Nutan Limaye and Meena Mahajan.
  to appear in Transactions on Computation Theory.
  preliminary version in Proceedings of 2nd International Computer Science Symposium in Russia CSR, Sep 3--7, 2007, Ekaterinburg. Springer-Verlag Lecture Notes in Computer Science series Volume 4649 pp 115--126.
  

• Polynomial size log depth circuits: between NC1 and AC1.

  in The Computational Complexity Column, Bulletin of the EATCS, Number 91, Feb 2007.

• Arithmetizing Classes arround NC1 and L

  Nutan Limaye and Meena Mahajan and B. V. Raghavendra Rao.
  Theory of Computing systems , special issue for STACS 2007.
  Volume 46(3), pp. 499--522, April 2010.
  
  A preliminary version appeared in Proceedings of 24th International Symposium on Theoretical Aspects of Computer Science STACS, 22-24 Feb 2007, Aachen (Germany). Springer-Verlag Lecture Notes in Computer Science series Volume 4393 pp 477--488.
  

• On the complexity of matrix rank and rigidity.

  Meena Mahajan and Jayalal Sarma M. N .
  Theory of Computing systems , special issue for CSR 2007.
  Volume 46(1), pp. 9--26, January 2010.
  
  A preliminary version appears in Proceedings of 2nd International Computer Science Symposium in Russia CSR, Sep 3--7, 2007, Ekaterinburg . Springer-Verlag Lecture Notes in Computer Science series Volume 4649 pp 269--280.
  

• Parameterizing MAXSNP problems above Guaranteed Values.

  Meena Mahajan and Venkatesh Raman and Somnath Sikdar.
  Proceedings of 2nd International Workshop on Parameterized and Exact Computation IWPEC'06, 13 - 15 Sep, 2006, Zuerich (Switzerland). (part of ALGO 2006) .
  Springer-Verlag Lecture Notes in Computer Science series Volume 4169 pp 38--49.
  

• On the Bipartite Unique Perfect Matching Problem.

  Thanh Minh Hoang and Meena Mahajan and Thomas Thierauf.
  Proceedings of 33rd International Colloquium on Automata, Languages and Programming ICALP, 9--16 July 2006, Venice (Italy).
  Springer-Verlag Lecture Notes in Computer Science series Volume 4051 pp 453--464.
  

• Evaluating Monotone Circuits on Cylinders, Planes and Tori

  Nutan Limaye and Meena Mahajan and Jayalal Sarma M. N
  Proceedings of 23rd Symposium on Theoretical Aspects of Computer Science STACS, 23-25 Feb 2006.
  Springer-Verlag Lecture Notes in Computer Science series Volume 3884 pp 660-671.
  The full version is a technical report of the ECCC.

• Simultaneous Matchings: Hardness and Approximation.

  Khaled Elbassioni and Irit Katriel and Martin Kutz and Meena Mahajan
  Journal of Computer and System Sciences.
  Volume 74(5), pp. 884--897, August 2008.
  
  A preliminary version appeared in Proceedings of 16th Annual International Symposium on Algorithms and Computation ISAAC, 19--21 Dec 2005.
  Springer-Verlag Lecture Notes in Computer Science series Volume 3827 pp 106--115.
  Copyright held by Springer-Verlag.
  

• Block Sorting: A Characterization and some Heuristics.

  Meena Mahajan and R. Rama and S Vijayakumar
  Nordic Journal of Computing .
  Volume 14 (2007), pp. 126--150.
  
  (This includes and extends the work reported in the paper "Towards constructing optimal strip move sequences"; see below.)

• A non-regular leftist language

  Suman Bandyopadhyay and Meena Mahajan and K. Narayan Kumar
  manuscript .
  

• Seeking a vertex of the planar matching polytope in NC.

  Raghav Kulkarni and Meena Mahajan
  Proceedings of the Twelfth Annual European Symposium on Algorithms (ESA) 2004 , 14--17 Sept (Bergen, Norway), Springer-Verlag Lecture Notes in Computer Science series Volume 3221 pp. 472--483.
  Copyright held by Springer-Verlag.

• Towards constructing optimal strip move sequences.

  Meena Mahajan and R. Rama and S Vijayakumar
  Proceedings of the Tenth International Computing and Combinatorics Conference (COCOON) 2004 , 17--20 August (Jeju Island, Korea), Springer-Verlag Lecture Notes in Computer Science series Volume 3106 pp. 33-42.
  Copyright held by Springer-Verlag.

• 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.
  
  A preliminary version of this paper appeared under the title
  Merging and Sorting By Strip Moves
  in the Proceedings of the 23rd Annual International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS) 2003 , 15--17 December (Mumbai, India), Springer-Verlag Lecture Notes in Computer Science series Volume 2914 pp. 314--325.

• On Sorting by 3-Bounded Transpositions.

  Meena Mahajan and R. Rama and S Vijayakumar.
  Discrete Mathematics .
  Vol. 306 (14) (2006), pp. 1569--1585.
  An extended abstract appears in the Electronic Notes in Discrete Mathematics Volume 15, Oct 2003.
  Presented at the R. C. Bose Centenary Symposium on Discrete Mathematics and Applications. 20--23 December 2002, ISI Kolkata.

• Madhu Sudan gets the Nevanlinna Prize.

  Research News article by Priti Shankar and Meena Mahajan.
  in Resonance: Journal of Science Education, Vol.7 (12) (2002) pp. 84--90.

• A new NC-algorithm for finding a perfect matching in planar and bounded genus graphs.

  Meena Mahajan and Kasturi R. Varadarajan.
  Proceedings of the 32nd Annual ACM Symposium on Theory of Computing STOC 2000 , 21--23 May (Oregon, USA), pp 351--357.
  Copyright held by ACM

• The Complexity of Planarity Testing.

  Eric Allender and Meena Mahajan.
  Information and Computation
  Vol. 189 (1) (2004), pp. 117--134.
  This is a revision of an extended abstract that appears in Proceedings of the 17th International Symposium on Theoretical Aspects of Computer Science STACS 2000, 17--19 February (Lille, France), in the Springer-Verlag Lecture Notes in Computer Science series Volume 1770, pp. 87--98.

• Arithmetic Complexity, Kleene Closure, and Formal Power Series.

  Eric Allender, V. Arvind and Meena Mahajan.
  Theory of Computing Systems. Vol. 36 (4) (2003), pp. 303--328.

• The Combinatorial Approach Yields an NC Algorithm for Computing Pfaffians

  Meena Mahajan, P. R. Subramanya and V Vinay.
  Discrete Applied Mathematics.
  143(1--3), 1--16, 2004.
  A preliminary version appears in the Proceedings of the Fifth Annual International Computing and Combinatorics Conference COCOON 1999, in the Springer-Verlag Lecture Notes in Computer Science series Volume 1627, pp. 134--143.

• Determinant: Old Algorithms, New Insights

  Meena Mahajan and V Vinay.
  SIAM Journal on Discrete Mathematics, 12(4), 474--490, 1999.
  A preliminary version appears in Proceedings of the Sixth Scandinavian Workshop on Algorithm Theory (SWAT'98) LNCS 1432, July 8--10 1998 (Stockholm, Sweden), pp 276--287.

• Parametrizing above Guaranteed Values: MaxSat and MaxCut.

  Meena Mahajan and Venkatesh Raman .
  Journal of Algorithms , 31(2), 335-354, 1999.

• Determinant: Combinatorics, Algorithms, and Complexity

  Meena Mahajan and V Vinay.
  Chicago Journal of Theoretical Computer Science, Volume 1997 Article 5.
  A preliminary version titled A combinatorial algorthm for the determinant appears in the Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 97 (New Orleans, Louisiana, USA), pp. 730-738, with
  copyright held by ACM.

• Applications of Universal Hashing in Complexity Theory.

  Tutorial Report by V. Arvind and Meena Mahajan.
  in Proceedings of the 6th National Seminar on Theoretical Computer Science}, Aug 1996, (Banasthali, Rajasthan, India) Allied Publishers, pp. 57--83.

• Logspace verifiers, NC, and NP.

  Lokam V. Satyanarayana, Meena Mahajan and V Vinay.
  Proceedings of the Sixth Annual International Symposium on Algorithms and Computation ISAAC , Dec 1995 (Cairns, Australia), LNCS 1004, pp. 52-61.

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

  This subsumes a paper titled Non-commutative computation, depth reduction, and skew circuits by Meena Mahajan and V Vinay, that appeared in the Proceedings of the 14th International Foundations of Software Technology and Theoretical Computer Science FST&TCS Conference Dec 1994 (Madras), in the Springer-Verlag Lecture Notes in Computer Science series Vol 880, pp. 48--59.

• A note on Mod and generalised Mod classes.

  Vinodchandran N.V. and Meena Mahajan.
  Information Processing Letters , 55(1) (1995), pp. 27-31.

• A note on SpanP functions.

  Meena Mahajan, Thomas Thierauf and Vinodchandran N.V.
  Information Processing Letters , 51 (1994), pp. 7-10.

• Nondeterministic, probabilistic and alternating computations on cellular array models.

  Kamala Krithivasan and Meena Mahajan.
  Theoretical Computer Science, Vol.143 (1995), pp.23--49.
  A preliminary version was presented at the Developments in Language Theory Conference, Turku, Finland, 12--15 July 1993.

• Language operations on cellular automata classes.

  Meena Mahajan and Kamala Krithivasan
  Journal of Mathematical and Physical Sciences Vol.27 (1993).

• Languages classes defined by time-bounded relativised cellular automata.

  Meena Mahajan and Kamala Krithivasan
  R.A.I.R.O. Theoretical Informatics and Applications Vol .27 (5) (1993), pp. 403--432.

• Some results on time-varying and relativised cellular automata.

  Meena Mahajan and Kamala Krithivasan
  International Journal of Computer Mathematics Vol. 43 (1,2) (1992), pp. 21--38.

• ``Forgetful'' L systems.

  Meena Mahajan, M. V. Nagendra Prasad and Kamala Krithivasan
  In Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics and Developmental Biology,
  editors G. Rozenberg and A. Salomaa, Springer-Verlag, 1992, pp. 419--436.

• Relativised cellular automata and complexity classes.

  Meena Mahajan and Kamala Krithivasan
  Proceedings of the 11th International Foundations of Software Technology and Theoretical Computer Science FST&TCS Conference Dec 1991 (New Delhi), in the Springer-Verlag Lecture Notes in Computer Science series Vol 560, pp. 172--185.

• Fuzzy L systems.

  M. V. Nagendra Prasad, Meena Mahajan and Kamala Krithivasan
  International Journal of Computer Mathematics Vol. 36 (3,4) (1990), pp. 139--162.

• Systolic pyramid automata, cellular automata and array languages.

  Kamala Krithivasan and Meena Mahajan
  International Journal of Pattern Recognition and Artificial Intelligence Vol. 3 (3,4) (1989), pp. 405--433.

• Hexagonal cellular automata.

  Kamala Krithivasan and Meena Mahajan
  In A Perspective in Theoretical Computer Science --- Commemorative Volume for Gift Siromoney,
  editor R. Narasimhan, World Scientific (Singapore), 1989, pp. 134--164.

• Studies in language classes defined by different types of time-varying cellular automata.

  Doctoral Thesis, 1993.
  Thesis work done at the Department of Computer Science and Engineering, Indian Institute of Technology, Madras, under the supervision of Kamala Krithivasan .