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: The Complexity of Formal Proofs
Synopsis: In a logical calculus, one starts with a few initial tautologies and axioms of some simple form, and uses specific inference rules to derive more complex tautologies. The derivation itself is thus a proof of the final statement. A good proof is not too long, and is not too hard to verify. Proof complexity formalises such calculi and proof systems, and analyses the structure and the length of derivations. It is intimately connected to fundamental questions in computational complexity. This talk will describe some ideas that have proved useful in designing short proofs, and some techniques that have been used to show that in certain settings, short proofs simply do not exist..

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 Fascinating World of Computational Complexity

Synopsis: Modern-day computers give us immense power to attack and solve many computational problems. Some problems are easy to solve. Some others are very hard. And some others -- we don't know yet. Computational complexity aims to classify problems according to their ease or hardness. Why is this a difficult task? And why is it so interesting?

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: [email protected]

About the Speaker