Meena Mahajan

Eminent Speaker

Short CV:
Meena Mahajan is a professor in the theoretical computer science group at the Institute of Mathematical Sciences, HBNI, Chennai. She researches questions concerning computational complexity. As recreation, she loves solving jigsaw puzzles (creating order out of disorder), and also solving combinatorial puzzles, which crop up in real-life situations far more often than one may think.

Title of Talk 1: Compute, Compute, Compute—How Hard Can It Get?
Synopsis:
Modern technology, and in particular, computers, have dramatically altered lifestyles, and have significantly increased our dependence and reliance on computation. So, is it now a purely engineering challenge—with better technology and better software, can computers solve all problems arising in mathematics, science and engineering? Or are there fundamental limitations on what even the yet-to-be-built computers can do? And if so, then within those, what are the practical limitations? Does the theory of NP-hardness provide answers?

Title of Talk 2: Matchings in Graphs: What, Why, How ...
Synopsis:
Matchings in graphs are combinatorial objects that have been very widely studied, because they arise naturally in a host of application settings. In this talk, we will use various examples to illustrate and establish some fundamental properties of maximum and perfect matchings.

Title of Talk 3: Depth-2 Threshold Circuits
Synopsis:
Circuits with linear threshold functions as primitives are a natural model for computation in the brain. Small threshold circuits of depth two are efficient neural networks with one hidden layer. They cannot compute most functions, but how do we prove such a statement? And how do we lay our hands on explicit functions that they cannot compute? This talk gives an overview of the landscape.

Title of Talk 4: The Power of Negations in Boolean Circuits
Synopsis:
The building blocks of the digital age computers are gates implementing Boolean functions. Every Boolean function can be implemented using just binary AND, binary OR and unary NOT gates. Furthermore, certain Boolean functions, the monotone functions, do not even need the NOT gates. Nonetheless, even for monotone functions, using NOT gates can significantly reduce the size of the required circuitry. In this talk, we explore this mystery and survey known facts.

Qualifications: BTech and MTech in Computer Science & Engineering, IIT Mumbai; PhD in CSE, IIT Chennai

Title: Professor

Affiliation: Institute of Mathematical Sciences, HBNI, Chennai

Contact Details: meena@imsc.res.in