| 2026 | SAT | Proof Systems for QBF Synthesis: Extracting Skolem and Herbrand Functions. | S. Akshay, Olaf Beyersdorff, Supratik Chakraborty, Lea Kasche, Meena Mahajan, Luc Nicolas Spachmann |
| 2026 | SAT | Long-Distance Q(D^std)-Consensus Is Sound. | Abhimanyu Choudhury, Meena Mahajan, Friedrich Slivovsky |
| 2025 | SAT | Semi-Algebraic Proof Systems for QBF. | Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, Luc Nicolas Spachmann |
| 2024 | AAAI | Runtime vs. Extracted Proof Size: An Exponential Gap for CDCL on QBFs. | Olaf Beyersdorff, Benjamin Bhm, Meena Mahajan |
| 2024 | SAT | New Lower Bounds for Polynomial Calculus over Non-Boolean Bases. | Yogesh Dahiya, Meena Mahajan, Sasank Mouli |
| 2023 | MFCS | Query Complexity of Search Problems. | Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan |
| 2022 | SAT | QBF Merge Resolution Is Powerful but Unnatural. | Meena Mahajan, Gaurav Sood |
| 2020 | LICS | Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution. | Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan |
| 2020 | SAT | MaxSAT Resolution and Subcube Sums. | Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals |
| 2019 | STACS | Building Strategies into QBF Proofs. | Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan |
| 2019 | SAT | Short Proofs in QBF Expansion. | Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan |
| 2018 | STACS | Lower Bound Techniques for QBF Proof Systems. | Meena Mahajan |
| 2017 | CSL | Arithmetic Circuits: An Overview (Invited Talk). | Meena Mahajan |
| 2017 | MFCS | Computing the Maximum using (min, +) Formulas. | Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari |
| 2016 | CSR | Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. | Meena Mahajan, Nitin Saurabh |
| 2016 | CSR | Sums of Read-Once Formulas: How Many Summands Suffice? | Meena Mahajan, Anuj Tawari |
| 2016 | STACS | Are Short Proofs Narrow? QBF Resolution is not Simple. | Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla |
| 2015 | ICALP | Feasible Interpolation for QBF Resolution Calculi. | Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla |
| 2015 | MFCS | The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials. | Herv Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan |
| 2014 | COCOON | Building above Read-once Polynomials: Identity Testing and Hardness of Representation. | Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah |
| 2013 | MFCS | Small Depth Proof Systems. | Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah |
| 2012 | COCOON | The Complexity of Unary Subset Sum. | Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah |
| 2012 | MFCS | Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs. | Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah |
| 2011 | MFCS | Verifying Proofs in Constant Depth. | Olaf Beyersdorff, Samir Datta, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer |
| 2010 | COCOON | Counting Paths in VPA Is Complete for #NC | Andreas Krebs, Nutan Limaye, Meena Mahajan |
| 2010 | MFCS | Counting Classes and the Fine Structure between NC | Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer |
| 2009 | FCT | Small-Space Analogues of Valiant's Classes. | Meena Mahajan, B. V. Raghavendra Rao |
| 2009 | LATA | Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata. | Nutan Limaye, Meena Mahajan |
| 2009 | WALCOM | The Planar k-Means Problem is NP-Hard. | Meena Mahajan, Prajakta Nimbhorkar, Kasturi R. Varadarajan |
| 2008 | CSR | On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata. | Nutan Limaye, Meena Mahajan, Antoine Meyer |
| 2008 | MFCS | Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae. | Meena Mahajan, B. V. Raghavendra Rao |
| 2007 | CSR | Planarity, Determinants, Permanents, and (Unique) Matchings. | Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan |
| 2007 | CSR | On the Complexity of Matrix Rank and Rigidity. | Meena Mahajan, Jayalal Sarma |
| 2007 | STACS | Arithmetizing Classes Around NC | Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao |
| 2006 | ICALP | On the Bipartite Unique Perfect Matching Problem. | Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf |
| 2006 | STACS | Evaluating Monotone Circuits on Cylinders, Planes and Tori. | Nutan Limaye, Meena Mahajan, Jayalal Sarma |
| 2005 | ISAAC | Simultaneous Matchings. | Khaled M. Elbassioni, Irit Katriel, Martin Kutz, Meena Mahajan |
| 2004 | COCOON | Towards Constructing Optimal Strip Move Sequences. | Meena Mahajan, Raghavan Rama, Vijayakumar Sundarrajan |
| 2004 | ESA | Seeking a Vertex of the Planar Matching Polytope in NC. | Raghav Kulkarni, Meena Mahajan |
| 2000 | STOC | A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract). | Meena Mahajan, Kasturi R. Varadarajan |
| 2000 | STACS | The Complexity of Planarity Testing. | Eric Allender, Meena Mahajan |
| 1999 | COCOON | A Combinatorial Algorithm for Pfaffians. | Meena Mahajan, P. R. Subramanya, V. Vinay |
| 1997 | SODA | A Combinatorial Algorithm for the Determinant. | Meena Mahajan, V. Vinay |
| 1995 | ISAAC | Logspace Verifiers, NC, and NP. | Satyanarayana V. Lokam, Meena Mahajan, V. Vinay |
| 1993 | DLT | Nondeterministic, Probabilistic and Alternating Computations on Cellular Array Models. | Kamala Krithivasan, Meena Mahajan |