Alan Turing Centennial

Eric Schmidt: watch video

Since joining Google in 2001, Eric Schmidt has helped grow the company from a Silicon Valley startup to a global leader in technology. As executive chairman, he is responsible for the external matters of Google: building partnerships and broader business relationships, government outreach and technology thought leadership, as well as advising the CEO and senior leadership on business and policy issues.

From 2001-2011, Eric served as Google’s chief executive officer, overseeing the company’s technical and business strategy alongside founders Sergey Brin and Larry Page. Under his leadership, Google dramatically scaled its infrastructure and diversified its product offerings while maintaining a strong culture of innovation.

Prior to joining Google, Eric was the chairman and CEO of Novell and chief technology officer at Sun Microsystems, Inc. Previously, he served on the research staff at Xerox Palo Alto Research Center (PARC), Bell Laboratories and Zilog. He holds a bachelor’s degree in electrical engineering from Princeton University as well as a master’s degree and Ph.D. in computer science from the University of California, Berkeley.

Eric is a member of the President’s Council of Advisors on Science and Technology and the Prime Minister’s Advisory Council in the U.K. He was elected to the National Academy of Engineering in 2006 and inducted into the American Academy of Arts and Sciences as a fellow in 2007. He also chairs the board of the New America Foundation, and since 2008 has been a trustee of the Institute for Advanced Study in Princeton, New Jersey.

Eugene Higgins Professor of Computer Science
Chair, Department of Computer Science
Princeton University

Title: Models of Computation and Systems of Logic: Turing, Gödel, and Church at Princeton in the 1930s

Abstract: Between inventing the concept of a universal computer in 1936 and breaking the Enigma code 1939-45, Turing came to Princeton University to study mathematical logic. Some of the greatest logicians in the world--including Alonzo Church, Kurt Gödel, John von Neumann, and Stephen Kleene--were at Princeton in the 1930s, and they were working on ideas that would lay the groundwork for what would become Computer Science. Turing's 1938 Princeton PhD thesis, "Systems of Logic Based on Ordinals," which includes his notion of an oracle machine, has had a lasting influence on computer science and mathematics.
A work of philosophy as well as mathematics, Turing's thesis envisions a practical goal--a logical system to formalize mathematical proofs so they can be checked mechanically. By now, Turing's vision of "constructive systems of logic for practical use" has become reality: in the twenty-first century, automated formal methods are now routine.

Bio: Andrew W. Appel is Eugene Higgins Professor and Chairman of the Department of Computer Science at Princeton University. He is a member of Princeton's Center for Information Technology Policy. His research is in computer security, programming languages and compilers, automated theorem proving, and technology policy. He received his A.B. summa cum laude in physics from Princeton in 1981, and his PhD in computer science from Carnegie Mellon University in 1985. He has been Editor in Chief of ACM Transactions on Programming Languages and Systems and is a Fellow of the ACM (Association for Computing Machinery).
 

Princeton University President Shirley M. Tilghman gave welcoming remarks to those attending Princeton's Turing Centennial Celebration. 

Professor Emeritus, New York University

Title: Universality is Ubiquitous

Abstract: The work of Turing, Post, Church, Gödel, and Kleene during the 1930s fundamentally altered our notion of the nature of computation. I will discuss this in terms of the theoretical underpinnings of the development of all-purpose computers and of modern computer science. I will go on to speculate about the role of computation in the human mind and in biological evolution.

Bio: Martin David Davis, Professor Emeritus at New York University, received his Ph.D. from Princeton University in 1950 under Alonzo Church. He is known for his work on Hilbert's tenth problem and for his model of Post–Turing machines. He is the co-inventor of the Davis-Putnam and the DPLL algorithms. He is a co-author, with Ron Sigal and Elaine J. Weyuker, of Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science, a textbook on the theory of computability.

RSA Professor of Electrical Engineering and Computer Science
Department of Electrical Engineering and Computer Science
MIT and the Weizman Institute

Title: Pseudo Deterministic Algorithms

