Meena Mahajan

According to our database1, Meena Mahajan authored at least 100 papers between 1989 and 2020.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2020
MaxSAT Resolution and Subcube Sums.
Electron. Colloquium Comput. Complex., 2020

Algebraic Branching Programs, Border Complexity, and Tangent Spaces.
Electron. Colloquium Comput. Complex., 2020

Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution.
Electron. Colloquium Comput. Complex., 2020

SAT and Interactions (Dagstuhl Seminar 20061).
Dagstuhl Reports, 2020

Lower bounds for linear decision lists.
Chic. J. Theor. Comput. Sci., 2020

2019
The Presburger Award for Young Scientists 2020 - Call for Nominations.
Bull. EATCS, 2019

Research in theoretical computer science.
Commun. ACM, 2019

2018
Are Short Proofs Narrow? QBF Resolution Is <i>Not</i> So Simple.
ACM Trans. Comput. Log., 2018

Sums of read-once formulas: How many summands are necessary?
Theor. Comput. Sci., 2018

Shortest path length with bounded-alternation (min, +) formulas.
Electron. Colloquium Comput. Complex., 2018

Computing the maximum using (min, +) formulas.
Electron. Colloquium Comput. Complex., 2018

Short Proofs in QBF Expansion.
Electron. Colloquium Comput. Complex., 2018

Building Strategies into QBF Proofs.
Electron. Colloquium Comput. Complex., 2018

Lower Bound Techniques for QBF Proof Systems.
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

2017
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials.
Theory Comput., 2017

Understanding Cutting Planes for QBFs.
Electron. Colloquium Comput. Complex., 2017

A Quest for Structure in Complexity.
Bull. EATCS, 2017

Arithmetic Circuits: An Overview (Invited Talk).
Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016
VNP=VP in the multilinear world.
Inf. Process. Lett., 2016

Level-ordered Q-resolution and tree-like Q-resolution are incomparable.
Inf. Process. Lett., 2016

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.
Electron. Colloquium Comput. Complex., 2016

Relating two width measures for resolution proofs.
Electron. Colloquium Comput. Complex., 2016

Homomorphism Polynomials Complete for VP.
Chic. J. Theor. Comput. Sci., 2016

Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation.
Algorithmica, 2016

2015
Sums of read-once formulas: How many summands suffice?
Electron. Colloquium Comput. Complex., 2015

Are Short Proofs Narrow? QBF Resolution is not Simple.
Electron. Colloquium Comput. Complex., 2015

Feasible Interpolation for QBF Resolution Calculi.
Electron. Colloquium Comput. Complex., 2015

Circuits, Logic and Games (Dagstuhl Seminar 15401).
Dagstuhl Reports, 2015

Read-once polynomials: How many summands suffice?
CoRR, 2015

2014
Monomials, multilinearity and identity testing in simple read-restricted circuits.
Theor. Comput. Sci., 2014

Space-Efficient Approximations for Subset Sum.
Electron. Colloquium Comput. Complex., 2014

2013
Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series.
Theory Comput. Syst., 2013

Small Depth Proof Systems.
Electron. Colloquium Comput. Complex., 2013

Algebraic Complexity Classes.
CoRR, 2013

Small Space Analogues of Valiant's Classes and the Limitations of Skew Formulas.
Comput. Complex., 2013

Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits.
Comput. Complex., 2013

2012
The planar k-means problem is NP-hard.
Theor. Comput. Sci., 2012

Counting classes and the fine structure between NC<sup>1</sup> and L.
Theor. Comput. Sci., 2012

Verifying Proofs in Constant Depth.
Electron. Colloquium Comput. Complex., 2012

Counting Paths in VPA Is Complete for #NC 1.
Algorithmica, 2012

Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

The Complexity of Unary Subset Sum.
Proceedings of the Computing and Combinatorics - 18th Annual International Conference, 2012

Counting paths in planar width 2 branching programs.
Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, 2012

2011
Verifying Proofs in Constant Depth.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

2010
Planarity, Determinants, Permanents, and (Unique) Matchings.
ACM Trans. Comput. Theory, 2010

On the Complexity of Matrix Rank and Rigidity.
Theory Comput. Syst., 2010

Arithmetizing Classes Around NC\textsf{NC}<sup>1</sup> and L\textsf{L}.
Theory Comput. Syst., 2010

Counting paths in VPA is complete for #NC<sup>1</sup>.
Electron. Colloquium Comput. Complex., 2010

Longest Paths in Planar DAGs in Unambiguous Log-Space.
Chic. J. Theor. Comput. Sci., 2010

Frontmatter, Table of Contents, Preface, Conference Organization, Author Index.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009
Parameterizing above or below guaranteed values.
J. Comput. Syst. Sci., 2009

