Meena Mahajan

191 papers A* 4A 15B 12C 2Misc 10Journal 126Unranked 18
YearRankTypeTitle / Venue / Authors
2026 A ed.
43rd International Symposium on Theoretical Aspects of Computer Science, STACS 2026, Grenoble, France, March 9-13, 2026
STACS
Meena Mahajan, Florin Manea, Annabelle McIver, Kim Thang Nguyen
2025 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 25111).
Dagstuhl Reports
Swastik Kopparty, Meena Mahajan, Rahul Santhanam, Till Tantau, Ian Mertz
2025 J jnl
On the Interplay of Cube Learning and Dependency Schemes in QCDCL Proof Systems.
CoRR
Abhimanyu Choudhury, Meena Mahajan
2025 — conf
On the Interplay of Cube Learning and Dependency Schemes in {QCDCL} Proof Systems.
FSTTCS
Abhimanyu Choudhury, Meena Mahajan
2025 J jnl
Pseudo-Deterministic Query Complexity of Search Problems.
Comput. Complex.
Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan
2025 J jnl
Runtime vs. Extracted Proof Size: An Exponential Gap for CDCL on QBFs.
J. Autom. Reason.
Olaf Beyersdorff, Benjamin Böhm, Meena Mahajan
2025 A conf
Semi-Algebraic Proof Systems for QBF.
SAT
Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, Luc Nicolas Spachmann
2025 J jnl
Semi-Algebraic Proof Systems for QBF.
CoRR
Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, Luc Nicolas Spachmann
2024 J jnl
Dependency Schemes in CDCL-Based QBF Solving: A Proof-Theoretic Study.
J. Autom. Reason.
Abhimanyu Choudhury, Meena Mahajan
2024 J jnl
Hard QBFs for Merge Resolution.
ACM Trans. Comput. Theory
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood
2024 J jnl
Linear threshold functions in decision lists, decision trees, and depth-2 circuits.
Inf. Process. Lett.
Yogesh Dahiya, K. Vignesh, Meena Mahajan, Karteek Sreenivasaiah
2024 A conf
New Lower Bounds for Polynomial Calculus over Non-Boolean Bases.
SAT
Yogesh Dahiya, Meena Mahajan, Sasank Mouli
2024 J jnl
QBF Merge Resolution is powerful but unnatural.
Log. Methods Comput. Sci.
Meena Mahajan, Gaurav Sood
2024 A* conf
Runtime vs. Extracted Proof Size: An Exponential Gap for CDCL on QBFs.
AAAI
Olaf Beyersdorff, Benjamin Böhm, Meena Mahajan
2024 J jnl
SAT and Interactions (Dagstuhl Seminar 24421).
Dagstuhl Reports
Olaf Beyersdorff, Laura Kovács, Meena Mahajan, Martina Seidl, Kaspar Kasche
2023 A ed.
26th International Conference on Theory and Applications of Satisfiability Testing, SAT 2023, Alghero, Italy, July 4-8, 2023
SAT
Meena Mahajan, Friedrich Slivovsky
2023 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111).
Dagstuhl Reports
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, Manaswi Paraashar
2023 — conf
Dependency Schemes in CDCL-Based QBF Solving: A Proof-Theoretic Study.
FSTTCS
Abhimanyu Choudhury, Meena Mahajan
2023 J jnl
Dependency schemes in CDCL-based QBF solving: a proof-theoretic study.
Electron. Colloquium Comput. Complex.
Abhimanyu Choudhury, Meena Mahajan
2023 J jnl
Hardness Characterisations and Size-width Lower Bounds for QBF Resolution.
ACM Trans. Comput. Log.
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl
2023 J jnl
Linear threshold functions in decision lists, decision trees, and depth-2 circuits.
Electron. Colloquium Comput. Complex.
Yogesh Dahiya, K. Vignesh, Meena Mahajan, Karteek Sreenivasaiah
2023 J jnl
MaxSAT Resolution and Subcube Sums.
ACM Trans. Comput. Log.
Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals
2023 J jnl
New lower bounds for Polynomial Calculus over non-Boolean bases.
Electron. Colloquium Comput. Complex.
Yogesh Dahiya, Meena Mahajan, Sasank Mouli
2023 J jnl
On (simple) decision tree rank.
Theor. Comput. Sci.
Yogesh Dahiya, Meena Mahajan
2023 B conf
Query Complexity of Search Problems.
MFCS
Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan
2023 J jnl
Query Complexity of Search Problems.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan
2022 J jnl
On (Simple) Decision Tree Rank.
CoRR
Yogesh Dahiya, Meena Mahajan
2022 J jnl
On (Simple) Decision Tree Rank.
Electron. Colloquium Comput. Complex.
Yogesh Dahiya, Meena Mahajan
2022 A conf
QBF Merge Resolution Is Powerful but Unnatural.
SAT
Meena Mahajan, Gaurav Sood
2022 J jnl
QBF Merge Resolution is powerful but unnatural.
CoRR
Meena Mahajan, Gaurav Sood
2022 J jnl
QBF Merge Resolution is powerful but unnatural.
Electron. Colloquium Comput. Complex.
Meena Mahajan, Gaurav Sood
2021 J jnl
Building Strategies into QBF Proofs.
J. Autom. Reason.
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
2021 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121).
Dagstuhl Reports
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau
2021 — conf
On (Simple) Decision Tree Rank.
FSTTCS
Yogesh Dahiya, Meena Mahajan
2021 J jnl
The Presburger Award for Young Scientists 2022 - Call for Nominations.
Bull. EATCS
Meena Mahajan
2020 A conf
Algebraic Branching Programs, Border Complexity, and Tangent Spaces.
CCC
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
2020 J jnl
Algebraic Branching Programs, Border Complexity, and Tangent Spaces.
CoRR
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
2020 J jnl
Algebraic Branching Programs, Border Complexity, and Tangent Spaces.
Electron. Colloquium Comput. Complex.
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
2020 — conf
Hard QBFs for Merge Resolution.
FSTTCS
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood
2020 J jnl
Hard QBFs for Merge Resolution.
CoRR
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood
2020 J jnl
Hard QBFs for Merge Resolution.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood
2020 A* conf
Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution.
LICS
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
2020 J jnl
Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
2020 J jnl
Lower bounds for linear decision lists.
Chic. J. Theor. Comput. Sci.
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
2020 A conf
MaxSAT Resolution and Subcube Sums.
SAT
Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals
2020 J jnl
MaxSAT Resolution and Subcube Sums.
CoRR
Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals
2020 J jnl
MaxSAT Resolution and Subcube Sums.
Electron. Colloquium Comput. Complex.
Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals
2020 J jnl
SAT and Interactions (Dagstuhl Seminar 20061).
Dagstuhl Reports
Olaf Beyersdorff, Uwe Egly, Meena Mahajan, Cláudia Nalon
2020 J jnl
The Presburger Award for Young Scientists 2021 - Call for Nominations.
Bull. EATCS
Thore Husfeldt, Meena Mahajan, Mikolaj Bojanczyk
2019 A conf
Building Strategies into QBF Proofs.
STACS
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
2019 J jnl
Lower Bounds for Linear Decision Lists.
CoRR
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
2019 J jnl
Lower Bounds for Linear Decision Lists.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
2019 J jnl
Research in theoretical computer science.
Commun. ACM
Meena Mahajan, Madhavan Mukund, Nitin Saxena
2019 A conf
Short Proofs in QBF Expansion.
SAT
Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan
2019 J jnl
The Presburger Award for Young Scientists 2020 - Call for Nominations.
Bull. EATCS
Thore Husfeldt, Meena Mahajan, Anca Muscholl
2018 J jnl
Are Short Proofs Narrow? QBF Resolution Is
ACM Trans. Comput. Log.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2018 J jnl
Building Strategies into QBF Proofs.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
2018 J jnl
Computing the maximum using (min, +) formulas.
Electron. Colloquium Comput. Complex.
Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari
2018 A conf
Lower Bound Techniques for QBF Proof Systems.
STACS
Meena Mahajan
2018 J jnl
Short Proofs in QBF Expansion.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan
2018 J jnl
Shortest path length with bounded-alternation (min, +) formulas.
Electron. Colloquium Comput. Complex.
Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari
2018 J jnl
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.
Theory Comput. Syst.
Meena Mahajan, Nitin Saurabh
2018 J jnl
Sums of read-once formulas: How many summands are necessary?
Theor. Comput. Sci.
Meena Mahajan, Anuj Tawari
2018 J jnl
Understanding cutting planes for QBFs.
Inf. Comput.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2017 J jnl
A Quest for Structure in Complexity.
Bull. EATCS
Vikraman Arvind, Meena Mahajan
2017 B conf
Arithmetic Circuits: An Overview (Invited Talk).
CSL
Meena Mahajan
2017 B conf
Computing the Maximum using (min, +) Formulas.
MFCS
Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari
2017 J jnl
Feasible Interpolation for QBF Resolution Calculi.
Log. Methods Comput. Sci.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2017 J jnl
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials.
Theory Comput.
Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
2017 J jnl
Understanding Cutting Planes for QBFs.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2016 A conf
Are Short Proofs Narrow? QBF Resolution is not Simple.
STACS
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2016 J jnl
Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation.
Algorithmica
Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
2016 J jnl
Feasible Interpolation for QBF Resolution Calculi.
CoRR
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2016 J jnl
Homomorphism Polynomials Complete for VP.
Chic. J. Theor. Comput. Sci.
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh
2016 J jnl
Level-ordered Q-resolution and tree-like Q-resolution are incomparable.
Inf. Process. Lett.
Meena Mahajan, Anil Shukla
2016 J jnl
Relating two width measures for resolution proofs.
Electron. Colloquium Comput. Complex.
Andreas Krebs, Meena Mahajan, Anil Shukla
2016 J jnl
Small Depth Proof Systems.
ACM Trans. Comput. Theory
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2016 Misc conf
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.
CSR
Meena Mahajan, Nitin Saurabh
2016 J jnl
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.
CoRR
Meena Mahajan, Nitin Saurabh
2016 J jnl
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.
Electron. Colloquium Comput. Complex.
Meena Mahajan, Nitin Saurabh
2016 J jnl
Space-Efficient Approximations for Subset Sum.
ACM Trans. Comput. Theory
Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2016 Misc conf
Sums of Read-Once Formulas: How Many Summands Suffice?
CSR
Meena Mahajan, Anuj Tawari
2016 J jnl
Sums of read-once formulas: How many summands suffice?
CoRR
Meena Mahajan, Anuj Tawari
2016 — conf
Understanding Cutting Planes for QBFs.
FSTTCS
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2016 J jnl
VNP=VP in the multilinear world.
Inf. Process. Lett.
Meena Mahajan, Nitin Saurabh, Sébastien Tavenas
2015 J jnl
Are Short Proofs Narrow? QBF Resolution is not Simple.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2015 J jnl
Building above read-once polynomials: identity testing and hardness of representation.
Electron. Colloquium Comput. Complex.
Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
2015 J jnl
Circuits, Logic and Games (Dagstuhl Seminar 15401).
Dagstuhl Reports
Mikolaj Bojanczyk, Meena Mahajan, Thomas Schwentick, Heribert Vollmer
2015 — conf
Feasible Interpolation for QBF Resolution Calculi.
ICALP (1)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2015 J jnl
Feasible Interpolation for QBF Resolution Calculi.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
2015 J jnl
Read-once polynomials: How many summands suffice?
CoRR
Meena Mahajan, Anuj Tawari
2015 J jnl
Sums of read-once formulas: How many summands suffice?
Electron. Colloquium Comput. Complex.
Meena Mahajan, Anuj Tawari
2015 — conf
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials.
MFCS (2)
Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
2015 J jnl
The shifted partial derivative complexity of Elementary Symmetric Polynomials.
Electron. Colloquium Comput. Complex.
Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
2014 Misc conf
Building above Read-once Polynomials: Identity Testing and Hardness of Representation.
COCOON
Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
2014 — conf
Homomorphism Polynomials Complete for VP.
FSTTCS
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh
2014 J jnl
Homomorphism polynomials complete for VP.
Electron. Colloquium Comput. Complex.
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh
2014 J jnl
Monomials, multilinearity and identity testing in simple read-restricted circuits.
Theor. Comput. Sci.
Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
2014 J jnl
Space-Efficient Approximations for Subset Sum.
Electron. Colloquium Comput. Complex.
Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2013 J jnl
Algebraic Complexity Classes.
CoRR
Meena Mahajan
2013 J jnl
Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series.
Theory Comput. Syst.
Eric Allender, Vikraman Arvind, Meena Mahajan
2013 J jnl
Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits.
Comput. Complex.
Maurice J. Jansen, Meena Mahajan, B. V. Raghavendra Rao
2013 B conf
Small Depth Proof Systems.
MFCS
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2013 J jnl
Small Depth Proof Systems.
CoRR
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2013 J jnl
Small Depth Proof Systems.
Electron. Colloquium Comput. Complex.
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2013 J jnl
Small Space Analogues of Valiant's Classes and the Limitations of Skew Formulas.
Comput. Complex.
Meena Mahajan, B. V. Raghavendra Rao
2013 J jnl
Verifying proofs in constant depth.
ACM Trans. Comput. Theory
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
2012 J jnl
Counting Paths in VPA Is Complete for #NC 1.
Algorithmica
Andreas Krebs, Nutan Limaye, Meena Mahajan
2012 J jnl
Counting classes and the fine structure between NC
Theor. Comput. Sci.
Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer
2012 — conf
Counting paths in planar width 2 branching programs.
CATS
Meena Mahajan, Nitin Saurabh, Karteek Sreenivasaiah
2012 B conf
Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs.
MFCS
Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
2012 Misc conf
The Complexity of Unary Subset Sum.
COCOON
Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2012 J jnl
The planar k-means problem is NP-hard.
Theor. Comput. Sci.
Meena Mahajan, Prajakta Nimbhorkar, Kasturi R. Varadarajan
2012 J jnl
Verifying Proofs in Constant Depth.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
2011 B conf
Verifying Proofs in Constant Depth.
MFCS
Olaf Beyersdorff, Samir Datta, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
2010 J jnl
Arithmetizing Classes Around NC\textsf{NC}
Theory Comput. Syst.
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao
2010 B conf
Counting Classes and the Fine Structure between NC
MFCS
Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer
2010 J jnl
Counting Classes and the Fine Structure between NC
Electron. Colloquium Comput. Complex.
Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer
2010 Misc conf
Counting Paths in VPA Is Complete for #NC
COCOON
Andreas Krebs, Nutan Limaye, Meena Mahajan
2010 J jnl
Counting paths in VPA is complete for #NC
Electron. Colloquium Comput. Complex.
Andreas Krebs, Nutan Limaye, Meena Mahajan
2010 — conf
Frontmatter, Table of Contents, Preface, Conference Organization, Author Index.
FSTTCS
Kamal Lodaya, Meena Mahajan
2010 — ed.
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, Chennai, India, December 15-18, 2010
FSTTCS
Kamal Lodaya, Meena Mahajan
2010 J jnl
Longest Paths in Planar DAGs in Unambiguous Log-Space.
Chic. J. Theor. Comput. Sci.
Nutan Limaye, Meena Mahajan, Prajakta Nimbhorkar
2010 J jnl
On the Complexity of Matrix Rank and Rigidity.
Theory Comput. Syst.
Meena Mahajan, Jayalal Sarma
2010 J jnl
Planarity, Determinants, Permanents, and (Unique) Matchings.
ACM Trans. Comput. Theory
Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan
2009 — conf
Longest Paths in Planar DAGs in Unambiguous Logspace.
CATS
Nutan Limaye, Meena Mahajan, Prajakta Nimbhorkar
2009 C conf
Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata.
LATA
Nutan Limaye, Meena Mahajan
2009 J jnl
On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata.
J. Autom. Lang. Comb.
Nutan Limaye, Meena Mahajan, Antoine Meyer
2009 J jnl
Parameterizing above or below guaranteed values.
J. Comput. Syst. Sci.
Meena Mahajan, Venkatesh Raman, Somnath Sikdar
2009 — conf
Small space analogues of Valiant's classes and the limitations of skew formula.
Algebraic Methods in Computational Complexity
Meena Mahajan, B. V. Raghavendra Rao
2009 B conf
Small-Space Analogues of Valiant's Classes.
FCT
Meena Mahajan, B. V. Raghavendra Rao
2009 B conf
The Planar k-Means Problem is NP-Hard.
WALCOM
Meena Mahajan, Prajakta Nimbhorkar, Kasturi R. Varadarajan
2009 J jnl
Upper Bounds for Monotone Planar Circuit Value and Variants.
Comput. Complex.
Nutan Limaye, Meena Mahajan, Jayalal Sarma
2008 B conf
Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae.
MFCS
Meena Mahajan, B. V. Raghavendra Rao
2008 J jnl
Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae.
Electron. Colloquium Comput. Complex.
Meena Mahajan, B. V. Raghavendra Rao
2008 J jnl
Longest paths in Planar DAGs in Unambiguous Logspace
CoRR
Nutan Limaye, Meena Mahajan, Prajakta Nimbhorkar
2008 Misc conf
On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata.
CSR
Nutan Limaye, Meena Mahajan, Antoine Meyer
2008 J jnl
Rigidity of a simple extended lower triangular matrix.
Inf. Process. Lett.
Meena Mahajan, Jayalal Sarma
2008 J jnl
Simultaneous matchings: Hardness and approximation.
J. Comput. Syst. Sci.
Martin Kutz, Khaled M. Elbassioni, Irit Katriel, Meena Mahajan
2008 J jnl
Some perfect matchings and perfect half-integral matchings in NC.
Chic. J. Theor. Comput. Sci.
Raghav Kulkarni, Meena Mahajan, Kasturi R. Varadarajan
2007 A conf
Arithmetizing Classes Around NC
STACS
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao
2007 J jnl
Arithmetizing classes around NC^1 and L.
Electron. Colloquium Comput. Complex.
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao
2007 J jnl
Block Sorting: A Characterization and some Heuristics.
Nord. J. Comput.
Meena Mahajan, Raghavan Rama, Vijayakumar Sundarrajan
2007 Misc conf
On the Complexity of Matrix Rank and Rigidity.
CSR
Meena Mahajan, Jayalal Sarma
2007 Misc conf
Planarity, Determinants, Permanents, and (Unique) Matchings.
CSR
Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan
2007 J jnl
Polynomial Size Log Depth Circuits: Between NC
Bull. EATCS
Meena Mahajan
2006 J jnl
Approximate Block Sorting.
Int. J. Found. Comput. Sci.
Meena Mahajan, Raghavan Rama, Venkatesh Raman, S. Vijaykumar
2006 J jnl
Evaluating Monotone Circuits on Cylinders, Planes and Tori
Electron. Colloquium Comput. Complex.
Nutan Limaye, Meena Mahajan, Jayalal Sarma
2006 A conf
Evaluating Monotone Circuits on Cylinders, Planes and Tori.
STACS
Nutan Limaye, Meena Mahajan, Jayalal Sarma
2006 J jnl
On sorting by 3-bounded transpositions.
Discret. Math.
Meena Mahajan, Raghavan Rama, Vijayakumar Sundarrajan
2006 — conf
On the Bipartite Unique Perfect Matching Problem.
ICALP (1)
Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf
2006 J jnl
On the Complexity of Rank and Rigidity.
Electron. Colloquium Comput. Complex.
Meena Mahajan, Jayalal Sarma
2006 — conf
Parameterizing MAX SNP Problems Above Guaranteed Values.
IWPEC
Meena Mahajan, Venkatesh Raman, Somnath Sikdar
2005 B conf
Simultaneous Matchings.
ISAAC
Khaled M. Elbassioni, Irit Katriel, Martin Kutz, Meena Mahajan
2004 — ed.
FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 24th International Conference, Chennai, India, December 16-18, 2004, Proceedings
FSTTCS
Kamal Lodaya, Meena Mahajan
2004 A conf
Seeking a Vertex of the Planar Matching Polytope in NC.
ESA
Raghav Kulkarni, Meena Mahajan
2004 J jnl
The combinatorial approach yields an
Discret. Appl. Math.
Meena Mahajan, P. R. Subramanya, V. Vinay
2004 J jnl
The complexity of planarity testing.
Inf. Comput.
Eric Allender, Meena Mahajan
2004 Misc conf
Towards Constructing Optimal Strip Move Sequences.
COCOON
Meena Mahajan, Raghavan Rama, Vijayakumar Sundarrajan
2003 J jnl
Arithmetic Complexity, Kleene Closure, and Formal Power Series.
Theory Comput. Syst.
Eric Allender, Vikraman Arvind, Meena Mahajan
2003 — conf
Merging and Sorting By Strip Moves.
FSTTCS
Meena Mahajan, Raghavan Rama, Venkatesh Raman, Vijayakumar Sundarrajan
2003 J jnl
On Sorting by 3-Bounded Transpositions.
Electron. Notes Discret. Math.
Meena Mahajan, Raghavan Rama, Vijayakumar Sundarrajan
2000 A* conf
A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract).
STOC
Meena Mahajan, Kasturi R. Varadarajan
2000 J jnl
A note on the hardness of the characteristic polynomial
Electron. Colloquium Comput. Complex.
Meena Mahajan, V. Vinay
2000 A conf
The Complexity of Planarity Testing.
STACS
Eric Allender, Meena Mahajan
1999 J jnl
A Combinatorial Algorithm for Pfaffians
Electron. Colloquium Comput. Complex.
Meena Mahajan, P. R. Subramanya, V. Vinay
1999 Misc conf
A Combinatorial Algorithm for Pfaffians.
COCOON
Meena Mahajan, P. R. Subramanya, V. Vinay
1999 J jnl
Arithmetic Complexity, Kleene Closure, and Formal Power Series
Electron. Colloquium Comput. Complex.
Eric Allender, Vikraman Arvind, Meena Mahajan
1999 J jnl
Determinant: Old Algorithms, New Insights.
SIAM J. Discret. Math.
Meena Mahajan, V. Vinay
1999 J jnl
Parameterizing above Guaranteed Values: MaxSat and MaxCut.
J. Algorithms
Meena Mahajan, Venkatesh Raman
1998 J jnl
Determinant: Old Algorithms, New Insights
Electron. Colloquium Comput. Complex.
Meena Mahajan, V. Vinay
1998 — conf
Determinant: Old Algorithms, New Insights (Extended Abstract).
SWAT
Meena Mahajan, V. Vinay
1998 J jnl
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds.
Theor. Comput. Sci.
Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay
1997 A* conf
A Combinatorial Algorithm for the Determinant.
SODA
Meena Mahajan, V. Vinay
1997 J jnl
Determinant: Combinatorics, Algorithms, and Complexity
Electron. Colloquium Comput. Complex.
Meena Mahajan, V. Vinay
1997 J jnl
Determinant: Combinatorics, Algorithms, and Complexity.
Chic. J. Theor. Comput. Sci.
Meena Mahajan, V. Vinay
1997 J jnl
Parametrizing Above Guaranteed Values: MaxSat and MaxCut
Electron. Colloquium Comput. Complex.
Meena Mahajan, Venkatesh Raman
1995 J jnl
A Note on Mod and Generalised Mod Classes.
Inf. Process. Lett.
Meena Mahajan, N. V. Vinodchandran
1995 B conf
Logspace Verifiers, NC, and NP.
ISAAC
Satyanarayana V. Lokam, Meena Mahajan, V. Vinay
1995 J jnl
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds
Electron. Colloquium Comput. Complex.
Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay
1995 J jnl
Nondeterministic, Probabilistic and Alternating Computations on Cellular Array Models.
Theor. Comput. Sci.
Kamala Krithivasan, Meena Mahajan
1994 J jnl
A Note on SpanP Functions.
Inf. Process. Lett.
Meena Mahajan, Thomas Thierauf, N. V. Vinodchandran
1994 — conf
Non-commutative Computation, Depth Reduction, and Skew Circuits (Extended Abstract).
FSTTCS
Meena Mahajan, V. Vinay
1993 J jnl
Language Classes Defined by Time-Bounded Relativised Cellular Automata.
RAIRO Theor. Informatics Appl.
Meena Mahajan, Kamala Krithivasan
1993 C conf
Nondeterministic, Probabilistic and Alternating Computations on Cellular Array Models.
Developments in Language Theory
Kamala Krithivasan, Meena Mahajan
1992 J jnl
Some results on time-varying and relativised cellular automata.
Int. J. Comput. Math.
Meena Mahajan, Kamala Krithivasan
1991 — conf
Relativised Cellular Automata and Complexity Classes.
FSTTCS
Meena Mahajan, Kamala Krithivasan
1990 J jnl
Fuzzy L-systems.
Int. J. Comput. Math.
M. V. Nagendra Prasad, Meena Mahajan, Kamala Krithivasan
1989 — ch.
Hexagonal Cellular Automata.
A Perspective in Theoretical Computer Science
Meena Mahajan, Kamala Krithivasan
1989 J jnl
Systolic Pyramid Automata, Cellular Automata and Array Languages.
Int. J. Pattern Recognit. Artif. Intell.
Kamala Krithivasan, Meena Mahajan
1989 — ch.
Systolic Pyramid Automata, Cellular Automata and Array Languages.
Array Grammars, Patterns and Recognizers
Kamala Krithivasan, Meena Mahajan