
The shifted partial derivative complexity of Elementary Symmetric Polynomials
Herve Fournier,
Nutan Limaye,
Meena Mahajan,
Srikanth Srinivasan.
to appear in MFCS 2015.

Feasible Interpolation for QBF Resolution Calculi
Olaf Beyersdorff,
Leroy Chew,
Meena Mahajan,
Anil Shukla.
to appear in ICALP 2015.
ECCC TR 15059 .

Anna Gal,
JingTang Jang,
Nutan Limaye,
Meena Mahajan,
Karteek Sreenivasaiah.
ECCC TR 14180 .
(This includes the work reported in the paper
"The complexity of unary subset sum." that appeared in
COCOON 2012; see below.)

Arnaud Durand,
Meena Mahajan,
Guillaume Malod,
Nicolas de RugyAltherre and
Nitin Saurabh.
Proceedings of the 34th Annual International
Conference on Foundations of Software Technology
and Theoretical Computer Science (FSTTCS),
1517 December 2014, (Delhi, India), LIPIcs.
Full version:
ECCC TR 14163 .

Meena Mahajan,
B. V. Raghavendra Rao and
Karteek Sreenivasaiah.
Proceedings of 20th Annual International Computing and Combinatorics Conference
COCOON, 46 Aug 2014, Atlanta, USA..
SpringerVerlag Lecture Notes in Computer Science
Volume 8591, pp.112.

Meena Mahajan,
B. V. Raghavendra Rao and
Karteek Sreenivasaiah.
Theoretical Computer Science
524, 90102, 2014.
A preliminary version titled
Identity Testing, multilinearity testing, and monomials in
ReadOnce/Twice Formulas and Branching Programs
appeared in
Proceedings of Proc. 37th International Symposium on
Mathematical Foundations of Computer Science MFCS
2731 Aug 2012, Bratislava, Slovakia.
SpringerVerlag Lecture Notes in Computer Science
Volume 7464, pp.655667.

Andreas Krebs,
Nutan Limaye,
Meena Mahajan, and
Karteek Sreenivasaiah.
Proceedings of 38th International
Symposium on Mathematical Foundations of Computer Science MFCS,
Aug 2013,
Klosterneuburg, Austria.
SpringerVerlag Lecture Notes in Computer Science
Volume 8087, pp.583594.
ECCC TR 13102 .

Nutan Limaye and
Meena Mahajan and
Karteek Sreenivasaiah.
Proceedings of 18th Annual International Computing and Combinatorics Conference
COCOON, 2022 Aug 2012, Sydney, Australia..
SpringerVerlag Lecture Notes in Computer Science
Volume 7434, pp.458469.

Meena Mahajan.
to appear in
Perspectives in Computational Complexity
Vol. 26 in Springer Series: Progress in Computer Science and Applied
Logic;
In Honor of Somenath Biswas on His Sixtieth Birthday.
See also
Workshop on
Complexity and Logic (in celebration of the 60th birthday of
Somenath Biswas), 2012.

Meena Mahajan and Nitin Saurabh and
Karteek Sreenivasaiah.
The 18th CATS symposium (Computing: the Australasian Theory
Symposium), 30 Jan  2 Feb 2012, Melbourne, Australia,
CRPIT series Vol.\ 128, pp.\ 5968.

Olaf Beyersdorff,
Samir Datta,
Andreas Krebs,
Meena Mahajan,
Gido ScharfenbergerFabian,
Karteek Sreenivasaiah,
Michael Thomas, and
Heribert Vollmer.
ECCC TR 12079 .
ACM Transactions on Computation Theory,Vol 5 issue 1 May 2013,
article 2: 123 .
A preliminary version appeared in
Proceedings of 36th International
Symposium on Mathematical Foundations of Computer Science MFCS,
Aug 2011,
Warsaw, Poland.
SpringerVerlag Lecture Notes in Computer Science
Volume 6907, pp.8495.

Meena Mahajan and
B. V. Raghavendra Rao.
Computational Complexity, Vol 22 pp 138, 2013.
(This includes the work reported in the paper
"Smallspace analogues of Valiant's classes" that appeared in
FCT 2009; see below.)