On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata.
J. Autom. Lang. Comb., 2009

Upper Bounds for Monotone Planar Circuit Value and Variants.
Comput. Complex., 2009

Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata.
Proceedings of the Language and Automata Theory and Applications, 2009

Small-Space Analogues of Valiant's Classes.
Proceedings of the Fundamentals of Computation Theory, 17th International Symposium, 2009

Small space analogues of Valiant's classes and the limitations of skew formula.
Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

Longest Paths in Planar DAGs in Unambiguous Logspace.
Proceedings of the Theory of Computing 2009, 2009

2008
Simultaneous matchings: Hardness and approximation.
J. Comput. Syst. Sci., 2008

Rigidity of a simple extended lower triangular matrix.
Inf. Process. Lett., 2008

Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae.
Electron. Colloquium Comput. Complex., 2008

Some perfect matchings and perfect half-integral matchings in NC.
Chic. J. Theor. Comput. Sci., 2008

2007
Block Sorting: A Characterization and some Heuristics.
Nord. J. Comput., 2007

Arithmetizing classes around NC^1 and L.
Electron. Colloquium Comput. Complex., 2007

Polynomial Size Log Depth Circuits: Between NC<sup>1</sup> and AC<sup>1</sup>.
Bull. EATCS, 2007

Arithmetizing Classes Around NC <sup>1</sup> and L.
Proceedings of the STACS 2007, 2007

2006
Approximate Block Sorting.
Int. J. Found. Comput. Sci., 2006

On the Complexity of Rank and Rigidity.
Electron. Colloquium Comput. Complex., 2006

Evaluating Monotone Circuits on Cylinders, Planes and Tori
Electron. Colloquium Comput. Complex., 2006

Parameterizing MAX SNP Problems Above Guaranteed Values.
Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

On the Bipartite Unique Perfect Matching Problem.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005
Simultaneous Matchings.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

2004
The complexity of planarity testing.
Inf. Comput., 2004

The combinatorial approach yields an <sub>NC</sub> algorithm for computing Pfaffians.
Discret. Appl. Math., 2004

Seeking a Vertex of the Planar Matching Polytope in NC.
Proceedings of the Algorithms, 2004

Towards Constructing Optimal Strip Move Sequences.
Proceedings of the Computing and Combinatorics, 10th Annual International Conference, 2004

2003
On Sorting by 3-Bounded Transpositions.
Electron. Notes Discret. Math., 2003

Merging and Sorting By Strip Moves.
Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2000
A note on the hardness of the characteristic polynomial
Electron. Colloquium Comput. Complex., 2000

A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999
Determinant: Old Algorithms, New Insights.
SIAM J. Discret. Math., 1999

Parameterizing above Guaranteed Values: MaxSat and MaxCut.
J. Algorithms, 1999

A Combinatorial Algorithm for Pfaffians
Electron. Colloquium Comput. Complex., 1999

Arithmetic Complexity, Kleene Closure, and Formal Power Series
Electron. Colloquium Comput. Complex., 1999

1998
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds.
Theor. Comput. Sci., 1998

Determinant: Old Algorithms, New Insights (Extended Abstract).
Proceedings of the Algorithm Theory, 1998

1997
Parametrizing Above Guaranteed Values: MaxSat and MaxCut
Electron. Colloquium Comput. Complex., 1997

Determinant: Combinatorics, Algorithms, and Complexity.
Chic. J. Theor. Comput. Sci., 1997

A Combinatorial Algorithm for the Determinant.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1995
Nondeterministic, Probabilistic and Alternating Computations on Cellular Array Models.
Theor. Comput. Sci., 1995

A Note on Mod and Generalised Mod Classes.
Inf. Process. Lett., 1995

Logspace Verifiers, NC, and NP.
Proceedings of the Algorithms and Computation, 6th International Symposium, 1995

1994
A Note on SpanP Functions.
Inf. Process. Lett., 1994

Non-commutative Computation, Depth Reduction, and Skew Circuits (Extended Abstract).
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994

1993
Language Classes Defined by Time-Bounded Relativised Cellular Automata.
RAIRO Theor. Informatics Appl., 1993

1992
Some results on time-varying and relativised cellular automata.
Int. J. Comput. Math., 1992

1991
Relativised Cellular Automata and Complexity Classes.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991

1990
Fuzzy L-systems.
Int. J. Comput. Math., 1990

1989
Hexagonal Cellular Automata.
Proceedings of the A Perspective in Theoretical Computer Science, 1989

Systolic Pyramid Automata, Cellular Automata and Array Languages.
Proceedings of the Array Grammars, Patterns and Recognizers, 1989

Systolic Pyramid Automata, Cellular Automata and Array Languages.
Int. J. Pattern Recognit. Artif. Intell., 1989


  Loading...