Featured Eminent Speaker of ACM India: Meena Mahajan

The ACM India Eminent Speaker Program (ESP) provides ACM Student and Professional chapters and institutional partners in India with direct access to top technology leaders, innovators and researchers who will give talks on contemporary and engaging issues that are important to the computing community. Chapters can invite ESP speakers to give talks as part of events that they hold. ACM India will help cover the costs for travel while the local chapter will arrange accommodation and local logistics. While most of the talks should be in-person to encourage interactions, some of the talks may be done virtually. For more details, see the ACM India ESP Page.

Meena Mahajan is a professor at The Institute of Mathematical Sciences, HBNI, Chennai, India. Her research focuses primarily on understanding the limits of efficient computation, and encompasses many aspects of computational complexity theory, including Boolean function complexity, algebraic circuits, and proof complexity. Meena is an alumna of IIT Bombay (CSE BTech and MTech) and IIT Madras (PhD).

Meena has served in numerous professional roles. She is currently an editor of the journal Logical Methods in Computer Science (LMCS), member of the editorial boards of the ACM Book series and the Leibniz International Proceedings in Informatics (LIPIcs), the advisory board of the journal TheoretiCS, the executive council of the Indian Association for Research in Computer Science (IARCS), and the board of trustees of the Computational Complexity Foundation. She has served on several conference program committees as well as award committees. Meena is a Fellow of the Indian Academy of Sciences, and a recipient of the J C Bose Fellowship.

What led you to work in the area of complexity theory?

Massive dollops of luck and being at the right place at the right time! I studied CSE at undergrad not so much by informed choice as because it was most sought after and I had the option. Over my bachelor's and master's studies, I built up a list of areas I did not want to pursue further! Theory wasn't eliminated, so I decided to try that for doctoral research. While there, I happened to find out about a lecture series on complexity theory that V. Arvind was going to offer at IMSc in 1988; I attended it, and I was hooked. It's a story I carry with me to this day. I attend a fairly broad range of talks in theoretical computer science, many far removed from my own current research interests, because otherwise I may completely miss something that would be just right for me. FOMO in the extreme! But it has worked wonderfully for me in academia, making me aware of many cross-connections and giving me many new research ideas.

For someone who is unfamiliar with computational complexity, how are innovations in this field impacting society?

At first glance, innovation doesn't seem to be the right word to use in the context of computational complexity, which, while rooted in understanding computation, is highly mathematical in nature. However, this research area indeed has made contributions that have been highly impactful. The most fundamental of these concerns the nature of proof. The notions of interactive proofs and zero-knowledge proofs, proposed and formalised by complexity theorists, provide significant theoretical underpinnings for cryptography research, and, with our current immersion in the digital world, who amongst us can possibly deny the societal impact of cryptography? Every time we do a digital payment, or authenticate our identity digitally, we are putting our faith in the hardness of cracking codes, and evidence for this hardness comes from complexity theory.

A closely related contribution comes from the study of the lengths of proofs. As we are becoming increasingly dependent on large system software, including in safety-critical settings, formally verifying such systems becomes increasingly crucial. While methods for formal verification come from a different research area, limits to their applicability get exposed by proof complexity. On another front, with large-scale distributed computing becoming the norm in many applications, communication becomes a major bottleneck. While clever design of distributed algorithms tells us what we can do, communication complexity is key to exposing the limitations.

What are important opportunities for those working in this area today?

The nature of computation is changing rapidly, from single-CPU activity to massively parallel computing, to massively distributed computing and storage, to highly interactive computing. Complexity theory needs to constantly formulate appropriate abstract computational models that reflect the changing realities, study their relative strengths and limitations, and examine trade-offs between newer resources. Great opportunities lie in exploring, for instance, lower bounds in circuit models that translate to limitations of specific deep-learning algorithms.

Do you think being a researcher enhances one's abilities as a teacher, or vice versa?

Maybe, and yes. I am not sure being a great researcher necessarily makes one a good teacher. To some extent, this depends on what one expects from a good teacher. Carry the class through, reaching even the weakest students? Deliver a good median experience? Train the cream? Researchers are not always trained in effective communication and logistics management, and excellent researchers could get completely bogged down by the nitty-gritty of managing the increasingly large classroom sizes we see today. However, I am sure that only the teachers-who-are-also-researchers can enthuse good and motivated students and lead them on to enter and love the world of academia and research.

In the other direction, my belief is unequivocal and unqualified – teaching enhances one's abilities as a researcher. Teaching pushes you to crystallise your thoughts, to identify key ideas and communicate them effectively, to be receptive to new approaches and suggestions thrown at you by students. (Yes, even after years of teaching the same course over and over again, a teacher can be pleasantly surprised by some insights coming from students.) And it is this clarity of thought, and this receptiveness, even if not the actual content, that makes you a better researcher as well.

How has being part of ESP been a rewarding experience?

I enjoy giving talks, and I enjoy talking with students. I work in a research institute and am relatively isolated from the worlds of undergraduate students. The Q&A sessions following my talks have pointed me to the kinds of questions intriguing today's students, and I am glad to have this better awareness. I joined the ACM India ESP just a few months before the pandemic, and so most of my ESP talks were delivered online. I categorically did not enjoy them! Online activity is undoubtedly better than no activity, and for interested students, it can be very useful. But from my point of view as a speaker, delivering an ESP-style talk to an online, faceless, remote audience simply did not spark any enthusiasm. My enjoyment giving talks comes from the interaction, which is inherent and implicit -- even when I am doing the talking, the facial response and body language of the audience members makes it a two-way communication process. This two-way nature is lost in online talks. I look forward to more in-person talks, and the joy and awareness it brings to me.

If your ACM Chapter would like to invite Meena Mahajan to give a talk, please follow the guidelines for inviting an ESP Speaker available here.

You can also start an ACM Chapter or become an ACM Member.