A round of questions with Subhash Khot

Subhash Khot  

This year, the International Mathematical Union awarded the Rolf Nevanlinna prize to Subhash Khot, Professor of computer science at New York University. The Indian-American computer scientist is known for having defined the Unique Games Conjecture. His work has achieved breakthroughs in algorithm design, approximation hardness and more.

The Rolf Nevanlinna prize is awarded once every four years for outstanding contribution in mathematical aspects of information sciences. It is given to mathematicians under forty years.

You grew up in Ichalkaranji – which may not have had the best facilities, such as libraries. How did you work around this to study advanced mathematics?

Ichalkaranji is a large town with about 250,000 people. However, there was zero awareness of math and science research and zero facilities. Almost no one had heard of the IITs or the Math Olympiad. The only things people knew about were the board exams.

How did you get to know about these?

It was a stroke of luck. The students in my town would prepare for the Class X and XII exams and a few competitive exams including the National Talent Search exam. They prepare quite well, but what it lacked was awareness of what lies beyond the Tenth grade, of higher math or research. Everyone focussed on the State board exams so that they could go to a good college.

As luck would have it, my high school teacher Mr Gogate paid a lot of attention to what students were studying. He gave us books and so on, but he wasn’t familiar with higher maths. One day Prof Katre, who was a professor at University of Pune was visiting Mr Gogate (he grew up in Ichalkaranji and his family used to be tenants of my school teacher) and I happened to meet him. He suggested that I appear for the Mathematics Olympiad [and told me]what books I should read. He also suggested a school in Pune – Bhaskaracharya Prathisthan – where I could study and develop my mathematics.

Once I entered into the Math Olympiad stream, things happened automatically. I had to study on my own, but when I went to Bhaskaracharya Prathisthan, I met students from other cities, and heard about the IIT exam. But I had to prepare on my own – which was a good thing because when you learn everything the hard way, you learn better.

What books did you read then?

I read many science books when I was in high school – Russian science books published by Mir Publishers which were translated into Marathi. This was remarkable. The headmaster also had some NCERT textbooks which were very good.

You topped the IIT entrance exam, how did it feel then?

I wasn’t surprised to be in the top ten or twenty ranks. This was because I studied using the material from Brilliant Tutorials. They used to conduct onsite exams every six months. These would be attended by students from all over the country, and they would give you a rank. I always used to be among the top five or ten students, so I knew I would do well. But standing first was like winning a lottery, involving lots of luck.

When you topped IIT JEE you chose to pursue Computer Science at IIT Bombay. What guided this choice?

I had never seen a computer before I reached IIT Bombay, but I had studied a fair amount of mathematics. I knew that many of my senior students in the Math Olympiad programme were also top rankers in IIT-JEE and had chosen to pursue Computer Science. Also, my cousin was in IIT Bombay (3 years older than me). He told me that the study the mathematical aspects of computer science was essentially mathematics. This was useful information to have.

Both your parents were doctors, how did you get interested in mathematics?

I was attracted to physics, chemistry and mathematics when I was young. But it occurred to me that underlying all this is mathematics. In order to understand the sciences, one has to understand mathematics. Then came the Math Olympiad. When I started solving challenging problems, it became a natural choice for me.

How was the environment at IIT-Bombay?

Moving from a small town to Bombay was a bit difficult in the beginning. Also, I was not so comfortable with English. But it was not so bad, as it was within the same State as my hometown, so I knew the local language, Marathi. I also had a cousin there. He was there for a year after I joined and helped me get into the system.

But the real tragedy struck when within a month of joining, my father died. I had to cope with that. On the academic front I was very strong and well prepared so I could take it.

A major difference was that the teachers were real experts. For the first time (apart from the teachers I met in the Math Olympiad programme) I was meeting people who could answer my questions. My friends and classmates were also good at the subjects and there was a serious but healthy competition. There was no negative side to it.

Can you tell us about how you formulate the questions you work on?

As it happens in many areas, in mathematics also, there are open questions – those which are universally recognised as important questions. Typically, I chose some of these important problems. In some cases, I was able to solve them. In some other cases, in the process of attempting to solve them, I came up with new questions or even new approaches to answer them. There was a class of questions that researchers were stuck with and I came up with the Unique Games Conjecture which is an approach to these problems.

What is the motivation to do theoretical computer science? Can you talk about your work?

The main motivation behind theoretical computer science is to solve computational problems fast.

We know and use a computer because we want to run applications. For instance, we use Google maps to find the direction, say, from Bangalore to Delhi. It gives the solution within a fraction of a second and makes sure it is optimum. What is being done? The computer is running an algorithm to find the best or optimal direction. Different apps require different algorithms. Theoretical computer scientists design these algorithms. These algorithms have to run fast. Designing and implementing algorithms are different things.

If you investigate this further to discover for which computational problem you can design fast algorithms, you will see that there is a mathematical reason why you cannot design a better algorithm for some problems.

Take this problem. Start at one city and you visit all the major cities in India and come back. You have to find the route which takes the minimum time to do this. Is it possible to find such a route? Computer scientists believe that it cannot be done. There is no fast algorithm to solve the tour problem, but perhaps we can find the solution that will take nearly (approximately) the minimum time? Indeed, it is possible to find an algorithm with nearly the minimum time.

This idea of finding approximate solutions, that’s more or less what I work on.

When did you get to hear about being selected for the Nevanlinna prize? How do you feel about it?

I was told in the first week of March. I had to keep it a secret from all except my closest family upto August. These members of my family accompanied me to the congress in Seoul. It was a bit difficult to keep the secret, especially from my school teacher, who would have been so happy.

It was nice, but not super surprising. Because this prize is given to mathematicians under forty and there are not that many candidates in a given year. I knew I was among the 5-10 candidates who may be given the prize. Still, when it happens it is a surprise.

The theoretical computer scientists already know about my work. This prize has brought it to the knowledge of people outside this group. But as far as my future research is concerned, the prize does not change anything much.

Our code of editorial values

Related Topics
This article is closed for comments.
Please Email the Editor

Printable version | Nov 26, 2021 1:49:13 PM |

Next Story