Avi Wigderson responds to yesterday's post.
20 years is a long time, and TCS is in a completely different place today than it was then.
I am happy to say that internally its members are far more confident of its importance and independence as a scientific discipline, and externally the recognition of that importance by all sciences (including computer science) has grown tremendously. I have no doubt that both will continue to grow, as will its impact on science and technology.
Let me address a few aspects of the original post (one can elaborate much more than I do here).
Young talent: The way we continuously draw exceptional young talent to our core questions is not just a fact to state - it carries important meaning, namely a key sign of our health and prosperity. After all, these exceptionally talented young people could have done well in any field in science and technology, and they freely chose us (and indeed have been responsible for the many great results of the field in the past 20 years)!
Funding levels: In contrast, funding levels are always controlled by few and are subject to political pressures. So here our field was wise to grow up politically and realize the importance of advocacy and PR besides just doing great research. This has definitely helped, as did other factors.
Growth of theory in academia: I have no idea of the exact statistics (or even how to measure it exactly) but I should note as an anecdote that as soon as Harvard got 12 new positions in CS it made three senior offers to theorists: Cynthia, Madhu and Boaz! I see it as an important critical development to have TCS well represented not only in the top 20 universities but in the top 100. Our educational mission is too important to be reserved only to the elite schools. (Needless to say, our science and way of thinking should be integrated to the K-12 educational system as well. While this is budding, significant meaningful presence will probably take decades.)
Scientific relevance: While it may be too early to evaluate the true impact of our (many) specific incursions into and collaborations with Biology, Economics, Physics, Mathematics, Social Science etc., I believe the following general statement. *The emerging centrality of the notion of algorithm, and the limits of its efficient utilization of relevant resources, is nothing short than a scientific revolution in the making.* We are playing a major role in that revolution. Some of the modeling and analysis techniques we have developed and continue to develop, and even more, the language we have created over the past half century to discuss, invent and understand processes, is the fuel and catalyst of this revolution. Eventually all scientists will speak this language, and the algorithmic way of thought will be an essential part of their upbringing and research.
Technological relevance: Even without going to great past achievements which are taken for granted and dominate technological products, and considering only current TCS work evidence is staggering. Sublinear algorithms, Linear solvers, Crypto (NC0-crypto, Homomorphic encryption,...), Privacy, Delegation, Distributed protocols, Network design, Verification tools, Quantum algorithms and error correction, and yes, machine learning and optimization as well, are constantly feeding technological progress. How much of it? Beyond counting patents, or direct implementations of conference papers, one should look at the integration of modeling and analysis techniques, ways of thinking, and the sheer impact of "proofs of concept" that may lead to drastically different implementations of that concept. Our part in the education we provide to future developers was, is and should be of central influence on technology.
In a tiny field like ours, having the impact we do on so many scientific and technological fields that are factors 10-100 larger than us may seem miraculous. Of course we know the main reason since Turing - we have universality on our side - algorithms are everywhere. What is perhaps more miraculous is the talent and willingness of pioneers in our field over decades to search, interact, learn and uncover the numerous forms of this universal need in diverse scientific and technological fields, and then suggest and study models using our language and tools. This has greatly enriched not only our connections and impact on other disciplines, but also had the same effect on our intrinsic challenges and mysteries, many of which remain widely open. I am happy to say that at least part of that remarkable young talent constantly drawn into our field keeps focus on these intrinsic challenges and the natural, purely intellectual pursuits they lead to. Our history proves that there are direct connections between the study and progress on core questions and our interactions with the outside world. Our current culture luckily embraces both!
All the above does not mean that we can't improve on various aspects, and constant questioning and discussion are welcome and fruitful. But I believe that a the firm foundation of these deliberations should be the intrinsic scientific importance of our mission, to understand the power, limits and properties of algorithms of all incarnations, shapes and forms, and the study of natural processes and intellectual concepts from this viewpoint. This importance does not depend on utility to other disciplines (it rather explains it), and should not seek justification from them. The correct analogy in my view is expecting theoretical physicists to seek similar confirmation in their quest to uncover the secrets of the universe.
Thanks Avi!
ReplyDeleteThere seems to some disagreement between Lance's
ReplyDelete"Rarely do the research in these papers affect real-world computing."
and Avi's
"[research fields] are constantly feeding technological progress."
So you think your job(s) cannot be endangered by the progress of AI?
ReplyDelete(like anyone else BTW)
Small disagreement regarding machine learning: theoretical computer science has not contributed much to machine learning. There is one or two ideas in machine learning that came from theoretical computer science and that is it. I would be really happy to be proven wrong on this. The reality is that machine learning researchers don't care about our work and see it of no use. During the last NIPS there were a few posters from theoretical computer scientists (one having Avi as a coauthor) among hundreds of posters and no one was paying any attention to them. That is how machine learning thinks about our work. Again I would be happy to be proven wrong on this.
ReplyDeleteAt least 2 of the ICML tutorials seem to be about FOCS/STOC style theory: http://icml.cc/2016/?page_id=97
DeleteI think this is misunderstanding of how the research in both ML and TCS works. Clearly, the vast majority of TCS research has no relevance to anything beyond TCS itself, even when nominally it is motivated by ML/AGT/distributed computation/crypto etc. By and large this is the nature of theoretical research. Also ideas that do end up influencing ML often go through several stages of digestion after which the original theory papers are not even cited. But TCS ideas, both big (like boosting, randomized linear algebra, LSH, submodular optimization, differential privacy) and small (too many to list) are everywhere in ML.
DeleteIn addition, TCS has spawned the COLT community which gradually transformed into a community at the intersection of TCS/ML/Stats/Optimization. This community has very strong interactions with ML research and is also influenced significantly by research in TCS.
not so long, in some places. In Finland, programming and algorithmic thinking will be taught since first grade starting next year...
ReplyDeleteI can think of two immediate TCS results relevant to machine learning. Shapire's boosting and Rivest and Blum's NP completeness result for neural net convergence.
ReplyDeleteNice try including Schapire's boosting as part of TCS!
DeleteI think all those bragging about TCS' contributions should try to compare it to ML's contribution.
@Anonymous, ML has lots of applications but I don't think it has contributed much to other fields. It is like saying that C++ has contributed a lot to computer science because it is use by so many. If we go the same way we can claim that theory has contributed a lot to other areas because they simply use our algorithms whether it is in ML or other fields. But I think that is not what we are talking about here.
DeleteCan you give some major contributions of ML to other areas in computer science? Not just black box usage, but ideas that have lead to major advances in other areas?
The original boosting paper, in FOCS 89: https://www.computer.org/csdl/proceedings/focs/1989/1982/00/063451.pdf
DeleteML is the bread and butter in computer vision, NLP, speech recognition, etc. etc. It is ridiculous to compare ML to C++. ML is a research discipline, mainly consisting of algorithms of a certain kind. How do you even compare it to C++? But the true success of ML is in the applications. Almost the entirety of web search is now ML. Self driving cars are ML. ML has had a much greater impact on other fields like economics, and other sciences such as medicine even, much more than theory has had. I can go on and on and on. The black box usage that you seem to deride is essentially what theory aspired to be (or should have aspired to be) and which ML actually managed.
ReplyDeleteApplications are important. Every time someone uses a sort algorithm theory can claim credit for its black box usage. Sort just is a simple example, there are many other algorithms that theoreticians have come up.
DeleteUsing a tool as a black box to make progress in a field is not the same as contributing to the field. If we are going to say that the work done by ML researchers have been helpful in other fields that is fine, theory can also claim the same thing. But that is not the same as contributing to other fields. I see ML as a black box as a tool and there is no reason one should think that this tool is somehow above others. The tools are exciting when they first become available to outside masses and that is what is happening in ML. Same thing has happened in theory decades earlier with algorithms and data structures. In a decade or so ML as a black box will be as exciting as sorting as black box.
It is not ridiculous to compare a programming language to black box usage of ML. Try doing ML in assembly if you don't believe that these high level programming languages are essentially for the work. But no one claims that they are contributing to other fields. They are tools that researchers in other fields use to make progress.
So I ask again: can you give some examples of ideas from ML that have contributed to progress in other fields excluding ML black box usage?
People like Avi have cemented TCS's position as an important scientific discipline, and not just an offbeat of Engineering. It is amazing to see how TCS has dealt with deep fundamental questions.
ReplyDelete