Abstract: We will present a new type of probabilistic algorithm, which we call Bellagio algorithms. These algorithms are pseudo-deterministic: they cannot be distinguished from deterministic algorithms by a probabilistic polynomial time observer with black box access.
We will show a necessary and sufficient condition for the existence of a
such an algorithm for an NP relation, and several examples of Bellagio algorithms
which improve on deterministic solutions.
The notion of pseudo-deterministic computations extends beyond sequential polynomial time
algorithms, to other domains where the use of randomization is essential such as distributed algorithms and sub-linear algorithms. We will discuss several such domains.

Bio: Shafi Goldwasser is the RSA Professor of Electrical Engineering and Computer Science at Massachusetts Institute of Technology, and of computer science and applied mathematics at Weizmann Institute of Science in Israel. She is a co-leader of the cryptography and information security group and a member of the complexity theory group within the Theory of Computation Group and the Laboratory for Computer Science.

The William Sussman Professorial Chair
Dept. of Computer Science and Applied Mathematics
The Weizmann Institute of Science

Title: Standing on the Shoulders of a Giant: One Person’s Experience of Turing’s Impact

Abstract: The talk will briefly describe three of Turing’s major achievements, in three different fields: computability, biological modeling and artificial intelligence. Interspersed with this, I will explain how each of them directly motivated and inspired me to work on a number of topics over a period of 30 years, the results of which can all be viewed humbly as extensions and generalizations of Turing’s pioneering and ingenious insights.

Bio: Prof. David Harel has been at the Weizmann Institute of Science since 1980, and served as Dean of the Faculty of Math & CS. He has worked in logic and computability, software and systems engineering and modeling biological systems. He invented Statecharts and co-invented Live Sequence Charts. Among his books are “Algorithmics: The Spirit of Computing” and “Computers Ltd.: What They Really Can't Do”. His awards include the ACM Karlstrom Outstanding Educator Award, the Israel Prize, the ACM Software System Award, and four honorary degrees. He is a Fellow of ACM, IEEE and AAAS, and a member of the Academia Europaea and the Israel Academy of Sciences.

Chairman, CEO, and President
Corporation for National Research Initiatives

Title: A Systems Approach to Managing Distributed Information

Abstract: An individual or organization can structure and make use of its information in any way it desires as long as it doesn’t have to be shared with others. More general access to distributed information requires that multiple independent systems adhere to a minimum set of standards or conventions to facilitate more widespread use of their information. Such systems will need to evolve and still continue to interoperate for years into the future despite many generational changes in technology. Mobile and interactive digital objects will have an important role to play along with the use of resolvable identifiers.

Bio: Robert E. Kahn is President of the Corporation for National Research Initiatives (CNRI), a not-for-profit organization founded in 1986 to provide leadership and funding for research and development of the National Information Infrastructure.

Dr. Kahn received a Ph.D. degree from Princeton University in 1964. Prior to completing his Ph.D degree he briefly worked on the technical staff at Bell Laboratories and subsequently joined the Electrical Engineering faculty at MIT. While at Bolt Beranek and Newman, on a leave of absence from MIT, he was responsible for the system design of the Arpanet, the first packet-switched computer network. He later joined DARPA, where he initiated the Strategic Computing Program, and conceived the idea of open-architecture networking. He is a co-inventor of the TCP/IP protocols and was responsible for originating DARPA's Internet Program. In his more recent work, Dr. Kahn has been developing the concept of a “digital object architecture” as a framework for interoperability of heterogeneous information systems.

Dr. Kahn is a member of the National Academy of Engineering, a Fellow of the IEEE, a Fellow of AAAI, a Fellow of ACM, a Fellow of the Computer History Museum and an inductee in the Inventors Hall of Fame. He is the recipient of numerous awards including, the National Medal of Technology, the Charles Stark Draper Prize, the A. M. Turing Award, the Japan Prize and the Presidential Medal of Freedom. Dr. Kahn holds numerous honorary degrees including one from Princeton University in 1998.

University Professor
Department of Electrical Engineering and Computer Sciences with additional appointments in Mathematics, Bioengineering and Operations Research
University of California at Berkeley

Title: Theory of Computation as an Enabling Tool for the Sciences

Abstract: Researchers in the theory of computation are increasingly adopting a computational worldview that is radiating out to a wide circle of scientific and technological fields, recognizing that central phenomena of these fields are often computational in nature. Over the past decade we have applied this viewpoint to physics, molecular biology and economics. Connections are also developing to evolutionary biology, machine learning, social choice, social network analysis, nanotechnology, cognitive science and astronomy. To maximize the effectiveness of this outreach to the sciences, the theory of computation must join forces with the fields of massive data analysis and combinatorial optimization.

