The HLF Portraits: Avi Wigderson
Formal Metadata
Title 
The HLF Portraits: Avi Wigderson

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
Nevanlinna theory
Musical ensemble
Family
00:31
Existence
Multiplication sign
Decision theory
Direction (geometry)
Mereology
Graph coloring
Wave packet
Mathematics
Manysorted logic
Thermodynamisches System
Term (mathematics)
Different (Kate Ryan album)
Natural number
Energy level
5 (number)
Condition number
Social class
Process (computing)
Forcing (mathematics)
Neighbourhood (graph theory)
Computability
Numerical analysis
Connected space
Order (biology)
Family
Directed graph
06:39
Point (geometry)
Geometry
Axiom of choice
Computer programming
Polynomial
Complex (psychology)
Observational study
State of matter
Multiplication sign
Decision theory
Characteristic polynomial
1 (number)
Insertion loss
Student's ttest
Mereology
Theory
Subset
Hypothesis
Fraction (mathematics)
Mathematics
Goodness of fit
Thermodynamisches System
Manysorted logic
Different (Kate Ryan album)
Term (mathematics)
Energy level
Körper <Algebra>
Series (mathematics)
Computability theory
Set theory
Social class
Area
Process (computing)
Constraint (mathematics)
Surface
Computability
Mathematical analysis
Bound state
Algebraic structure
Line (geometry)
Cartesian coordinate system
Connected space
Degree (graph theory)
Universe (mathematics)
Mathematician
Family
Resultant
22:09
Ocean current
Statistical hypothesis testing
Standard error
Randomization
Existence
Observational study
Multiplication sign
Dichotomy
Student's ttest
Prime number
Rule of inference
Food energy
Theory
Integer factorization
Product (business)
Power (physics)
Element (mathematics)
Prime ideal
Gaussian elimination
Mathematics
Goodness of fit
Manysorted logic
Thermodynamisches System
Natural number
Term (mathematics)
Theorem
Randomized algorithm
Körper <Algebra>
Determinant
Extension (kinesiology)
Set theory
Hydraulic jump
Physical system
Process (computing)
Physical law
Model theory
Moment (mathematics)
Computability
Physicalism
Basis <Mathematik>
Cartesian coordinate system
Axiom
Numerical analysis
Proof theory
Arithmetic mean
Right angle
Game theory
Mathematician
37:38
Potenz <Mathematik>
Existence
Observational study
Model theory
Proof theory
Frequency
Field extension
Mathematics
Manysorted logic
Natural number
Right angle
Körper <Algebra>
Resultant
00:00
[Music] you professor I'd like to begin with the family into which you were born but I hope you can call me a V because everybody does Adi yeah tell me about the family to which both my parents are Holocaust
00:33
survivors and among the very few of their families that survived domestic Israel and my father was an electrical engineer I was was Navy my mother was a nurse about time we grew up me and my two brothers in a in a tiny apartment in a bluecollar neighborhood on the beach were exhausted to the beach in you know in  so an urban environment it's I don't know exactly it's sort of it's very different than you know when I don't get it now than when I purchased it as a as a kid yeah the child it was heaven heaven yeah because you may never remember is it public till the age of 15 are the only thing I did this was either on the beach or play soccer and that's the only two activities we were engaged in under I mean most kids and yeah it's it's a small level this was not part of an elephant thing you needed to get out take a bus or something in order to so are you to use an awful word a nerd I figured the opposite of in there I was definitely a nerd here even though I the beachbum life I was definitely stuck out as a source of anger yeah I liked studying I mean this was not so common no no no it's no
02:16
no my father was a you know sort of in different conditions he would have been an intellectual in different conditions it would have been maybe and academic I don't know it's very hard to say but I mean he was just forced to find a job when he arrived and then they had their family and he supported it and actually yeah is it a house full of books no no no it's there were books definitely he liked leading against was a mess of time available my my mother less so he was he was definitely interested in in puzzles is his job was sort of puzzle solving more or less in in at least the way he always explained it to mean fixing you know the engines of large boats where something goes wrong I mean finding out what's wrong I mean that was a intellectual puzzles which tests to make and so on it's something I can relate to in fact he he got me I'm sure he got me interested in lots of the I would say the the art of the magic of solving problems and it definitely gave me Russian books that he had that had the puzzles in them or mathematical oh yeah definitely that's the earliest memories of connection to math I remember and we speak of your parents ambitions for you as I don't know in terms of ambition success be they were happy with our yeah I don't I don't remember any force was pushing us in any directions are happy with our achievements and so in this neighborhood blue color in your taifa what is the quality of education in the local school pretty low very low yeah so for my high school the one thing they did with because also my teacher recommended teachers recommended is that I go to a high school you know high fives more or less layer of economically accorded sunny mountains with a beautiful by the beaches Louis there was a high school it's a famous high school in fact they are early high school in Haifa which it was a semiprivate thing that also was a rare thing in Israel still arising in Israel and was a good high school relatively speaking so you know it was good in nature there were some excellent teachers in particular and the math teacher who just came from Russia at the last three years of high school and he was phenomenal was he also because I've spoken to a number of your colleagues in mathematics and computers who were trained in the Soviet Union or the school and the teaching and mathematics was very rigorous it was really this was the kind of training it was not just service it was also it was but also inspiring I mean he was just you know he's his love his passion for mathematics he wrote textbooks in Russia which I had copy or copies of even though I Koons really taught me some but he gave extra you know extra curricular classes beyond the you know so some of us took these and learn about some you know some college mysterious but she remember his name dear Kaplan yeah you are how old when you first meet him as a teacher you know junior and since I was 17 in the Israeli system or at least in this school when do you have to decide on a direction is what is it decided for you by just know it's you decide everything yourself for you oh yeah I mean you consult with friends and family but in Israel you don't do this decision in high school because after high school you go to the army so so you know you are going for three years of intellectual less existence most people some people do there are some interesting jobs in the army yeah so so you don't make any decisions
06:39
there you make decisions when you are 21 you're leaving the army and then you think what you want to do although and I don't know but I know that something about the fact that many get their introduction to computers and the ability to work with them in the army did that happen to you no it happens a lot more nowadays not when my time with computers were young yeah there are there's some subset of people that many of them do find themselves later in academia who go either to you know what with computers although some mathematically related work maybe in intelligence or some yes but just was no definitely not my case I went for a year for the flying course and then I was kicked out because I didn't fly well enough and yeah then I was in its process so so the pilot I don't know what yeah I don't believe in this kind of thing anyway so you completed your army yeah and you are certainly set on going to university yeah it was natural because I was loved study and it was clear that I'll continue studying at the time we are a relatively small fraction in Israel went to college I mean college I mean I was in America I became like sort of the grill master but anyway yeah I definitely wanted to learn and I want to study mathematics and my parents thought that maybe I should try to be the size because I learn mathematics anyway there and maybe I'll also have a job when I graduate so right so I went yes and it was a great decision I must say because I fell into this wonderful line so let me see you were born in 56 we are now seven in the 70s 70s yes there were 77 I went to college 77 and you went to the Hebrew University no no I went to the texts name take the okay technical what a high level of technology do you feel okay at this point what is the state of computer science do they have a department of computers things are just created it was very young we had a class of 40 students there was a phenomenal class many of them are colleagues today are in academia in the US and in Israel yeah and we had phenomenal teachers they're very inspiring ones and the ones I tend to you know connect more to all the theoreticians right so were they apparent at that point I mean I know there's a time when so many people think of computers at this era as programming as opposed to the broader theory and mathematics of it at Technion are they already aware and emphasizing the theory yes and I should probably tell you about the big difference because baby you interviewed there mainly American computer scientists theory in Israel was within computer science was always you know a bigger part highly valued and the reason is that in Israel computer science support for mathematics named like you know microwave in Mill Valley Oh Alicia Miller and many other human Haven who was my teacher at the Technion the year they studied mathematics they're all mathematicians who realize this you know new world and they came from a tradition of mathematics and they wanted to create foundations of course a well coefficient grant theoreticians feel but in the u.s. computer science evolved mainly from engineering yes when I came to Princeton for my PhD it was in an engineering Electrical Engineering Department was not yet a separate department but anyway most of the United States could be a science apart from engineering traditions and their while theoreticians you know existed a religion or is essential for the development of the field it was not the same so why I asked maybe is so the question about intellectual snobbery was it didn't require a leap of imagination for mathematicians to say now I will devote time to computers wasn't this a kind of degradation of pure analysis in their minds well yeah I don't know about other people exactly how they work with this doing work which I mean inserting qualifications like is it more supremo more yeah I don't you know I don't see any serious mathematicians think about what they are going to work on in these terms of course you may know some a tonne or maybe I do know this aspect I'm sure that they I don't think it was an issue I think that the the enormous intellectual challenges in understanding loss computation is which we are still facing today were clear to some of them and I think that's the reason they chose to do foundations of computer science or the theory of computation yes you find a particular mentor Technion the the one that inspired me the most was shim 11i I took several crosses from him it was mainly algorithms and yeah but definitely my main influence they are together Co closest and yeah and it appealed to me very much to to study on I mean at the time because I came from a family that's not academic I didn't even know it was the Technion the earth that it was a profession to be a yes professor but I definitely wanted to continue studying and he encouraged me to apply to universities in the US and at the time some of my classmates also did the same for other things to do I understand sometimes the role of the mentor the guide if you will the intellectual guide is to present problems to a promising students young student was his doneforyou a Technion were your sentence agree we have just no there was no special special relationship it was just that the environment I was in the other students and these very good courses that just proposed not ever I didn't do any resource problems if that's what you mean there was no we learned and they were challenging you know problems and I had no idea what research was until I got into graduate school I have no idea I knew I wanted to learn more that's all I know I didn't know about this profession and I didn't know academic you weren't required to do a thesis no no you don't do a thesis Lee undergraduate degree okay we just learned there and so now you go into the Uncharted world of academic preparation you you you research universities in fields that interest you know I mean it's amazing because I do talk to students nowadays and it was completely naive we knew who you know what's the best universities are I applied to about
14:25
none of them I was admitted with the fellowship which brother of course is essential for me to live only at Princeton at Yale and yet and I asked Shimon have been about and he said that you know in theories are more or less equivalent which were both it was not whether one of the best at the time in theoretical computer science now it's a major powerhouse here but I said they are roughly the same but Princeton is so much nicer place so you know that's my accommodation another person I interviewed in the series who was Indian thought that he was Harry Potter when you write the president from India it's a really nice very relaxed it's of course yeah yeah we also my wife and I just married we met at the Technion so we came here together and she went to what girls so so now graduate study I don't say now you get serious who have been serious alone but now you must specialize or frame the next stage of your career how did you do this yeah I never I never made any such decisions consciously I don't know maybe some people do but I came here and I took some courses and there are only two theoreticians at Princeton at the time can Stiglitz we did optimization and and decrypt on who did more complexity geo attic stuf which who he became my advisor so this attracted me more and you know he was he's a man of in a maze increate ivities and broad interests so he he was there with which research areas like so he moved between areas and I just moved with him I learned about various things he was ask me questions about many of these areas and I also became interested in lots of things so it's I never thought he think of my surface working in one particular area I maybe I got the bug off of being interested in well theoretical so mathematical questions about computing and that's a very very bored so one day you will be in an institute where you can do and think about anything but as a graduate student at least in my experience the structure of the degree requires you to frame either a specialty or certainly move toward a thesis so where are you here no no that's different theory theory is that chunk are in computer science is so bored even at the time the programming languages and I know software engineering and as compilers and some hardware and networks even you know they didn't exist much anyway people were doing different data structures that are databases yeah you chose one of these I chose theory this was clear to me that I was to stay close to mathematics and do and that's the only choice this is the only you I felt that there was no constraint even them you did what you liked and that was the you know you've told your advisor and then would you you can choose but you also require preparation did you find that your mathematical preparation was sufficient for your needs in computer never it was never sufficient because I was a student of computer science also of the Technion so I have to learn mathematics all my life and this is great too but yeah it I could have been in terms if I had I known as I mean more conscious I would take an undergraduate degree and probably a graduate degree in mathematics theory of computation has become much more sophisticated mathematically with time and requires more and more deeper and wider mathematics so the connections are extremely you know interesting and bored so yes since I didn't have this background lots of if I had to do later which is rania again it may be too too broad a question but we are now in the late 70s early Earth revealer 82 83 okay is it possible to give me a kind of snapshot of the state of computer theory at this point what is it like what what are the questions being asked okay so yeah there's a absolutely amazing time because first in the 70s to two major things happen in the 70s one after the other one was the framing of the the question of p.m. NP which is the most or the biggest question I can explain it's an acceptable just I want to say what the two things are so this is a basic computation of complexity questions which natural things we cannot solve and which we can and this was framed in mathematically in the 70s and soon after I'm very related to this was a framework for complexity based cryptography which is you know I can explain so people understood already since during time that there are certain computational tasks that cannot be performed they're just impossible to perform this in particular debugging programs is impossible so that was very nice beginnings to the field and then I people realized that the definition that can be solved is 2 lakhs it's just solved in finite time is not enough we need to see the results tomorrow so people started to investigate time bounds and in general complexity bounds on programs on algorithms and wanted to be wanted them to be really quickly so this complexity theory was initiated in the 60s and in the 70s both in the US and in Russia people understood that there is a particular class of problems that are extremely natural we can hope to solve them quickly solve them quickly we call P for polynomial time but doesn't matter there's a class we knew how to solve and this is what more or less related to having computers do it fastest via reticle but this is related to efficiently real efficiency in the real world all the applications you see there are programs that are India problem certainty and there's a bunch of a larger set of questions that is called the NP whose characteristic is that like maybe a crossword puzzle or Sudoku you know or maybe an engineering task these are things that it's very easy to recognize a good solution when you see one but maybe finding one solving such a year of times maybe how but if I give you the service so anyway that's empty that's a class of problems that where our solutions can be easily recognized as good quickly recognize it's good but there are cells problem so
22:13
you know can you solve all of these this characterized more or less all the people all the problems that people are looking at in almost all of them a solution I found is recognized as good in particular mathematical theorems of this nature right I mean maybe it's difficult to pull some of them as they hang but in most cases somebody proves the theorem then most mathematicians maybe with some background can verify that this is a good example so if P equals NP in our language then you don't need mathematicians right you can automate all of this this is the biggest service since the 70s that's the biggest question which still open it's one of the clay problems it's one of the major problems in mathematics as well but the idea that some problems of this nature are difficult or maybe difficult acceptable or not yeah they cannot be solved quickly they will have today you know all all these problems have both four solutions you know the proof of the theorem will take a hundred pages let's try all hundred pages manuscripts one of them would let's run through them all this is the only type of algorithm we know for general problems in NP so far so but the idea that there may be problems of this nature that are hard another set of people started with Diffie and Hellman and then how a say the rest a million Adelman and walrus and Macaulay to develop a theory of cryptography which is based on the idea that you know what what is hiding a secret is a computational difficulty of a problem this is this and this idea which is amazing in itself is what is what really you know cause the internet will be built right suddenly with this idea you could have people who never talked with each other before communicate in secrecy I think people don't realize so much the fact that you know cryptography before that in the let's say 3000 theater it existed was secret communication between people based on the fact that they had secret communication before so life emesis so in some sense you know James Bond has to meet with them before this allowed the situation that you and I have never met before or Amazon and I have never met before I can barely send them my credit card number even though we didn't agree on a secret book and secret page and secrets yeah so it's all based you know again something that I can explain but it's based on computational difficulty of certain problems in NP that people imagined like integer factoring people imagine me it may be difficult and all hope it becomes a benefit exactly which is extremely rare thing it's good to have heart problems it's a it's amazing shocking surprising and there are other aspects of this there are other benefits of how problem that it merits in the history of computation with health problems you can build good through the random generator so that's another very important aspect of the you know jumping I'm jumping like is the biggest feast of my life which is still continuing it's extremely rich and lively with with people with amazing talent especially creative people cryptography as the times mideighties I went to Berkeley on a postdoc and I did a little of my PhD but went to Berkeley as a postdoc and this was sort of the hubble place well most of the ideas and some of the people you know resided or world other students a blonde and gravis McCauley and and the owl and so on and yeah that was just it was like playing amazing games can you do this impossible task so in cryptography until that time you know secret communication was the main major thing you had to do the major problem to to solve but now you wanted to solve all sorts of people can we exchange secrets can we play poker over the telephone can we you know can we zero knowledge issue can we can I prove to you something it's sort of the antithesis of mathematics right usually you know mathematical proof you would like not only to have a correct proof and know that the theorem is correct but also understand what's going on I mean the post should be revealing should be on the other hand in cryptography often you want to prove to the other party something but specifically only that thing let's say that you know that the secret number you chose is a product of two primes but you are not willing to reveal which two because this will violate you yeah so so the question that was asked was is it possible to prove theorems without providing the listener or the student or whoever your colleague any absolutely no detail about the proof except it's that your proof is correct so this is beyond radical in terms of at least mathematical thinking it's just it's a very weird concept but what you have to get used to in this world of cryptography is that the computational difficulty is just like we said changes the rules in some sense I mean it's it's it's a wonderful axiom first of all it seems to hold in real life the axiom that some problems are difficult and once you accept this axiom was it you know some problems are extremely hard and we are computational limited then suddenly you can do you can do this magical thing so one of the no hobby um the jump into this what is going to be and what becomes your contribution ongoing contribution to this discourse yeah there are lots of subjects yeah so at the time when I was a postdoc we did this so we pulled that every theorem can be proved in what we call zero knowledge so this is sort of yeah definitely highlight I'm interested in yeah another is the power of randomness so understanding you know there are lots of one one thing that developed at the time again that was extremely powerful is the use of current offices in algorithms that you know solving problems that we didn't know we didn't have any means of solving in a deterministic fashion using randomness to solve them this was not a new idea a Monte Carlo simulations existed in the 50s Gulam for Neyman and so on but just just sort of the wealth of applications the wealth of problems people were trying to solve once computers existed many were you know hit a brick wall unless you use you know randomness and so the obvious theoretical question is
29:54
this just because we are too stupid to find the deterministic algorithm it's always better to have something that's totally predictable and you know you know is totally correct always with with when you're applying randomness is always some chance of small chance of errors and very unlikely event with with which you produce the wrong answer this is accepted but you know it will be nicer if if you could avoid it so this is a great challenge that I worked on for for 30 years I mean lots of mine understand is in advance being the tolerance for randomness or the recognition of it is a problem that must be solved no I'm talking about the fact that okay first of all even today lots of problems are telling that they are solved on a daily basis I was sold using a probabilistic algorithm why because either it's the only one we have or it's more efficient than the counterpart a deterministic counterpart that's a fact in all these algorithms there is a tiny chance of error okay so a good example from that time it's a climb allottee testing testing whether a number is prime or not at the termination algorithm which is service law was discovered in the early 2000s but for 30 years and this was important for cryptography because you need prime numbers so we have these algorithms that were fast and deliver the answer correctly with 99.99% probability as high as you want but not a hundred percent so you should ask yourself I mean you know suppose it gives the security of your system of your electronic commerce environment dependent on the correctness of this assumption that the number you are holding which is very long is a prime can you achieve it deterministically this you can ask about every algorithm that is there so that was a challenge can we eliminate randomness from algorithms that was the question and we know the answer is it's a bit complicated and related to the P versus NP question which is another surprise so we know roughly the following I'm oversimplifying but if an assumption very similar to be different than NP namely just the assumption that some problems are exponentially hard some natural problems are especially hard problems we believe are expensive if just holes then you can replace every determining every probabilistic algorithm with a determinant counterpart so you can eliminate run randomness always so health problems are useful in a very different way yes yes yeah so if the interview were longer I would get you through your career but of course you you do a number of you go to a number of places and in the end you wind up back in Princeton which is a kind of intellectual home for you yes it's definitely one of one I would just see I mean the main places I was at is here directly and the Hebrew University in Jerusalem I spent 15 years Oh 15 years is worth at least spending a bit of time with in a sense of how did you find the nature of the discourse is discourse so globally framed now in your field that being in the Hebrew University not in the United States with other is not an issue or are there different emphases in the various academic environment I would say that it's really global everybody is aware of what everybody is doing but still you know you all call it's an environment matter and I had fantastic fantastic quality fantastic students which from I learned a lot I mean I love all the time for all the young people I collaborate with that it was students graduate students at the Hebrew University as postdocs because we don't have students but it was a phenomenal environment very enriching has a very good math department and yeah it was it was a great place to be so you might've stayed if not for the great the opportunity that the Institute yeah it's an opportunity that we decided to test and my wife is also working here in the computer center so we both got offers at the same time and we came here as a trial you know decided to give ourselves a couple of years and relax it's always thing at the end of the interview I want to at least touch on the fact that at this very moment you're about to come out with a book of it's essentially out yeah it's out brings together so much of what you have looked into is it possible to explain briefly what the book aims to do the book the book to explain just things understand well I think I understand well in the way that I like to explain it it is called mathematics and computation it's about this field that I met in which which is it's sort of an interesting dichotomy and people keep asking me whether I'm a mathematician or a computer scientist and I am both but it's sort of an interesting existence because the two traditions you know the sort of technological tradition the mathematical traditions are very different the technological side is great because keep generating you know the new technologies new models new things for new things to model new problems new algorithmic challenges new whatever but it's also demanding in terms of you know what it's like to produce it it lacks applications with on all the other hand this community operates as a mathematical community at least in the extent that it builds formal models poor widow as theorems this is the discourse of the of the field I think it's great has been great for the fields I'm just explaining lots of facets of this field in the book and at the very end I tried to explain more globally why this way of thinking the viewing processes in general not just computed processes this is something that's been happening the last two or three decades the interactions of my filled with energy economics physics you name it Social Sciences is sort of revolutionizing these fields in many of them and in many studies of us aspects of various processes in nature let's say Oh in the human or in the you know disease or everything the computational element of the understanding of resources it's going to processes I would say was lacking and there are many
37:40
many collaborations in which you know this is exposed and this is enriching both us and the sciences so there are lots more happening and I talk about that most of the book is about various fields of I mean it's a big field sort of aims in particular to explain how big the field is what other major subfields and what are the major problems are interested in both of the major results and there are no proofs in there and in a way you're very lucky in your life period because your study to participation is during this burst of exponential growth I'm extremely lucky I consider myself unbelievably lucky to live in this you know and exactly this age whether it's a young field it's the young field that may be partly accounts for your lack of you know maybe most traditional fields our more conservative it's a very democratic field it's a very friendly field so feels a very collaborative with so small nature I like to work work with people and definitely it's bursting with intellectual problems and challenges and modelling problems that are not so I mean people associate somehow modelling questions in mathematics more with applied math where you try to model by but here modeling these as important despoiling cioran's just finding the right definitions let's say in cryptography is a very good example but there are many just finally the right definitions is you know just try to define what is zero knowledge puffeth is a major is a major issue in itself anyway so I consider myself unbelievably lucky it's a very fantastic existence thank you okay thanks
39:55
you
39:59
you