Maurice Jansen and Meena Mahajan and
B. V. Raghavendra Rao.
Computational Complexity
Vol 22(3), pp 517564, 2013.
(This includes and extends the work reported in the paper
"Arithmetic circuits, syntactic multilinearity, and
the limitations of skew formulae"; see
below.)

Samir Datta,
Meena Mahajan,
B. V. Raghavendra Rao,
Michael Thomas, and
Heribert Vollmer.
Theoretical Computer Science (special issue for
MFCS 2010)
Vol 417, pp 3649, 2012.
Proceedings of 35th International
Symposium on Mathematical Foundations of Computer Science MFCS,
Aug 2010,
Czech Republic.
SpringerVerlag Lecture Notes in Computer Science series
Volume 6281 pp.306317.

Andreas Krebs and
Nutan Limaye and
Meena Mahajan.
Algorithmica
Volume 64, Issue 2, Page
279294, 2012. special issue for
COCOON 2010.
A preliminary version appeared in
Proceedings of 16th International Computing and
Combinatorics Conference COCOON,
1921 July, 2010,
Vietnam.
SpringerVerlag
Lecture Notes in Computer Science series
Volume 6196
pp.4453.

Meena Mahajan and
B. V. Raghavendra Rao.
Proceedings of 17th International Symposium on
Fundamentals of Computation Theory FCT,
24 Sep 2009,
Wroclaw, Poland.
SpringerVerlag
Lecture Notes in Computer Science series
Volume 5699 pp.250261.

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

Meena Mahajan and
Prajakta Nimbhorkar and
Kasturi R. Varadarajan.
Theoretical Computer Science (special issue for
WALCOM 2009)
Vol 442, pp. 1321, 2012.
A preliminary version appeared in
Proceedings of 3rd Annual Workshop on Algorithms and
Computation WALCOM,
1820 Feb 2009, Kolkata.
SpringerVerlag
Lecture Notes in Computer Science series Volume 5431
pp.274285.

Nutan Limaye and
Meena Mahajan and
Prajakta Nimbhorkar.
Chicago Journal of Theoretical Computer Science (special
issue for CATS 2009)
Volume 2010 Article 8.
A
preliminary version appeared in
Computing: The
Australasian Theory Symposium CATS ,
January 2009, New Zealand.
CRPIT Series Volume 94, pp. 99105.

Raghav Kulkarni, Meena Mahajan and
Kasturi
R. Varadarajan.
Chicago Journal of Theoretical Computer Science,
Volume 2008 Article 4.

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

Meena Mahajan and
B. V. Raghavendra Rao.
Proceedings of 33rd International Symposium on Mathematical
Foundations of Computer Science MFCS, Aug 2529, 2008, Torun .
SpringerVerlag Lecture Notes in Computer Science series
Volume 5162
pp.455466.
The
full version is a Technical report of
the ECCC:
TR08048, 2008.

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

Nutan Limaye and
Meena Mahajan and
Antoine Meyer.
Journal of Automata, Languages and Combinatorics
Volume 14(3,4), pp. 211235, 2009.
A
preliminary version appeared in
Proceedings of 3rd International Computer Science
Symposium in Russia CSR, June 712, 2008, Moscow .
SpringerVerlag Lecture Notes in Computer Science series
.

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

Samir Datta,
Raghav Kulkarni,
Nutan Limaye and
Meena Mahajan.
ACM Transactions on Computation Theory,
Vol 1, No. 3, 10, March 2010.
preliminary version in
Proceedings of 2nd International Computer Science
Symposium in Russia CSR, Sep 37, 2007, Ekaterinburg.
SpringerVerlag Lecture Notes in Computer Science series
Volume 4649 pp 115126.

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

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

Meena Mahajan and
Jayalal Sarma M. N .
Theory of Computing systems (special
issue for CSR 2007).
Volume 46(1), pp. 926, January 2010.
A preliminary version appears in
Proceedings of 2nd International Computer Science
Symposium in Russia CSR, Sep 37, 2007, Ekaterinburg
.
SpringerVerlag Lecture Notes in Computer Science series
Volume 4649 pp 269280.

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) .
SpringerVerlag Lecture Notes in Computer Science series
Volume 4169 pp 3849.