Bio: Richard M. Karp was born in Boston, Massachusetts on January 3, 1935. He received his Ph.D.from Harvard University in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department at IBM Research. From 1968 to 1994 and from 1999 to the present he has been a Professor at the University of California, Berkeley, where he held the Class of 1939 Chair and is currently a University Professor. From 1995 to 1999 he was a Professor at the University of Washington. From 1988 to 1995 and 1999 to the present he has been a Research Scientist at the International Computer Science Institute in Berkeley.

The unifying theme in Karp's work has been the study of combinatorial algorithms. His 1972 paper ``Reducibility Among Combinatorial Problems'' showed that many of the most commonly studied combinatorial problems are NP-complete, and hence likely to be intractable. His current activities center around algorithmic methods in molecular biology and genomics. He has supervised forty-two Ph.D. dissertations. His awards include the U.S. National Medal of Science, the Kyoto Prize, the Turing Award and ten honorary doctorates.

Frederick G. Storey Professor of Computer Science
School of Computer Science
Georgia Institute of Technology

Title: What Would Turing Be Doing Today?

Abstract: I will try to guess in what Alan Turing might be interested if he was around today. We will speculate on whether he would be working on this open problem or that one. And whether or not he could solve the problem, you know which I mean.

Bio: Dick Lipton received his undergraduate degree in mathematics from Case Western Reserve University in 1968. In 1973, he received his Ph.D. from Carnegie Mellon University. After graduating, Lipton taught at Yale 1973–1978, at Berkeley 1978–1980, and at Princeton 1980–2000 and since at Georgia Tech. At Princeton, Lipton was involved in the burgeoning field of DNA computing. He has been the chief consulting scientist at Telcordia since 1966. He is an ACM Fellow, a Guggenheim Fellow, and a member National Academy of Engineering (NAE).

Institute Professor
Department of Electrical Engineering and Computer Science
Massachusetts Institute of Technology

Title: Programming the Turing Machine

Abstract: Turing provided the basis for modern computer science. However there is a huge gap between a Turing machine and the kinds of applications we use today. This gap is bridged by programs, and designing and implementing large programs is a difficult task. The main way we have of keeping the complexity of software under control is to make use of abstraction and modularity. This talk will discuss how abstraction and modularity are used in the design of large programs, and how these concepts are supported in modern programming languages. It will also discuss what support is needed going forward.

Bio: Barbara Liskov is an Institute Professor at MIT and also Associate Provost for Faculty Equity. She is a member of the National Academy of Engineering, a fellow of the American Academy of Arts and Sciences, and a fellow of the ACM. She received the ACM Turing Award in 2009, the ACM SIGPLAN Programming Language Achievement Award in 2008, the IEEE Von Neumann medal in 2004, a lifetime achievement award from the Society of Women Engineers in 1996, and in 2003 was named one of the 50 most important women in science by Discover Magazine. Her research interests include distributed systems, replication algorithms to provide fault-tolerance, programming methodology, and programming languages. Her current research projects include Byzantine-fault-tolerant storage systems and online storage systems that provide confidentiality and integrity for the stored information.

E. Fredkin University Professor
Chair, Machine Learning Department
School of Computer Science
Carnegie Mellon University

Title: Never Ending Language Learning

Abstract: We describe our Never-Ending Language Learner (NELL) -- a computer program that runs 24 hours per day, forever, learning to read the web. Now two years old, NELL performs two tasks each day. First, it extracts (reads) more facts from the web. Second, it learns to read better than yesterday, enabling it to go back to the text it read yesterday, and extract more facts more accurately today.

Bio: Tom M. Mitchell is the E. Fredkin University Professor and founding head of the Machine Learning Department at Carnegie Mellon University. His research interests lie in machine learning, artificial intelligence, and cognitive neuroscience. Mitchell is a member of the U.S. National Academy of Engineering, and a Fellow of the American Association for the Advancement of Science (AAAS), and of the Association for the Advancement of Artificial Intelligence (AAAI).

Professor Emeritus of Mathematical Biology at the University of Oxford
Professor Emeritus of Applied Mathematics at the University of Washington
Senior Scholar at Princeton University

