# Computer Science

## High Dimensional Expanders and Ramanujan Complexes

Expander graphs have played, in the last few decades, an important role in computer science, and in the last decade, also in pure mathematics. In recent years a theory of "high-dimensional expanders" is starting to emerge - i.e., simplical complexes which generalize various properties of expander graphs. This has some geometric motivations (led by Gromov) and combinatorial ones (started by Linial and Meshulam). The talk will survey the various directions of research and their applications, as well as potential applications in math and CS. Some of these lead to questions about buildings and representation theory of p-adic groups.

We will survey the work of a number of people. The works of the speaker in this direction are with various subsets of { S. Evra, K. Golubev, T. Kaufman, D. Kazhdan , R. Meshulam, S. Mozes }

## Sparse - Dense Phenomena

The dichotomy between sparse and dense structures is one of the profound, yet fuzzy, features of contemporary mathematics and computer science. We present a framework for this phenomenon, which equivalently defines sparsity and density of structures in many different yet equivalent forms, including effective decomposition properties. This has several applications to model theory, algorithm design and, more recently, to structural limits.

- Read more about Sparse - Dense Phenomena
- 3836 reads

## Cryptography: Secrets and Lies, Knowledge and Trust

What protects your computer password when you log on, or your credit card number when you shop on-line, from hackers listening on the communication lines? Can two people who never met create a secret language in the presence of others, which no one but them can understand? Is it possible for a group of people to play a (card-less) game of Poker on the telephone, without anyone being able to cheat? Can you convince others that you can solve a tough math (or SudoKu) puzzle, without giving them the slightest hint of your solution?These questions (and their remarkable answers) are in the realm of modern cryptography. In this talk I plan to survey some of the mathematical and computational ideas, definitions and assumptions which underlie privacy and security of the Internet and electronic commerce. We shall see how these lead to solutions of the questions above and many others. I will also explain the fragility of the current foundations of modern cryptography, and the need for stronger ones.No special background will be assumed.

## How Does Google Google?

**Abstract:** We all Google. You may even have found this talk by Googling. What you may not know is that behind the Google's and other search engines is beautiful and elegant mathematics. In this talk, I will try to explain the workings of page ranking and search engines using only rusty calculus.

**Bio:** Dr. Margot Gerritsen is the Director of the Institute for Computational and Mathematical Engineering at Stanford University. She is also the chair of the SIAM Activity group in Geoscience, the co-director and founder of the Stanford Center of Excellence for Computational Algorithms in Digital Stewardship, and the director of Stanford Yacht Research. She has been appointed to several prestigious positions, including Magne Espedal Professorship at Bergen University, Aldo Leopold Fellow, Faculty Research Fellow at the Clayman Institute and she is also a Stanford Fellow. She is the editor of the Journal of Small Craft Technology and an associate editor of Transport in Porous Media. We are delighted to have Dr. Gerritsen participate in the Mathematics of Planet Earth series.

- Read more about How Does Google Google?
- 9164 reads

## How Does Google Google? The Math Behind the Internet

We all Google. You may even have found this talk by Googling. What you may not know is that behind the Google’s and other search engines is beautiful and elegant mathematics. In this talk, I will try to explain the workings of page ranking and search engines using only rusty calculus.

An alternative version of this lecture presented at the University of Calgary is also available.

## Alan Turing, the Politics of Sexual Science, and the Making of a Gay Icon

In the 1940s Alan Turing’s homosexuality was an open secret amongst his co-workers at Bletchley Park. In 1952 the secret became widely known when Turing was arrested on charges of “gross indecency” under the same 1885 law that had led to the imprisonment of Oscar Wilde over half a century earlier. Opting for chemical “treatment” of his “condition” rather than imprisonment, Turing was one of many well-known casualties of a heightened drive against homosexuality in a postwar Britain that drew the line between the normal and the deviant more sharply than ever before. In his talk, Chris Waters will discuss Turing’s sexual proclivities and their meanings in the context of his times, focusing in particular on his arrest and subsequent fate in the context of the sexual politics of the first half of the 1950s. In addition, he will discuss the shaping of Turing’s posthumous reputation, beginning with the attempts made by the Gay Liberation Front in the 1970s to render Turing the gay icon he has become today.

## Turing and Intelligent Machines

