Prized Science | Understanding autoimmune disorders; computer’s solution-finding

Read about Dipyaman Ganguly’s study on autoimmune disorders, and Neeraj Kayal’s work on transforming a philosophical problem into a mathematical one

Dipyaman Ganguly, principal scientist at CSIR-Indian Institute of Chemical Biology, has won this year’s Shanti Swarup Bhatnagar Prize for Medical Sciences. He explains how his research has uncovered, among other things, connections between the immune responses involved in autoimmune disorders and metabolic conditions such as diabetes. Edited experts:

What made you look for a connection between autoimmunity and metaflammation?

Dipyaman Ganguly, principal scientist at CSIR-Indian Institute of Chemical Biology

I have always been interested in the way our immune system often reacts against our own body and thereby causes a

Neeraj Kayal, principal researcher with Microsoft Research Institute in Bengaluru

The power and limits of computation

Neeraj Kayal, principal researcher with Microsoft Research Institute in Bengaluru, is one of the two winners of this year’s Shanti Swarup Bhatnagar Prize for mathematical sciences, sharing it with Apoorva Khare of IISc. Kayal’s work straddles a number of subfields. Read edited excerpts:

Tell us a little about your work.

I have worked in the areas of number theory, algebra, geometry, complexity theory and machine learning. I often explore computational questions in the context of concepts in number theory, algebra and geometry. Let me attempt to describe this with an example.

Can computers quickly solve “easy-to-describe” problems, such as finding solutions to a given system of equations? If someone gives us the solution then it’s easy to verify if it is correct by plugging in the values and doing a simple check. But finding the solution itself is usually much harder. But “how much” harder? What is remarkable is that this vague, almost philosophical-sounding notion of “how much harder” can be made mathematically precise so that this is not a philosophical question but actually a precisely defined mathematical question. Currently, we don’t know the answer although it is conjectured that a computational task such as finding solutions to equations (over a finite field) is in general very hard for computers.

What kind of problems have you worked on?

One of the early problems that started off my research career was about prime numbers. After the advent of computers, both mathematicians and computer scientists began asking questions such as whether a computer can “quickly” determine if a large number given to it is prime or not. My first paper, jointly with Manindra Agrawal and Nitin Saxena, addressed this question.

I have worked on some computational problems related to number theory, algebra and geometry but there is one problem that is dear to my heart and remains unsolved to this day. Let me explain. A problem that pertains to both number theory and algebra is finding solutions to equations. Once again, after the advent of computers, mathematicians and computer scientists started wondering if there is a computer program to which one can give any set of equations and it quickly find a solution and/or can quickly count how many solutions there are. There is a computer program that will try all possible solutions and check whether any of them satisfies all the equations, but if there are a large number of variables, say 1000, it would require such a huge number of steps that it would be infeasible in practice for the biggest imaginable computer.

Is there a faster way to solve such a problem? Another related question is what is the corresponding counting problem: out of the sets of values for a set of equations, how many are solutions? The widely believed conjecture here is that computers cannot solve such counting problems efficiently (in a few steps) but we don’t know. The Holy Grail of this subfield of computer science is to prove lower bounds: i.e. to prove that *any* computer program, no matter how clever, will take at least, say, 2^500 steps [two raised to the power of 500, or 2 multiplied by itself 500 times] to solve such a counting problem. A sequence of works involving me and my co-authors including Chandan Saha showed that under certain important restrictions, such a conjecture is true. Very recently, another set of scientists including two from India (Nutan Limaye, Srikanth Srinivasan and Sebastien Tavenas) substantially improved our result.

Why is it important to have such a conjecture?

Such a problem arose as a basic scientific question pertaining to the power and limits of computation. But besides being of interest in itself, it turns out that it is an assumption underlying all of cryptography. For example, if there was a fast algorithm to find solutions to equations, then one could use that to effectively snoop on mobile communications and that would for example severely compromise the security of our payment systems like UPI. Just to clarify, we believe there is no such fast algorithm to find solutions, so UPI is secure, but we don’t know for sure. It also turns out that while for a long time proving such lower bounds [the lower limits within which the conjecture holds good] was mostly a scientific challenge with hardly any practical applications, recently in some joint work (with Chandan Saha and Ankit Garg among others) we discovered that the lower bounds proofs that we have, limited/restricted though they are, are nevertheless useful in designing algorithms which find structure in data, i.e. solving certain problems in machine learning.

The Shanti Swarup Bhatnagar Prizes for Science and Technology were awarded to 12 researchers in seven disciplines. The annual prizes, given by the Council of Scientific and Industrial Research, recognise scientists under the age of 45 for notable or outstanding research. Read interviews of all 12 awardees in the Prized Science series