Title: Mathematical biology, past present and future: from animal coat patterns to brain tumours to saving marriages

Abstract: I shall briefly describe a reaction diffusion model which helped explain the diversity of animal coat patterns. I shall then describe a surprisingly informative model, currently used medically, for quantifying the growth of brain tumours and enhancing imaging techniques which is used to estimate patient life expectancy and explain a major reason why some patients live longer than others. Finally I shall describe an example from the social sciences, which quantifies marital interaction which is used to predict divorce and has helped design a new scientific marital therapy which is currently in practice.

Bio: Professor James D. Murray FRS, FRSE, Foreign Member of French Academy is Professor Emeritus of Mathematical Biology, University of Oxford, Professor Emeritus of Applied Mathematics, University of Washington and now Senior Scholar, Princeton University. Professor Murray’s research has been in a wide spectrum of areas, just a few of which are animal coat pattern formation, the spread and control of rabies, brain tumour growth and control, marital interaction and divorce prediction, the benefits of cannibalism, bovine tuberculosis, the mechanochemical theory of biological pattern formation, wound healing and justifying tribal warfare. He has published numerous research papers and books, including the well-known book Mathematical Biology.

Professor of Mathematics
University of Minnesota

Title: Turing and the Riemann zeta function

Abstract: Alan Turing was fascinated by the zeta function from his early days as a student. While it was not one of his major areas, he kept returning to it throughout his life. He was a pioneer in the design of a special purpose device to compute zeta zeros, and later in the first zeta computations on a general purpose digital computer, as well as in a clever method for verifying that all the zeros in a given range satisfy the Riemann Hypothesis. Interestingly, as his career advanced, his skepticism about the truth of the Riemann Hypothesis grew.

Bio: Andrew Odlyzko has had a long career in research and research management at Bell Labs, AT&T Labs, and most recently at the University of Minnesota, where he built an interdisciplinary research center, and is now a Professor in the School of Mathematics. He has published many technical papers in computational complexity, cryptography, number theory, combinatorics, coding theory, analysis, probability theory, and related fields. In recent years he has also been working in electronic commerce, economics of data networks, and economic history, especially on diffusion of technological innovation.

C. Lester Hogan Professor of EECS
Computer Science Division
University of California at Berkeley

Title: The Origin of Computable Numbers: A Tale of Two Classics

Abstract: Turing, like Darwin, transformed scientific and human culture through a singularly disruptive work written in a brilliantly self-conscious style. I shall recount the stories of these two classics, concluding with certain unexpected connections between computational ideas and evolution.

Bio: Christos H. Papadimitriou is C. Lester Hogan Professor of Computer Science at UC Berkeley. Before joining Berkeley in 1996 he taught at Harvard, MIT, Athens Polytechnic, Stanford, and UCSD. He has written five textbooks and many articles on algorithms and complexity, and their applications to optimization, databases, AI, economics, and the Internet. He holds a PhD from Princeton (1976), and honorary doctorates from ETH (Zurich), Athens Polytechnic, and the Universities of Macedonia, Athens, Cyprus, and Patras. He is a member of the Academy of Sciences of the US, the American Academy of Arts and Sciences, and the National Academy of Engineering, and a fellow of the ACM. His novel “Turing (a novel about computation)” was published by MIT Press in 2003, and his graphic novel "Logicomix" (with Apostolos Doxiadis) was translated in more than 20 languages.

Andrew and Erna Viterbi Professor of Electrical Engineering and Computer Science
Massachusetts Institute of Technology

Title: The Growth of Cryptography

Abstract: We give a broad overview of the growth of cryptography, placing Turing's contributions in a larger context. We emphasize modern developments, including the development of number-theoretic public-key methods such as RSA. We conclude with an overview of current active research questions in the field.

Bio: Professor Ronald L. Rivest is the Viterbi Professor of Computer Science in MIT's Department of Electrical Engineering and Computer Science and the Computer Science and Artificial Intelligence Laboratory. He is a recent ACM Turing Award winner (with Adi Shamir and Len Adleman), and a member of the National Academy of Engineering and the National Academy of Sciences. His recent research emphasizes the security of voting systems.

Emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic
Carnegie Mellon University

Title: Lambda Calculus, Then and Now