Turing's interest in the possibility of machine intelligence is probably most familiar in the form of the 'Turing Test', a version of which has been instantiated since 1991 as the Loebner Prize in Artificial Intelligence. To this date the Loebner Gold Medal has not been won. But should any future winner of the prize count themselves as having created a computer that thinks? Turing's 1950 Mind paper 'Computing Machinery and Intelligence', gives a sustained defence of the claim that a machine able to pass the test, which Turing called the Imitation Game, would indeed qualify as thinking. This lecture will explain the Turing Test as well as Turing's more general views concerning the prospects for artificial intelligence and examine both the criticisms of the test and Turing's rebuttals

- Read more about Turing and Intelligent Machines
- 13785 reads

## Alan Turing and Enigma

Central to Alan Turing's posthumous reputation is his work with British codebreaking during the Second World War. This relationship is not well understood, largely because it stands on the intersection of two technical fields, mathematics and cryptology, the second of which also has been shrouded by secrecy. This lecture will assess this relationship from an historical cryptological perspective. It treats the mathematization and mechanization of cryptology between 1920-50 as international phenomena. It assesses Turing's role in one important phase of this process, British work at Bletchley Park in developing cryptanalytical machines for use against Enigma in 1940-41. It focuses on also his interest in and work with cryptographic machines between 1942-46, and concludes that work with them served as a seed bed for the development of his thinking about computers.

### Turing 2012 - Calgary

This talk is part of a series celebrating the Alan Turing Centenary in Calgary. The following mathtube videos are part of this series

- Alan Turing and the Decision Problem,
*Richard Zach*. - Turing's Real Machine,
*Michael R. Williams*. - Alan Turing and Enigma, John R. Ferris.

- Read more about Alan Turing and Enigma
- 9455 reads

## Turing's Real Machines

While Turing is best known for his abstract concept of a "Turing Machine," he did design (but not build) several other machines - particularly ones involved with code breaking and early computers. While Turing was a fine mathematician, he could not be trusted to actually try and construct the machines he designed - he would almost always break some delicate piece of equipment if he tried to do anything practical.

The early code-breaking machines (known as "bombes" - the Polish word for bomb, because of their loud ticking noise) were not designed by Turing but he had a hand in several later machines known as "Robinsons" and eventually the Colossus machines.

After the War he worked on an electronic computer design for the National Physical Laboratory - an innovative design unlike the other computing machines being considered at the time. He left the NPL before the machine was operational but made other contributions to early computers such as those being constructed at Manchester University.

This talk will describe some of his ideas behind these machines.

### Turing 2012 - Calgary

This talk is part of a series celebrating The Alan Turing Centenary in Calgary. The following mathtube videos are also part of this series

- Alan Turing and the Decision Problem,
*Richard Zach*. - Turing's Real Machine,
*Michael R. Williams*. - Alan Turing and Enigma,
*John R. Ferris*.

- Read more about Turing's Real Machines
- 10910 reads

## Alan Turing and the Decision Problem

Many scientific questions are considered solved to the best possible degree when we have a method for computing a solution. This is especially true in mathematics and those areas of science in which phenomena can be described mathematically: one only has to think of the methods of symbolic algebra in order to solve equations, or laws of physics which allow one to calculate unknown quantities from known measurements. The crowning achievement of mathematics would thus be a systematic way to compute the solution to any mathematical problem. The hope that this was possible was perhaps first articulated by the 18th century mathematician-philosopher G. W. Leibniz. Advances in the foundations of mathematics in the early 20th century made it possible in the 1920s to first formulate the question of whether there is such a systematic way to find a solution to every mathematical problem. This became known as the decision problem, and it was considered a major open problem in the 1920s and 1930s. Alan Turing solved it in his first, groundbreaking paper "On computable numbers" (1936). In order to show that there cannot be a systematic computational procedure that solves every mathematical question, Turing had to provide a convincing analysis of what a computational procedure is. His abstract, mathematical model of computability is that of a Turing Machine. He showed that no Turing machine, and hence no computational procedure at all, could solve the Entscheidungsproblem.

### Turing 2012 - Calgary

This talk is part of a series celebrating the Alan Turing Centenary in Calgary. The following mathtube videos are also part of this series

- Alan Turing and the Decision Problem,
*Richard Zach*. - Turing's Real Machine,
*Michael R. Williams*. - Alan Turing and Enigma,
*John R. Ferris*.