People of ACM - Meena Mahajan
October 22, 2020
How did you initially become interested in theoretical computer science?
My first non-trivial interest in theoretical computer science was automata theory. Turing machines and cellular automata seem such simple devices and yet are so powerful—why is this so? While studying finite-state automata, I encountered lower-bound arguments concerning state space explosion, and arguments establishing non-regularity. The flavor of these arguments really appealed to my mind—a wonderful cocktail of logical thinking, combinatorial reasoning, some discrete mathematics, and modelling of computation—and got me hooked!
One focus of your research has been algebraic complexity, and in a 2019 article in Communications of the ACM, you, along with co-authors Madhavan Mukund and Nitin Saxena, noted that Indian researchers have developed numerous foundational results and proof techniques in this area. Will you discuss how advances in algebraic complexity are impacting other areas of computer science?
Algebraic complexity is driven by two differing goals. On the one hand, more efficient algorithms for specific algebraic problems (such as matrix multiplication, polynomial factorization, and testing polynomial identities) can yield efficient algorithms for a broad swath of problems which are not even algebraic in nature. On the other hand, obtaining non-trivial lower bounds for algebraic computation is a necessary step towards resolving the celebrated P-versus-NP question and its variants; thus every step forward in the quest for algebraic lower bounds brings us closer, in some sense, to the still-very-distant goal of understanding the power of nondeterminism.
You have said that combinatorial puzzles emerge in real-life situations more often than people recognize. Will you explain what you meant by this? What is an example of an interesting recent advance in the field of combinatorial algorithms?
When we teach NP-completeness, we describe Satisfiability, but inevitably the next NP-complete problems we discuss are problems like Vertex Cover, Clique, and Knapsack.
These problems model real-life situations, and stripped of the asymptotics, what are they if not combinatorial puzzles?! Take graph coloring—scaled-down versions of this on cleverly-chosen graphs can easily form the basis of single-player or even multi-player board games for elementary school children. Finding perfect matchings in graphs is just pairing up compatible items. And so on…
One of my all-time favorite combinatorial algorithms is the Gale-Shapley algorithm for the stable marriage problem. But that algorithm is hardly recent—it was devised before I was born. An interesting recent advance is hard to pick; there’s so much clever stuff going on worldwide! One result that I really like is the constant-factor approximation algorithm for the asymmetric Travelling Salesperson Problem, as proposed by Svensson, Tarnawski and Vegh. The authors repeatedly simplify the structure of the network using insights from polyhedral optimization, solve a related problem on the simpler network, and use the solution to retrieve a solution to the original problem. Why do I like this result? The algorithm is very clever and neat, it gives the first constant-factor approximation algorithm for this problem, and the problem itself is such a natural, simple-to-state, and enormously well-studied one. (The paper announcing this result won the Best paper Award at the 50th ACM Symposium on Theory of Computing, STOC 2018.)
How are organizations such as the Indian Association for Research in Computing Science (IARCS), as well as international collaborations, such as the Indo-German Max Planck Center for Computer Science at IIT Delhi and the French National Centre for Scientific Research (CNRS) research lab in Chennai, benefiting computer science research in India?
I can speak best from the viewpoint of theoretical computer science, although some comments could well apply to all of computer science research. IARCS has played a crucial role in fostering a sense of local community among theoretical computer science researchers in India. At a time when there were very few such researchers based in India, IARCS enabled the streamlining of activities that could enlarge this base, including organizing teacher-training workshops as well as summer schools and research workshops for graduate students.
Today the community has achieved critical mass. However, within specific subareas, the communities are still quite small. (For instance, one of the areas I have been working in for the last few years is proof complexity, and there are barely a handful of active researchers in this area in India. I hope this will change soon!) International collaborations, especially of the kind supported by IMPECS (with Germany) and Indo-French Centre for the Promotion of Advanced Research and CNRS (with France), have allowed researchers in India to tap a significantly larger pool of specialists as potential collaborators. These collaborations have provided avenues for graduate students in India to obtain wider international exposure, not only to research themes, but also to different academic cultures and styles. The current pandemic has sent us back to collaborating through virtual online interactions rather than exchange visits, but it is the real exchanges in the past that have made this possible.
For computer science research in India to achieve its potential, it is imperative that we researchers have a strong sense of local community as well as confidence about our standing in the international community. The impetus provided by the activities of IARCS and ACM India contributes immensely to both these goals.
What is a current challenge in your field?
Access to archival-quality literature. The open-access publication model can be a game-changer for many researchers, provided it is properly implemented as diamond access—free to author, free to reader. More important, beyond benefiting individuals, it can change the trajectory of future research by making immersion in a global space that much easier for everyone. We advance best when we advance together.
Meena Mahajan is a Professor at the Institute of Mathematical Sciences in Chennai, India. Her primary research interest is in computational complexity theory, with a current focus on proof complexity and algebraic complexity. She is also interested in combinatorial and discrete algorithms.
She has served in numerous professional roles in service to the field, including member and Past Chair of the Steering Committee of the IARCS Conference on Foundations of Software Technology and Theoretical Computer Science. Currently she is on the Board of Trustees for the Computational Complexity Conference as Paper Chair, a member of the Editorial Board of the Leibniz International Proceedings in Informatics, and an editor of Logical Methods in Computer Science. Since 2019, Mahajan has been an ACM India Eminent Speaker, where she gives talks on topics including computability and complexity, matchings in graphs, threshold circuits, and the power of negations in Boolean circuits.