Abstract: A very fast development in the early 1930s following Hilbert's codification of Mathematical Logic led to the Incompleteness Theorems, Computable Functions, Undecidability Theorems, and the general formulation of Recursive Function Theory. The so-called Lambda Calculus played a key role. The history of these developments will be traced, and the much later place of Lambda Calculus in Mathematics and Programming-Language Theory will be outlined.

Bio: Dana Scott, a native of California, received his B.A. in Mathematics from U.C. Berkeley in 1954, and his Ph.D. in Mathematics from Princeton in 1958. He has been awarded honorary degrees at Utrecht, Darmstadt, Edinburgh, and Ljubljana. He has taught at the University of Chicago, U.C. Berkeley, Stanford, Amsterdam, Princeton, Oxford (U.K.), Carnegie Mellon, and Linz (Austria). He became Professor Emeritus in July of 2003. Over the years he has been supervisor of forty-two Ph.D. students.

He was a Bell Telephone Fellow, Miller Institute Fellow, Alfred P. Sloan Research Fellow, Guggenheim Foundation Fellow, Visiting Scientist at Xerox PARC, Visiting Professor at the Institut Mittag-Leffler, Sweden, and most recently a Humboldt Stiftung Senior Visiting Scientst, Munich, Germany.

He is a fellow of the Academia Europaea, American Association for the Advancement of Science, American Academy of Arts and Sciences, Association for Computing Machinery, British Academy, Finnish Academy of Sciences and Letters, New York Academy of Sciences, and U.S. National Academy of Sciences.

He received the LeRoy P. Steele Prize of the American Mathematical Society, the Turing Award (with Michael Rabin) of the Association for Computing Machinery, the Harold Pender Award, University of Pennsylvania, the Rolf Schock Prize in Logic and Philosophy, Royal Swedish Academy of Sciences, the Bolzano Medal for Merit in the Mathematical Sciences of the Czech Academy of Sciences, and the Gold Medal of the The Sobolev Institute of Mathematics, Novosibirsk, Russia.

James S. McDonnell Distinguished University Professor of Computer Science
Department of Computer Science
Princeton University

Title: Search Tree Mysteries

Abstract: The search tree is a classical and ubiquitous data structure, fundamental to databases and many other computer applications. The AVL tree, a type of balanced binary tree, was invented fifty years ago; since then, many different kinds of search trees have been described, analyzed, and used. Yet the design space is vast, and mysteries remain. This talk will describe recent work by the speaker and his colleagues that has produced a new framework for defining and analyzing balanced search trees, a new kind of balanced tree with especially nice properties, and a way to maintain balance by rebalancing only on insertion, not on deletion.

Bio: Robert E. Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University and a Senior Fellow at HP labs. His main research areas are the design and analysis of data structures and graph and network algorithms. He has also done work in computational complexity and security. He has held positions at Cornell University, U. C. Berkeley, Stanford University, NYU, Bell Laboratories, NEC, and InterTrust Technologies. He is a member of the National Academy of Sciences, the National Academy of Engineering, the American Philosophical Society, and the American Academy of Arts and Sciences. He was awarded the Nevanlinna Prize in Informatics in 1982 and the Turing Award in 1986.

T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics
School of Engineering and Applied Sciences
Harvard University

Title: Computer Science as a Natural Science

Abstract: Computer science can be approached as mathematics, as technology, and as a natural science. Turing's foundational contributions opened up all three of these avenues and his lasting imprint on them is still evident. The first two approaches may be the ones that have been most thoroughly explored to date, but this talk will argue that the last is at least as fundamental and was perhaps the one closest to the core of Turing's thinking. Turing's success in capturing the phenomenon of mechanical mental activity by means of the notion of computability sets the standard as a robust mathematical definition of a natural phenomenon. This talk will review more recent attempts to capture the phenomena of biological evolution, learning, and intelligence by means of definitions that seek to capture these various phenomena by analogously robust mathematical definitions.

