Source: https://www.imsc.res.in/~meena/publ.html
Timestamp: 2019-04-20 02:48:26+00:00

Document:
Depth-2 Threshold Circuits: Provable Limitations.
Vol. 24 Issue 3, pp. 371-380, March 2019.
Lower Bounds for Linear Decision Lists.
Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, and Nitin Saurabh.
Building strategies into QBF proofs.
Olaf Beyersdorff, Joshua Blinkhorn, and Meena Mahajan.
Proceedings of 36th Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs series Vol 126, pages 14:1--14:18, 2019.
Short Proofs in QBF Expansion.
Olaf Beyersdorff, Leroy Chew, Judith Clymo, and Meena Mahajan.
Meena Mahajan, Prajakta Nimbhorkar, and Anuj Tawari.
to appear in International Journal of Advances in Engineering Sciences and Applied Mathematics, special issue on Theory of Computation - Festschrift for Kamala Krithivasan.
Lower Bound Techniques for QBF Proof Systems.
in Proceedings of 35th STACS 2018, Caen, France. pp 2:1--2:8, LIPIcs vol 96, 2018. Invited plenary talk.
A Quest for Structure in Complexity.
V. Arvind and Meena Mahajan.
in The Computational Complexity Column, Bulletin of the EATCS, Number 123, Oct 2017.
Full version in ECCC TR18-020.
Relating two width measures for resolution proofs.
Andreas Krebs, Meena Mahajan, and Anil Shukla.
Understanding Cutting Planes for QBFs.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla.
In Information and Computation, 262:141--161, 2018.
preliminary version in Proceedings of the 36th Annual International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 13--15 December 2016, (Chennai, India), LIPIcs.
Full version in ECCC TR 17-037 .
Meena Mahajan and Nitin Saurabh.
In Theory of Computing Systems (TOCS) 62(3):622-652, 2018, (special issue for CSR 2016).
A preliminary version appeared in Proceedings of 11th Computer Science Symposium in Russia CSR 2016, Springer-Verlag LNCS Vol 9691, pp 251-265.
Winner of Best Paper Award at CSR 2016.
Extended version in ECCC TR 16-038 .
Sums of read-once formulas: How many summands are necessary?
Meena Mahajan and Anuj Tawari.
In Theoretical Computer Science, Vol. 708, pp 34--45, 2018.
Preliminary version in Proceedings of 11th Computer Science Symposium in Russia CSR 2016, Springer-Verlag LNCS Vol 9691, pp 266-279.
Full version in ECCC TR 15-204 .
Meena Mahajan and Anil Shukla.
Information Processing Letters. 116(3), 256-258, 2016.
Are Short Proofs Narrow? QBF Resolution is not so Simple.
ACM Transactions on Computational Logic, Vol 19(1), 1:1--1:26, 2018.
Preliminary version in Proceedings of 33rd Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs series Vol 47, pages 15:1--15:14, 2016.
VNP = VP in the multilinear world.
Meena Mahajan and Nitin Saurabh and Sebastien Tavenas.
Information Processing Letters 116(2), 179--182, 2016.
Herve Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan.
Theory of Computing, Vol 13 Article 9 pp 1-34, 2017.
preliminary version in Proceedings of MFCS 2015. Springer-Verlag Lecture Notes in Computer Science Vol 9235, pp 324-335.
Full version: ECCC TR 15-118 .
Logical Methods in Computer Science, June 8, 2017, Volume 13, Issue 2.
preliminary version in Proceedings of 42nd ICALP 2015 (Kyoto, Japan). Springer-Verlag Lecture Notes in Computer Science Vol 9134, pp 180-192.
Full version: ECCC TR 15-059 .
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.
Homomorphism polynomials complete for VP.
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre and Nitin Saurabh.
Proceedings of the 34th Annual International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 15--17 December 2014, (Delhi, India), LIPIcs.
Also at ECCC TR 14-163 .
Building above read-once polynomials: identity testing and hardness of representation.
Meena Mahajan, B. V. Raghavendra Rao and Karteek Sreenivasaiah.
Algorithmica (special issue for COCOON 2014). Vol. 76 (4), 890-909, Dec 2016 .
Also at: ECCC TR 15-202 .
A preliminary version appeared in Proceedings of 20th Annual International Computing and Combinatorics Conference COCOON, 4-6 Aug 2014, Atlanta, USA..
Springer-Verlag Lecture Notes in Computer Science Volume 8591, pp.1--12.
Theoretical Computer Science 524, 90--102, 2014.
appeared in Proceedings of Proc. 37th International Symposium on Mathematical Foundations of Computer Science MFCS 27-31 Aug 2012, Bratislava, Slovakia. Springer-Verlag Lecture Notes in Computer Science Volume 7464, pp.655--667.
Andreas Krebs, Nutan Limaye, Meena Mahajan, and Karteek Sreenivasaiah.
ACM Transactions on Computation Theory, Vol. 9, Issue 1, 2:1-26, Dec 2016.
Preliminary version in Proceedings of 38th International Symposium on Mathematical Foundations of Computer Science MFCS, Aug 2013, Klosterneuburg, Austria.
Springer-Verlag Lecture Notes in Computer Science Volume 8087, pp.583--594.
Full version: ECCC TR 13-102 .
The complexity of unary subset sum.
Nutan Limaye and Meena Mahajan and Karteek Sreenivasaiah.
Proceedings of 18th Annual International Computing and Combinatorics Conference COCOON, 20-22 Aug 2012, Sydney, Australia..
Springer-Verlag Lecture Notes in Computer Science Volume 7434, pp.458--469.
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.
Counting paths in planar width 2 branching programs.
Meena Mahajan and Nitin Saurabh and Karteek Sreenivasaiah.
CRPIT series Vol.\ 128, pp.\ 59--68.
Verifying Proofs in Constant Depth.
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, and Heribert Vollmer.
ACM Transactions on Computation Theory,Vol 5 issue 1 May 2013, article 2: 1--23 .
A preliminary version appeared in Proceedings of 36th International Symposium on Mathematical Foundations of Computer Science MFCS, Aug 2011, Warsaw, Poland.
Springer-Verlag Lecture Notes in Computer Science Volume 6907, pp.84--95.
Small-space analogues of Valiant's classes and the limitations of skew formulas.
Meena Mahajan and B. V. Raghavendra Rao.
Computational Complexity, Vol 22 pp 1--38, 2013.
Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits.
Maurice Jansen and Meena Mahajan and B. V. Raghavendra Rao.
Computational Complexity Vol 22(3), pp 517--564, 2013.
Counting classes and the fine structure between NC^1 and L.
Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, and Heribert Vollmer.
Theoretical Computer Science (special issue for MFCS 2010) Vol 417, pp 36--49, 2012.
Proceedings of 35th International Symposium on Mathematical Foundations of Computer Science MFCS, Aug 2010, Czech Republic.
Springer-Verlag Lecture Notes in Computer Science series Volume 6281 pp.306--317.
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.
A preliminary version appeared in Proceedings of 16th International Computing and Combinatorics Conference COCOON, 19-21 July, 2010, Vietnam.
Springer-Verlag Lecture Notes in Computer Science series Volume 6196 pp.44--53.
Small-space analogues of Valiant's classes.
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.
Theoretical Computer Science (special issue for WALCOM 2009) Vol 442, pp. 13--21, 2012.
A preliminary version appeared in 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.
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. 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.
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 .
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.
Journal of Automata, Languages and Combinatorics Volume 14(3,4), pp. 211--235, 2009.
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 .
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.
Planarity, Determinants, Permanents, and (Unique) Perfect Matchings.
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 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.
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.
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.
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.
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.
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.
Block Sorting: A Characterization and some Heuristics.
Nordic Journal of Computing .
Volume 14 (2007), pp. 126--150.
Seeking a vertex of the planar matching polytope in NC.
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.
Towards constructing optimal strip move sequences.
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.
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.
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.
and was 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.
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.
See also a Corrigendum, April 2011, appearing in ToCS 2013 here .
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.
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) July 8--10 1998 (Stockholm, Sweden), LNCS 1432, pp 276--287.
Parametrizing above Guaranteed Values: MaxSat and MaxCut.
Meena Mahajan and Venkatesh Raman .
Journal of Algorithms, 31(2), 335-354, 1999.
Chicago Journal of Theoretical Computer Science, Volume 1997 Article 5.
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.
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.
Journal of Mathematical and Physical Sciences Vol.27 (1993).
Languages classes defined by time-bounded relativised cellular automata.
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.
International Journal of Computer Mathematics Vol. 43 (1,2) (1992), pp. 21--38.
editors G. Rozenberg and A. Salomaa, Springer-Verlag, 1992, pp. 419--436.
Relativised cellular automata and complexity classes.
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.
International Journal of Computer Mathematics Vol. 36 (3,4) (1990), pp. 139--162.
Systolic pyramid automata, cellular automata and array languages.
International Journal of Pattern Recognition and Artificial Intelligence Vol. 3 (3,4) (1989), pp. 405--433.
editor R. Narasimhan, World Scientific (Singapore), 1989, pp. 134--164.
Studies in language classes defined by different types of time-varying cellular automata.
Thesis work done at the Department of Computer Science and Engineering, Indian Institute of Technology, Madras, under the supervision of Kamala Krithivasan .
Eric Allender , V. Arvind , Suman Bandopadhyay, , Olaf Beyersdorff , Joshua Blinkhorn , Arkadev Chattopadhyay , Leroy Chew , Judith Clymo , Samir Datta , Arnaud Durand , Khaled Elbassioni (also see here ), Herve Fournier , Anna Gal, Thanh Minh Hoang , Jing-Tang Jang, Maurice Jansen , J Jiao , Irit Katriel , Andreas Krebs , Kamala Krithivasan , Raghav Kulkarni , Martin Kutz , K Narayan Kumar , Nutan Limaye, Satya Lokam , Guillaume Malod , Nikhil Mande , Antoine Meyer , M.V.Nagendra Prasad , Prajakta Nimbhorkar , R Rama , Venkatesh Raman , B V Raghavendra Rao , Nicolas de Rugy-Altherre , Jayalal Sarma M N , Nitin Saurabh , Gido Scharfenberger-Fabian , Priti Shankar , Anil Shukla , Somnath Sikdar , Karteek Sreenivasaiah , Srikanth Srinivasan , P V Subramanya , Sebastien Tavenas , Thomas Thierauf , Michael Thomas , Kasturi Varadarajan , S Vijayakumar , V Vinay , Vinodchandran N.V. , Heribert Vollmer .

References: V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V.