Computers, algorithms, and artificial intelligence have touched every aspect of our society, from science, to communication, to the justice system. But despite their enormous power, computers have fundamental limits — problems that no program can solve, and thorny issues in fairness and human rights. During this 26th year of the popular Ulam Lecture Series, SFI Professor Cristopher Moore looks at two sides of computation — the mathematical structures that make problems easy or hard, and the growing debate about fairness in algorithmic predictions.
Lecture I, Monday, September 24, 7:30 p.m.— Easy, Hard, and Impossible Problems: The Limits of Computation
Every day we are faced with problems that we need to solve. Some are easy, like choosing the quickest way across town. Others are more difficult but can be solved. Some seem impossible to solve.
In this first Ulam Lecture, SFI scientist Cristopher Monroe talks about the nature of problems, the use of mathematics to analyze and solve them. He also looks at the nature of mathematical truth and creativity.
Key message: Mathematics will never be complete; we will constantly be looking beyond the systems we have, seeking new forms of reason, and ways to explore, to think and to learn.
8:35 Computation means the art and science of problem-solving. Some problems are easy to solve, others are very hard, and others still are absolutely impossible.
11:24 What is an algorithm? A method of solving a problem of a certain kind.
12:25 Leonhard Euler invented graph theory, which is a simple, elegant algorithm that can be used to study food webs, biological networks, transport routes, etc. without exploring each possible route.
14:31 Hamilton invented Hamiltonian paths, which systematically search through all possible paths, making a choice between two paths, with no possibility of shortening the process.
26:51 Mount Fuji landscape theory operates where there is only one possible solution to a problem. In this case, always moving up, making small changes one at a time, will bring the eventual solution.
28:00 Most problems are much more complex, where this approach does not work. These very hard problems demand exploration and research to show where the best solution is and the pathway to approaching it.
31:50 For some problems, it is even hard to tell if the right solution has been reached, leading to the concept of complexity classes.
46:56 Are there problems that cannot be solved, with or without a computer?
49:10 Paradoxes are the heart of mathematics, which show that there are limits to what computers can do, leading to the concept of:
1:00:26 Unprovable truths. There is no one logical system that can prove all the true things in mathematics.
Lecture II, Tuesday, September 25, 7:30 p.m.— Data, Algorithms, Justice, and Fairness
Algorithms and artificial intelligence are having a growing influence in human society, but despite their enormous power, they still have limits. This is especially true in issues involving human rights and fairness.
In this second Ulam Lecture, SFI scientist Cristopher Monroe talks about the role of algorithms in day to day life, using and the justice system and the bail/detention process as an example.
Key message: Algorithms and artificial intelligence will help us move towards a better future if we can control bias and strive to inculcate fairness into the system.
12:58 The promise of artificial intelligence: playing games, diagnosing disease, translating, etc. But it still has limitations.
23:45 Can AI algorithms assist in relieving the challenge of pretrial detention?
26:43 How do the algorithms work in predicting criminal behavior? Can we tolerate false negatives or false positives?
30:37 Comparison of the two main algorithms that are used to predict how people will behave in the criminal justice system. One is COMPAS, which uses propriety software and so is not transparent, and Arnold PSA, which uses a simple, transparent points system.
39:00 How accurate are these systems, and what level of error can we tolerate when people are concerned?
45:52 Fairness and the ProPublica debate: is the COMPAS system racially biased and inherently unfair?
53:00 Can we actually arrive at a correct definition of fairness? That seems unlikely at the moment?
55:05 Where do we go from here? Use open algorithms, embrace uncertainty, balance science and politics, allow human interventions, avoid human bias from the past being perpetuated in the future AI.
Cristopher Moore is a Professor at the Santa Fe Institute where he works on problems at the interface of mathematics, computer science, and physics. The co-author of The Nature of Computation (Oxford University Press), a classic textbook in modern mathematics, Moore has also written more than 150 scientific papers on topics ranging from quantum computing to the theory of social networks.
Moore is an elected fellow of the American Association for the Advancement of Science, the American Physical Society, and the American Mathematical Society.
SFI's Stanislaw Ulam Memorial Lecture Series honors the memory of the late theoretical mathematician Stanislaw Ulam.
Read the Q&A with Julia Goldberg and Cris Moore in The Santa Fe Reporter (September 19, 2018)