Bio: Leslie Valiant was educated at King's College, Cambridge; Imperial College, London; and at Warwick University where he received his Ph.D. in computer science in 1974. He is currently T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics in the School of Engineering and Applied Sciences at Harvard University, where he has taught since 1982. His work has ranged over several areas of theoretical computer science, particularly complexity theory, computational learning, and parallel computation. He also has interests in computational neuroscience, evolution and artificial intelligence. He received the Nevanlinna Prize at the International Congress of Mathematicians in 1986, the Knuth Award in 1997, the European Association for Theoretical Computer Science EATCS Award in 2008, and the 2010 A. M. Turing Award.

Professor of Theoretical Computer Science
Laboratory for Foundations of Computer Science
School of Informatics
University of Edinburgh

Title: Church's Coincidences

Abstract: The foundations of computing lay in a coincidence:
Church's lambda calculus (1933), Herbrand and Godel's recursive functions (1934), and Turing's machines (1935) all define the same model of computation.
Another coincidence: Gentzen's intuitionistic natural deduction (1935) and Church's simply-typed lambda calculus (1940) define isomorphic systems. We review the history and significance of these coincidences, with an eye to Turing's role.

Bio: Philip Wadler is Professor of Theoretical Computer Science at the University of Edinburgh. He is an ACM Fellow and a Fellow of the Royal Society of Edinburgh, past holder of a Royal Society-Wolfson Research Merit Fellowship, and Chair of ACM SIGPLAN. Previously, he worked or studied at Stanford, Xerox Parc, CMU, Oxford, Chalmers, Glasgow, Bell Labs, and Avaya Labs, and visited as a guest professor in Copenhagen, Sydney, and Paris. He has an h-index of 52, appears at position 269 on Citeseer's list of most-cited authors in computer science, and is a winner of the POPL Most Influential Paper Award. He contributed to the designs of Haskell, Java, and XQuery, and is a co-author of Introduction to Functional Programming (Prentice Hall, 1988), XQuery from the Experts (Addison Wesley, 2004) and Generics and Collections in Java (O'Reilly, 2006). He has delivered invited talks in locations ranging from Aizu to Zurich.

Professor
School of Mathematics
Institute for Advanced Study
Princeton

Title: "The hardness of proving computational hardness"

Abstract: Turing proved that certain natural problems are unsolvable by computers, and many more were discovered thanks to his groundbreaking work. Computational Complexity theory seeks to extend this work and find, among those problems which are solvable, which are easy and which are hard. Despite half a century of research, we still lack tools to establish the difficulty of natural computational tasks. I will survey what we know, what we want to know, and some possible reasons why we don't know it yet.

Bio: Avi Wigderson has been a Professor of Mathematics at the Institute for Advanced Study, Princeton since 1999. His research interests include Complexity Theory, Parallel Computation, Combinatorics and Graph Theory, Combinatorial Optimization Algorithms, Randomness and Cryptography, and Distributed and Neural Networks.
His honors include the Gödel Prize (2009), the Conant Prize (2008), the Gibbs Lecture, San Diego, California (2008), the ICM Plenary Lecture, Madrid, Spain (2006), The Yoram Ben-Porat Presidential Prize for Outstanding Researcher, and the Nevanlinna Prize (1994). He has a Ph.D. in Computer Science, Princeton University and a B.Sc in Computer Science, Technion, Haifa, Israel, 1980. He taught at the Computer Science Institute, Hebrew University, Jerusalem from 1986-2003.

Director and Professor
Institute for Theoretical Computer Science
Tsinghua University

Title: Quantum Computing: A Great Science in the Making

Abstract: In recent years, the scientific world has seen much excitement over the development of quantum computing, and the ever increasing possibility of building real quantum computers. What’s the advantage of quantum computing? What are the secrets in the atoms that could potentially unleash such enormous power, to be used for computing and information processing? In this talk, we will take a look at quantum computing, and make the case that we are witnessing a great science in the making.

Bio: Andrew Chi-Chih Yao is currently the Dean of the Institute for Interdisciplinary Information Sciences, at Tsinghua University, Beijing. He received his BS in Physics from National Taiwan University, PhD in Physics from Harvard University, and PhD in Computer Science from the University of Illinois. From 1975 onward, Yao served on the faculty at MIT, Stanford, UC Berkeley and Princeton University, before joining Tsinghua Univeristy in 2004. He is a member of the US National Academy of Sciences, the American Academy of Arts and Sciences, and the Chinese Academy of Sciences, and recipient of the A.M. Turing Award in year 2000 for his contributions to the theory of computation.