Meena Mahajan

ORCID

Publication Activity (10 Years)

Years Active: 1989-2024
Publications (10 Years): 73

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

FSTTCS

Dagstuhl Reports

Publications

Olaf Beyersdorff, Benjamin Böhm, Meena Mahajan
Runtime vs. Extracted Proof Size: An Exponential Gap for CDCL on QBFs. AAAI (2024)
Yogesh Dahiya, K. Vignesh, Meena Mahajan, Karteek Sreenivasaiah
Linear threshold functions in decision lists, decision trees, and depth-2 circuits. Inf. Process. Lett. 183 (2024)
Yogesh Dahiya, Meena Mahajan, Sasank Mouli
New Lower Bounds for Polynomial Calculus over Non-Boolean Bases. SAT (2024)
Abhimanyu Choudhury, Meena Mahajan
Dependency Schemes in CDCL-Based QBF Solving: A Proof-Theoretic Study. J. Autom. Reason. 68 (3) (2024)
Yogesh Dahiya, Meena Mahajan
On (simple) decision tree rank. Theor. Comput. Sci. 978 (2023)
Yogesh Dahiya, K. Vignesh, Meena Mahajan, Karteek Sreenivasaiah
Linear threshold functions in decision lists, decision trees, and depth-2 circuits. Electron. Colloquium Comput. Complex. (2023)
Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals
MaxSAT Resolution and Subcube Sums. ACM Trans. Comput. Log. 24 (1) (2023)
Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan
Query Complexity of Search Problems. Electron. Colloquium Comput. Complex. (2023)
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, Manaswi Paraashar
Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111). Dagstuhl Reports 13 (3) (2023)
Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan
Query Complexity of Search Problems. MFCS (2023)
Abhimanyu Choudhury, Meena Mahajan
Dependency Schemes in CDCL-Based QBF Solving: A Proof-Theoretic Study. FSTTCS (2023)
Yogesh Dahiya, Meena Mahajan, Sasank Mouli
New lower bounds for Polynomial Calculus over non-Boolean bases. Electron. Colloquium Comput. Complex. (2023)
Abhimanyu Choudhury, Meena Mahajan
Dependency schemes in CDCL-based QBF solving: a proof-theoretic study. Electron. Colloquium Comput. Complex. (2023)
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl
Hardness Characterisations and Size-width Lower Bounds for QBF Resolution. ACM Trans. Comput. Log. 24 (2) (2023)
Yogesh Dahiya, Meena Mahajan
On (Simple) Decision Tree Rank. Electron. Colloquium Comput. Complex. 29 (2022)
Yogesh Dahiya, Meena Mahajan
On (Simple) Decision Tree Rank. CoRR (2022)
Meena Mahajan, Gaurav Sood
QBF Merge Resolution Is Powerful but Unnatural. SAT (2022)
Meena Mahajan, Gaurav Sood
QBF Merge Resolution is powerful but unnatural. CoRR (2022)
Meena Mahajan, Gaurav Sood
QBF Merge Resolution is powerful but unnatural. Electron. Colloquium Comput. Complex. (2022)
Meena Mahajan
The Presburger Award for Young Scientists 2022 - Call for Nominations. Bull. EATCS 135 (2021)
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
Building Strategies into QBF Proofs. J. Autom. Reason. 65 (1) (2021)
Yogesh Dahiya, Meena Mahajan
On (Simple) Decision Tree Rank. FSTTCS (2021)
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121). Dagstuhl Reports 11 (2) (2021)
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood
Hard QBFs for Merge Resolution. CoRR (2020)
Thore Husfeldt, Meena Mahajan, Mikolaj Bojanczyk
The Presburger Award for Young Scientists 2021 - Call for Nominations. Bull. EATCS 132 (2020)
Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals
MaxSAT Resolution and Subcube Sums. SAT (2020)
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
Lower bounds for linear decision lists. Chic. J. Theor. Comput. Sci. 2020 (2020)
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution. LICS (2020)
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. CoRR (2020)
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution. Electron. Colloquium Comput. Complex. 27 (2020)
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood
Hard QBFs for Merge Resolution. Electron. Colloquium Comput. Complex. 27 (2020)
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. Electron. Colloquium Comput. Complex. 27 (2020)
Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals
MaxSAT Resolution and Subcube Sums. Electron. Colloquium Comput. Complex. 27 (2020)
Olaf Beyersdorff, Uwe Egly, Meena Mahajan, Cláudia Nalon
SAT and Interactions (Dagstuhl Seminar 20061). Dagstuhl Reports 10 (2) (2020)
Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals
MaxSAT Resolution and Subcube Sums. CoRR (2020)
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood
Hard QBFs for Merge Resolution. FSTTCS (2020)
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. Computational Complexity Conference (2020)
Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan
Short Proofs in QBF Expansion. SAT (2019)
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
Building Strategies into QBF Proofs. STACS (2019)
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
Lower Bounds for Linear Decision Lists. CoRR (2019)
Thore Husfeldt, Meena Mahajan, Anca Muscholl
The Presburger Award for Young Scientists 2020 - Call for Nominations. Bull. EATCS 129 (2019)
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
Lower Bounds for Linear Decision Lists. Electron. Colloquium Comput. Complex. 26 (2019)
Meena Mahajan, Madhavan Mukund, Nitin Saxena
Research in theoretical computer science. Commun. ACM 62 (11) (2019)
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
Building Strategies into QBF Proofs. Electron. Colloquium Comput. Complex. 25 (2018)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
Understanding cutting planes for QBFs. Inf. Comput. 262 (2018)
Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan
Short Proofs in QBF Expansion. Electron. Colloquium Comput. Complex. 25 (2018)
Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari
Computing the maximum using (min, +) formulas. Electron. Colloquium Comput. Complex. 25 (2018)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
So Simple. ACM Trans. Comput. Log. 19 (1) (2018)
Meena Mahajan, Nitin Saurabh
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. Theory Comput. Syst. 62 (3) (2018)
Meena Mahajan
Lower Bound Techniques for QBF Proof Systems. STACS (2018)
Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari
Shortest path length with bounded-alternation (min, +) formulas. Electron. Colloquium Comput. Complex. 25 (2018)
Meena Mahajan, Anuj Tawari
Sums of read-once formulas: How many summands are necessary? Theor. Comput. Sci. 708 (2018)
Meena Mahajan
Arithmetic Circuits: An Overview (Invited Talk). CSL (2017)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
Understanding Cutting Planes for QBFs. Electron. Colloquium Comput. Complex. 24 (2017)
Vikraman Arvind, Meena Mahajan
A Quest for Structure in Complexity. Bull. EATCS 123 (2017)
Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials. Theory Comput. 13 (1) (2017)
Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari
Computing the Maximum using (min, +) Formulas. MFCS (2017)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
Feasible Interpolation for QBF Resolution Calculi. Log. Methods Comput. Sci. 13 (2) (2017)
Meena Mahajan, Nitin Saurabh, Sébastien Tavenas
VNP=VP in the multilinear world. Inf. Process. Lett. 116 (2) (2016)
Meena Mahajan, Anuj Tawari
Sums of Read-Once Formulas: How Many Summands Suffice? CSR (2016)
Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation. Algorithmica 76 (4) (2016)
Meena Mahajan, Anuj Tawari
Sums of read-once formulas: How many summands suffice? CoRR (2016)
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh
Homomorphism Polynomials Complete for VP. Chic. J. Theor. Comput. Sci. 2016 (2016)
Meena Mahajan, Nitin Saurabh
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. CSR (2016)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
Understanding Cutting Planes for QBFs. FSTTCS (2016)
Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Space-Efficient Approximations for Subset Sum. ACM Trans. Comput. Theory 8 (4) (2016)
Andreas Krebs, Meena Mahajan, Anil Shukla
Relating two width measures for resolution proofs. Electron. Colloquium Comput. Complex. 23 (2016)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. ACM Trans. Comput. Theory 9 (1) (2016)
Meena Mahajan, Anil Shukla
Level-ordered Q-resolution and tree-like Q-resolution are incomparable. Inf. Process. Lett. 116 (3) (2016)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
Are Short Proofs Narrow? QBF Resolution is not Simple. STACS (2016)
Meena Mahajan, Nitin Saurabh
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. CoRR (2016)
Meena Mahajan, Nitin Saurabh
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. Electron. Colloquium Comput. Complex. 23 (2016)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
Feasible Interpolation for QBF Resolution Calculi. CoRR (2016)
Mikolaj Bojanczyk, Meena Mahajan, Thomas Schwentick, Heribert Vollmer
Circuits, Logic and Games (Dagstuhl Seminar 15401). Dagstuhl Reports 5 (9) (2015)
Meena Mahajan, Anuj Tawari
Sums of read-once formulas: How many summands suffice? Electron. Colloquium Comput. Complex. 22 (2015)
Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
The shifted partial derivative complexity of Elementary Symmetric Polynomials. Electron. Colloquium Comput. Complex. 22 (2015)
Meena Mahajan, Anuj Tawari
Read-once polynomials: How many summands suffice? CoRR (2015)
Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
Building above read-once polynomials: identity testing and hardness of representation. Electron. Colloquium Comput. Complex. 22 (2015)
Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials. MFCS (2) (2015)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
Feasible Interpolation for QBF Resolution Calculi. Electron. Colloquium Comput. Complex. 22 (2015)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
Are Short Proofs Narrow? QBF Resolution is not Simple. Electron. Colloquium Comput. Complex. 22 (2015)
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla
Feasible Interpolation for QBF Resolution Calculi. ICALP (1) (2015)
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh
Homomorphism Polynomials Complete for VP. FSTTCS (2014)
Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
Monomials, multilinearity and identity testing in simple read-restricted circuits. Theor. Comput. Sci. 524 (2014)
Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Space-Efficient Approximations for Subset Sum. Electron. Colloquium Comput. Complex. 21 (2014)
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh
Homomorphism polynomials complete for VP. Electron. Colloquium Comput. Complex. 21 (2014)
Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
Building above Read-once Polynomials: Identity Testing and Hardness of Representation. COCOON (2014)
Meena Mahajan, B. V. Raghavendra Rao
Small Space Analogues of Valiant's Classes and the Limitations of Skew Formulas. Comput. Complex. 22 (1) (2013)
Eric Allender, Vikraman Arvind, Meena Mahajan
Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series. Theory Comput. Syst. 53 (3) (2013)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. Electron. Colloquium Comput. Complex. 20 (2013)
Meena Mahajan
Algebraic Complexity Classes. CoRR (2013)
Maurice J. Jansen, Meena Mahajan, B. V. Raghavendra Rao
Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits. Comput. Complex. 22 (3) (2013)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. CoRR (2013)
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Small Depth Proof Systems. MFCS (2013)
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
Verifying proofs in constant depth. ACM Trans. Comput. Theory 5 (1) (2013)
Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
The Complexity of Unary Subset Sum. COCOON (2012)
Andreas Krebs, Nutan Limaye, Meena Mahajan
Counting Paths in VPA Is Complete for #NC 1. Algorithmica 64 (2) (2012)
Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs. MFCS (2012)
Meena Mahajan, Nitin Saurabh, Karteek Sreenivasaiah
Counting paths in planar width 2 branching programs. CATS (2012)
Meena Mahajan, Prajakta Nimbhorkar, Kasturi R. Varadarajan
The planar k-means problem is NP-hard. Theor. Comput. Sci. 442 (2012)

Meena Mahajan.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Meena Mahajan