The HLF Portraits: Subhash Khot
Video in TIB AVPortal:
The HLF Portraits: Subhash Khot
Formal Metadata
Title 
The HLF Portraits: Subhash Khot

Title of Series  
Author 

License 
No Open Access License:
German copyright law applies. This film may be used for your own use but it may not be distributed via the internet or passed on to external parties. 
Identifiers 

Publisher 

Release Date 
2017

Language 
English

Content Metadata
Subject Area 
00:00
Musical ensemble
Family
00:36
Point (geometry)
Principal ideal
Computer programming
Observational study
State of matter
Multiplication sign
Inclined plane
Routing
Student's ttest
Mereology
Regular graph
Rule of inference
Theory
Wave packet
Expected value
Mathematics
Root
Manysorted logic
Term (mathematics)
Energy level
Set theory
Physical system
Social class
Gradient
Complete metric space
Sphere
Arithmetic mean
Universe (mathematics)
Right angle
Pressure
Family
Arithmetic progression
Annihilator (ring theory)
09:45
Point (geometry)
Axiom of choice
Computer programming
Observational study
Decision theory
Multiplication sign
Student's ttest
Applied mathematics
Hypothesis
Expected value
Mathematics
Latent heat
Term (mathematics)
Körper <Algebra>
Physical system
12 (number)
Generating set of a group
Gradient
Projective plane
Physicalism
Line (geometry)
Faculty (division)
Universe (mathematics)
Right angle
Musical ensemble
Annihilator (ring theory)
18:25
Point (geometry)
Complex (psychology)
Group action
Observational study
State of matter
Length
Direction (geometry)
Multiplication sign
Student's ttest
Mereology
Distance
Theory
Goodness of fit
Mathematics
Latent heat
Term (mathematics)
Modulform
Theorem
Körper <Algebra>
Rhombus
Physical system
Area
Pairwise comparison
Process (computing)
Gradient
Computability
Maxima and minima
Numerical analysis
Approximation
Field extension
Proof theory
Right angle
Figurate number
Mathematician
27:41
Category of being
Length
Direction (geometry)
Moment (mathematics)
1 (number)
Right angle
Maxima and minima
Körper <Algebra>
Approximation
28:38
Process (computing)
Observational study
Direction (geometry)
Uniqueness quantification
Projective plane
Similarity (geometry)
Travelling salesman problem
Flow separation
Latent heat
Reduction of order
Right angle
Körper <Algebra>
Game theory
Arithmetic progression
Resultant
33:29
Point (geometry)
Uniqueness quantification
Direction (geometry)
Projective plane
Student's ttest
Mass
Expected value
Natural number
Phase transition
Heuristic
Right angle
Körper <Algebra>
Game theory
Arithmetic progression
Mathematical optimization
38:09
Mortality rate
00:00
[Music]
00:17
professor god I'd like to begin before you are a professor maybe even before you think you're going to be a professor in your childhood where are you what is your family like I was born in India in a town called HL chironji it's in
00:36
southern southern and western part of India about ten hours drive south from Bombay cultural spheres yes it's in the state of Maharashtra whose capital is the city of Bombay so it's exactly half way through Bombay and another city which people might know Bangalore yes yeah especially yes yes I was born there so everybody in my family is a doctor so my parents my mother is a doctor my father was a doctor my preserver is now doctor Ian so I guess somehow the
01:29
expectation was that I would end up the intro dr. and I didn't have any specific inclination towards any particular scientific topic certainly not when I was in third grade or fourth grade but slowly slowly happened let's just arbitrarily say do 10 now are you stealing to your parents library looking inside different books are you indifferent to that are you mostly interested in football I mean what sort of Shari so I wasn't heavily into sports or any specific extracurricular activities and I was good in studies prophesy I did play a lot but nothing which can be called organized or systematic sports but in fact I played a lot I was probably the most active kid in my class also would add studies and when I was in the 4th grade and the fifth grade so soon the in our the state we have mathematics exams at regular intervals in the in the in the high school so after I was already doing well in these mathematical exams one in the fourth grade and one in the fifth grade and the one which is in fifth grade and there's also version in the eighth grade these are called Garnett pravinia exams so this translates to is mathematics talent exams and these are actually quite advanced for those levels they are comparable to for example the International mathematical Olympiads which are well known yeah in terms of their quality and the difficulty yes yeah so because of these exams and since I was doing well I'm it was clear that I was good at not this is a state school private school that you're in the school itself it's it's a it's a public school or does the state frontend school and clearly it seems like the state has a theory of searching for talent and then sending young people according to the routes that the talent indicates so you're being tested they're examining you and others you are turning out to be not without certain ability in mathematics does that mean your faith becomes for ordained in terms of the schooling system no not really it's a it's it's a at least in those days it was a bit strange situation in the sense that as I said we have these exams which included math but there were also exams which included languages things and this was until 8th grade and perhaps even tenth grade but and up to those levels I would say I was very well prepared but somehow beyond that it was in some sense complete darkness so for example I mean nobody in my town which is a large town with a couple of hundred thousand people and certainly in that time nobody knew anything about higher mathematics or the surely research done in universities this was early 90s and yes but somehow by rather actually miraculous circumstances somehow I was introduced to the right people I was given access to the right set of books so for example my mother and my high school principal mr. Gupta so these two were really instrumental in guiding me in the senses are right they would go and actually find out what's what what's there after you are done with let's say the tenth grade and they would find books so mr. Bach day he produced me to professor with the name of car three he is he's a professor in the math department in Pune University so Pune is a another large city not far from Bombay and that was I think very actually big somehow coincidence that I managed to make him and he knew about these international mathematical Olympiads which students participate in them there in eleventh and twelfth grade because and that I asked the following question I want the child's reaction to all of this do you feel pressure do you feel that you are following the advice of your elders and so you will do what they say what is your internal discussion about this pressure at all there was no pressure whatsoever it was more like yes I mean you seem to be good at it and these are the resources we can make available to you and then it's up to you young young turned out I was interested and apparently could have these things yes there was no pressure what said well did you know each other our brother and was he any of the same rules intellectual roots the same yeah we went through roughly the same process but at some point he he decided to take medicine so he's a doctor a gastroenterologist so you are the wild rebel you go become a doctor but I clearly know University is that's where you begin to get guidance and in what we would call Iraq Alex yeah so for my introduction to higher mathematics was primarily through these international mathematical Olympiads these are I suppose well known to people yeah and then so so India actually has a very serious training program for high school students high school meaning in India it's called eleventh and twelfth grade so there are serious programs to train students to participate in the math Olympiads but for me they show us I was in this town which was somehow a remote town and I just don't know anything that even these exams exist and but but as I said through mr. Gupta and mr. Caffrey I somehow managed to find out about these and yeah then I had the books all the books to prepare and then there was a issue in the sense that there was nobody to actually guide as such so I had to I had to prepare myself reading all these books also spent a short amount of time maybe a week or so in a math Institute in Pune called Pass Karachi Pakistan and that was very nice would you describe yourself as having passion through switches so progression
09:50
and curiosity still yeah it's all combined together interacting and there is also passion you realized that you are doing well you see all these books and they're fascinating and actually it wasn't just mathematics mathematics I was always doing but times I was also very fascinated with chemistry and physics and one of the things I remember about chemistry and physics is so somehow we have these amazing Russian books which we are translated into the local language which is for Meraki the and yeah those were really amazing and I was yeah I was quite fascinated with both chemistry and physics as well yeah but somehow I slowly write in what dragonoid tracked but at some point for she to make decisions yeah yes so so in India the system is very rigid so what you have to do is at the end of the 12th grade you simply have to decide I want to be a doctor or I want to be an engineer or I want to pursue pure sciences so you simply have to decide at the end of 12th grade which is clearly nearly very early and even in 12th grade I wasn't completely sure that I necessarily wanted to do write sciences and not medicine yeah I saw I had to choose I was also admitted to the Indian Institute of Technology which are the premier engineering institutes in India even then I had to choose right as computer science or say mathematics and I chose computer science which Chile in hindsight was very in inform uninformed decision but but the right one it seems because I'd never even seen a computer before I entered the institution before my first year in college I had never even seen a computer but somehow I was told by some friends that with the friends that I met in the in the math Olympiad program and these were friends from other big cities who knew who had much better idea of how things work yes I was told that there are aspects of computer science which are effectively same as mathematics and you could do that yes why more or less took that to that advice on faith and it turned out that there are aspects of computer science which are very very mathematical and that's what is what I do now very career this is making reach a distinction between Science and Mathematics and when we take your long in your career I'd like to talk more about those distinctions if they exist but what's interesting is like anything that people I've interviewed in this series and you're coming into the world of the line at a point of our computer science is even considered a field people just one generation above you are stumbling into the world that they later will contribute to tremendously but the words computer science are virtually nothing in there but for you already there's an established world out there that you can enter into you can specialize in computer science have you discovered the joy of the computer what did you think that again the computer field was going to lead you did you again how many expectations or was it just one problem by another as you developed your intellectual curiosity maybe you just stumbled so the computer science as I already said I more or less tumbled onto the subject I was really a math person in terms of interests and training up to that point and then since I chose the computer science as my major I mean of course I had to do all the coursework and I had to know about operating systems and programming languages [Music] yeah but then as we will right become a third year or fourth years florentine college you have to choose specific I don't know this semester longer year long projects right and then at the end of the college you also need to where it was a standard practice then that you would apply to the US universities for a ph.d program right so and then you would have to say what you are interested in yeah let's say this for because the computer science feel that that will apply mathematics has develop so fast in your career that I wonder about what as you look back was known and not known at this point I mean you are finishing a computer course at the distinguished in the university you're about to go to the United States broadly to look back with what is known at this point where where are what is your sense of the field there's a seegar yes so somehow I always felt that I'm kind of wandering in darkness and is once in a while I just stumbled on two things so for example when I was I applied to the PhD programs in United States and I was admitted to the topmost PhD programs in computer science and in particular the theoretical computer science which is really the study of mathematical aspects of computer science but I knew very little about what the actual research that goes on in these universities I had very little access to even internet and in fact the internet was so slow that all I wanted to do was to go to web pages of the professor at these universities and see what they were doing and it was too slow I just I couldn't even really figure out what the topics of research are couple of phone conversations with the faculty members of these universities I mean who are trying to attract me to their University and I was really was the word or I was fact nervous he wound up talking to these people because I mean nothing yeah but you know I had to make a choice why I chose the Princeton University for PST well I guess mainly because I'm you know a student who was couple of years my senior from from IIT Bombay and yeah so as you thesis yes it's I had done one semester long pieces and one another year long pieces yeah I mean these were some specific topics in theoretical computer science which I mean I don't I don't know these anymore well somebody is sensing that you have a future in this field or you will end up in the in one of the great
18:09
universities support but there you go again I've been use the word stumble a lot I don't think it's probably the exactly the right word you're following your instincts and you are at now in Princeton okay what is the guidance that you are
18:25
now getting now that you are in a place with good internet sophisticated computer technology what diamonds are you getting no no once I was in Princeton everything was just clear in some sense that I mean essence immediately I had access to the best resources the best researchers right so after that it was just a matter of in some sense me doing my job as a PhD student which is to read research papers and research talks select research problems and work on them and solve them yeah so once I was impressed from yeah I would say the things were much clearer and easier I mean there is some issue of right I mean you end up in a completely new place one needs to adjust in terms of just the living or the life or the yeah cultural things yeah but academically it was yeah once I was in Princeton it was easy I suppose yeah so I had wonderful not wiser Sanjeev Arora in principle there is Institute for Advanced Studies with the group of avi Winterson in computer science so there are plenty of talks I could go to any conferences that I would want to 5 into conferences right it's for century 999 and I mean I just support and again I'd ask if it interest you in the state of the field of applied mathematics as applied to computer at this point I mean are we are there buzzwords of the time is artificial intelligence circulating is one of the frameworks for inquiry what what is the again the direction because things change so fast in your field you just yeah maybe one needs to make a distinction between what is theoretical and what is applied it's a very very subjective term for example pure mathematicians may call theoretical computer science as applied mathematics right whereas I'm a theoretical computer scientist and I will call other parts of computer sciences applied which is artificial intelligence graphics operating systems right yes now for me personally yeah I consider myself a theory person right theoretical person so theoretical computer scientist and mathematician so I actually I mean I have taken courses right in all the applied side of computers I'm in a computer science department and right and I interact with colleagues and attend talks so I has some view of computer science of outside of theoretical computer science yeah but I wouldn't I don't think myself as competent enough to make any comments on the direction or a big picture I'm really a theory person so I prove theorems I sit in my office I write theorems on the board right and I stare at the ceiling or the sky and I think sometimes wonder in Washington Square Park when I was a grad student in Princeton at the Institute for Advanced Studies that was actually in fact when I came to Princeton on my first day it was amazing it was the most beautiful place one had ever seen in fact after that the Harry Potter movies came right and they have this forwards School of wizardry yeah so in hindsight the my experience of Princeton was this entering Hogwarts in fact all the graduating from incoming grad students they are placed in this dormitory called Graduate College I'm not sure if you have seen this that exactly have the feel of Hogwarts and they have this amazing dining hall which is quite similar to what you would see in Harry Potter and actually those College architecture in the army I really was the fantasy of English style so you were exactly right from their aspiration so you have a great mentor I think the president who was and what was his field Sanjeev Arora he's he's a professor in Princeton computer science department so he is in fact the area of very specific area of research that I work on is called probablistic elite checkable proofs and also it's called hardness of approximation for npcomplete problems so he was one of the early founders of this research area another mentor in Princeton was a V Wilkerson is is at Institute for Advanced Studies I mean though I I haven't really worked directly with avi on anything specific I mean he's just this father figure right inspiring figure another mentor is Johan hosta that he is he's in Stockholm but he was visiting Princeton for a year when I was a graduate student so yeah so that was another very good mentorship experience I want to well is the important in your career this question and I want to say it as Malayan to make sure what I understand what I don't understand it boils down to the the sense of what the computer can actually achieve compute if I'm right that while we know that the computers certainly can be tested can be used for verification it's a question of what they can solve it not solve is that it's at the core of this this issue yeah I'm assuming you're yeah you're right in the broader sense so more specifically a computational complexity that's the name of the subfield it's a subfield of theoretical computer science and the subject here is I mean we know that there are many many computational problems that we want to solve and then I say we want to solve I mean we want to solve fast right yeah and then the question is classification of these problems according to what their inherent difficulty is right and turns out some problems you can solve them fast some problems cannot be solved fast and and in fact in some cases even that is a good news that some there are problems which cannot be solved fast so for example right I'm sure you would be happy to know that people cannot break into crypto systems right and that actually right so it's a it's an example of a computational problem which cannot be solved fast right breaking into computer system or your banking accounts right so one should be thankful that there are problems which cannot be solved fast yes so combinational complexity is the study of classification of problems according to their inherent hardness or difficulty and then it then it takes many many different forms so one specific topic which is my area of research is turns out there are many many computational problems these are known as NP complete or NP hard problems the most perhaps well known example is there traveling salesperson problem where you are given a large number of cities all pairwise distances between the cities and your goal is to start at one city let's say New York and visit all the cities come back to New York while minimizing the total distance that you travel okay it's a computational problem which is evidently yourself evidently we would
27:01
like to solve fast but turns out nobody knows how to solve this problem fast and computer scientists very strongly believe that there is no fast algorithm for this so it is inherently also so it's inherently unsolvable but this is what computer scientists very very strongly believe ok now once you accept this essentially fact of life you can ask the next question that okay maybe I cannot find the two of the minimum length but maybe I can find a
27:43
tour of length which is close to the minimum writers which might be good enough in practice so this is notion of an approximation right yeah and then if
27:54
I have to say in one sentence what I do for my research is I classify npcomplete problems into categories as to which ones we can find good approximate solutions and which ones we cannot was there a Eureka moment after you develop this background the Princeton's of this variant or where you began to see the direction of your work would go in across yes yes and no in the sense that so so this particular field of approximations
28:40
is it was already a very established field of research when I entered graduate studies so in particular right Sanjeev Arora and Johann hosta and several others they already had foundational results on this topic throughout the 90s right so so there was definitely a direction though I would say that when I started my graduate studies this direction seemed a bit stuck right and right meaning right there were many many very difficult questions to be answered right but we were seemingly stuck yeah yes when I started I started in 99 so it took me at least two years to just survey or read about everything that was known and once I was at least an expert in the sense that I knew what was already done yeah then it was kind of clear that this this project was stuff and yeah and then since then now so since early 2000 so for about 20 years now we have been making I must say I would say significant progress and we are in process of getting out of this stuck situation this is of course the
30:23
collective process I understand that button the you of the we and with it he said on to articulate to help instead unstick the field yeah so one of the specific things I mean I personally did it was to propose a conjecture called unique games conjecture it simply amounts to saying that there is a very specific concrete problem well not quite same as traveling salesman problem but something similar and I conjectured that this problem is very hard to solve and even very hard to approximate and and then this is one of the key key issues in theoretical computer science which problems are hard and which problems are not or which problems are easy right and an even proposing that a certain problem is hard is at least in hindsight is a contribution in itself right and and we still don't know for sure whether this unique games problem whether it's hard or not though we do have very significant progress me and my coauthors in the last three years or so indicating that yes it's indeed the case that this problem is very likely to be hard and nevertheless well and if you to believe that this problem is hard it turns out a by a process called reduction you can show that many many other problems are also hard which we we have no clue about their status we are so conditioned along this problem being hard we have made lots of profits the progress is in knowing which you yeah the progress is in knowing that there are several problems that we are interested in and they are hard as well in knowing that several problems are hard when suppose you know the father is hard any question we simplify a very complex process once you when she dela is that when you've said the approximation in worried when I said hard a ligament they're hard to even approximate even we already know that all these problems are already hard to find the exact solutions right and what I have been doing or what this idea is doing is try to show that these problems remain hard even to approximate there could be even something beyond that once you realize that these problems are hard work even hard to approximate you can ask further questions are they hard even on instances that actually arise in practice or they just happen to be hard
33:31
on instances they that might not even arise in practice so there are many many questions of more refined nature and it's these words and you can tell me that is this an optimistic expectation of future inquiry or is this an acknowledgement that there are some doors that stay closed I don't like the words optimistic what's the specimen step it is what it is you're trying to discover or establish what is reality right and if there are hard problems then yes there are hard problems as already said even having a hard problem has its own advantages if there were no hard problems then you are not never going to have any cryptography you will never have secure back accounts nothing is going to be secure and even if there are hard problems you can try to find ways around it right so for example you can try to design what are known as heuristics these are algorithms which which are not guaranteed they do not come up with hundred percent guarantee that they will work but sometimes they work maybe they work well enough in practice right so right so there are ways of dealing with even hard problems as becomes were the end of the about the role the Democrats to mentally channelization of collaboration when you came closer to your insights were there other people working at that point and that breakthrough inquiry as well I do have colleagues who are doing work similar to what you're doing oh yeah certainly and so this is really so this particular topic of research that we have been describing it's a massive collaborative effort but massive right what is massive and what is not massive again that is a relative term but at least in the computer context of computer science which is a very young field this does qualify as a fairly large project which started in early 90s and it is now going on for 30 years with many many prominent researchers making contributions and for me one of their actually nicest developments is my adviser Sanjeev Arora he was one of the founding founders of this field and well I guess I have been working on this for about 20 years now and in the last three years as I alluded to mentioned before we did make a significant progress me and my coauthors we didn't make a significant progress on arguably the most central question in on this topic the unique games conjecture and this is again a collaborative effort quarters Melissa like in Dunedin or from Israel and and kind of remarkably a student dorm in said he's a student of Tel Aviv University so he's formally not my student but I guess effectively or for all practical purposes he's my student and for me it's it's super nice that my advisor started something I continued for many many years and now my student or he's now at the forefront of it and then it's it's it's a nice experience and the point where you have the expectation so young life a lot of work in this field and a lot more development you see and perhaps it's unnecessary say already a direction the
37:32
next step the next phase of inquiry that you will address well there are certainly directions right there are always directions and the important thing is to have a direction with very difficult ball at the end of it and irrespective of any in some sense bias of optimism or pessimism just keep working towards it and see right let's see what happens thank you
38:23
you