Thanh Minh Hoang and Meena Mahajan and
Thomas Thierauf.
Proceedings of 33rd International
Colloquium on Automata, Languages and Programming
ICALP, 916 July 2006, Venice (Italy).
SpringerVerlag Lecture Notes in Computer Science series
Volume 4051 pp 453464.

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

Khaled Elbassioni and
Irit Katriel and
Martin Kutz and
Meena Mahajan
Journal of Computer and System Sciences
Volume 74(5), pp. 884897, August 2008.
A preliminary version appeared in
Proceedings of 16th Annual International
Symposium on Algorithms and Computation ISAAC, 1921 Dec 2005.
SpringerVerlag Lecture Notes in Computer Science series
Volume 3827 pp 106115.
Copyright held by SpringerVerlag.

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

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

Raghav Kulkarni and Meena Mahajan
Proceedings of the
Twelfth Annual European Symposium on Algorithms (ESA)
2004 ,
1417 Sept (Bergen, Norway),
SpringerVerlag
Lecture Notes in Computer Science series
Volume 3221
pp. 472483.
Copyright held by SpringerVerlag.

Meena Mahajan and
R. Rama and
S Vijayakumar
Proceedings of the Tenth International Computing and
Combinatorics Conference (COCOON) 2004 ,
1720 August (Jeju Island, Korea),
SpringerVerlag
Lecture Notes in Computer Science series
Volume 3106
pp. 3342.
Copyright held by SpringerVerlag.

Meena Mahajan and
R. Rama and
Venkatesh Raman and
S Vijayakumar.
International Journal of Foundations of Computer Science
Volume 17(2) (April 2006), pp. 337355.
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 ,
1517 December (Mumbai, India),
SpringerVerlag
Lecture Notes in Computer Science series
Volume 2914
pp. 314325.

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

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

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

Eric Allender and Meena Mahajan.
Information and Computation
Vol. 189 (1) (2004), pp. 117134.
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,
1719 February (Lille, France), in the SpringerVerlag
Lecture Notes in Computer Science series
Volume 1770, pp. 8798.

Eric Allender,
V. Arvind and
Meena Mahajan.
Theory of Computing Systems.
Vol. 36 (4) (2003), pp. 303328.
See also
a Corrigendum, April 2011, appearing in ToCS 2013
here .

Meena Mahajan,
P. R. Subramanya and
V Vinay.
Discrete Applied Mathematics.
143(13), 116, 2004.
A preliminary version appears in the Proceedings
of the Fifth Annual International Computing and Combinatorics
Conference COCOON 1999, in the SpringerVerlag
Lecture Notes in Computer Science series
Volume 1627, pp. 134143.

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

Meena Mahajan and
Venkatesh Raman .
Journal of Algorithms,
31(2), 335354, 1999.

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 ACMSIAM Symposium
on Discrete Algorithms,
(New Orleans, Louisiana, USA),
SODA 1997 pp. 730738,
copyright held by ACM.
 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. 5783.

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

Eric Allender,
J. Jiao,
Meena Mahajan and
Vinay.
Theoretical Computer Science ,
Vol. 209 (1,2) (1998),
pp. 4786.
This subsumes a paper titled
Noncommutative 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
SpringerVerlag Lecture Notes in Computer Science
series
Vol 880, pp. 4859.

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

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

Nondeterministic, probabilistic
and alternating computations on cellular array models.
Kamala Krithivasan and Meena Mahajan.
Theoretical Computer Science,
Vol.143 (1995), pp.2349.
A preliminary version was
presented at the Developments in Language Theory
Conference, Turku, Finland, 1215 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
timebounded relativised cellular automata.
Meena Mahajan and Kamala Krithivasan
R.A.I.R.O. Theoretical Informatics and Applications
Vol .27 (5) (1993), pp. 403432.

Some results on timevarying
and relativised cellular automata.
Meena Mahajan and Kamala Krithivasan
International Journal of Computer Mathematics
Vol. 43 (1,2) (1992), pp. 2138.

``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, SpringerVerlag, 1992,
pp. 419436.

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 SpringerVerlag Lecture Notes in
Computer Science series
Vol 560, pp. 172185.

Fuzzy L systems.
M. V. Nagendra Prasad and
Meena Mahajan
and Kamala Krithivasan
International Journal of Computer
Mathematics Vol. 36 (3,4) (1990), pp. 139162.

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

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

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 .