A Talk on “The Complexity of Computation, of Communication, and of Proofs” by Professor Meena Mahajan
ABOUT THE TALK
The notion of algorithmic computation is centuries old, as is the quest for efficient computation. A precise mathematical formulation of what can be considered efficient lies at the heart of the field of computational complexity.
The rules of logical reasoning, the art of debate, the nature of proof — these too have been objects of study for centuries. The field of proof complexity seeks to understand how long a proof needs to be, if it adheres to the syntax and the rule set of a specific proof system.
When multiple agents are involved in computation, as is increasingly often the case, the exchange of information between agents merits closer attention. Communication complexity focuses exclusively on analysing the amount of communication required.
Three different themes – algorithmic computation, logical reasoning, and the sharing of information – all viewed from the lens of complexity. This talk will highlight some intriguing and sometimes unexpected interconnections between these areas.
ABOUT THE SPEAKER
Professor Meena Mahajan is a professor at The Institute of Mathematical Sciences, 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. Professor Mahajan is an alumna of IIT Bombay (CSE B.Tech and M.Tech) and IIT Madras (PhD)
Professor Mahajan has held several professional roles, including member (and past chair) of the Steering Committee of the Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), and the executive council of the Indian Association for Research in Computer Science (IARCS). She is currently an editor of the journal Logical Methods in Computer Science (LMCS), a 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, and on the board of trustees of the Computational Complexity Foundation. She has served on several conference program committees as well as award committees. Prof. Mahajan is a Fellow of the Indian Academy of Sciences and a recipient of the J C Bose Fellowship. Prof. Mahajan serves on the ICM Structure Committee for ICM 2026.