The London Mathematical Society Computer Science Colloquium 2015 - Algorithms and Cryptography - Apology Accepted
This event was held on 17th September 2015
Venue: The Royal Society, 6-9 Carlton House Terrace, SW1Y 5AG.
Kindly supported by GCHQ and Microsoft Research.
G.H. Hardy ended his 1940 essay A Mathematician's Apology by declaring that, along with other like-minded mathematicians, he has never done anything 'useful'. Algorithms and Cryptography provide the greatest examples disproving this claim, as the existence and non-existence of algorithms solving basic problems of pure maths underpin e-commerce and the security of encrypted digital data. In this Colloquium, three illustrious innovators from each of these fields will reflect on the practical importance in our modern digital society of the purely mathematical ideas on which their subjects are based.
Mike Paterson (University of Warwick)
The Bent Coin: tales of the expected and unexpected
Randomness plays an important role in many human activities (for examples, tie-breaking in sport and elections; assigning priority; assigning an indivisible good; gambling) and is a key component in some algorithms and cryptographic protocols, and in many games.
Devices used for generating randomness include dice, ping-pong balls, spinning tops, thermal noise in transistors, clay shards, straws (long and short), but perhaps the most characteristic and convenient is the toss of a coin. Some famous events have been decided or influenced in such a way.
Coins can be fair or unfair and exploited in fair or unfair ways. A fair coin can be used surprisingly efficiently to generate arbitrary probabilities. We explore the efficiency of fair and unfair coins in generating a range of different probabilities. In this talk we will focus on an intriguing question posed by John Conway fifty years ago and show some progress in resolving it. This is joint work with Troels Sorensen.
Jon Kleinberg (Cornell)
Bursts, Cascades, and Hot Spots: Mathematical Models of the Online World
As an increasing amount of social interaction moves online, it becomes possible to study phenomena that were once essentially invisible: how our social networks are organized, how groups of people come together, and how information spreads through society.
With computational and mathematical ideas, we can begin to map the rich landscape that emerges, filled with "hot spots" of collective attention, and behaviors that cascade through complex networks of social connections.
Nigel Smart (University of Bristol)
It's Good to Talk
I will review the positive side of communication in computer science and cryptography in particular. After a brief discussion of the standard theoretical results on communication in complexity theory; Professor Smart will turn to discussing why communication is a powerful primitive in cryptography. I will talk about secure computation, key agreement and identification protocols. The talk will be aimed at a general computer science/mathematics audience with no prior knowledge of cryptography assumed.
Lance Fortnow (Georgia Tech)
The P v NP Problem in the Era of Fast Computing
The P v NP problem asks if every problem where we can efficiently verify a solution, we can also efficiently find that solution.
The P v NP problem is a great mathematical challenge, one of the Clay Math millennial problems, and we'll review the (limited) progress towards separating P and NP.
The importance of the P v NP came from real-world algorithmic challenges and advances in hardware and algorithms have let us solve NP problems we never thought we could solve years ago. We discuss this progress and the implications across computer science and society in general.
Adi Shamir (Weizmann Institute of Science)
New Connections Between Randomness Hardness and Security
In the last 35 years, researchers in cryptography had explored the interesting relationships between random functions, computational complexity, and cryptographic security. In this talk Professor Shamir will survey some of these known results, and describe several new surprising connections which had been discovered in the last few years.
Shafi Goldwasser (MIT & Weizmann Institute of Science)
The Cryptographic Lens: Past, Present and Future
Abstract: Going beyond the basic challenge of private and authentic communication, in the last 35 years, cryptography has become the general study of correctness and privacy of computation in the presence of a computationally bounded adversary. These studies have en route changed how we think today of proofs, reductions, randomness, and information from a computational point of view. In this talk Professor Goldwasser will discuss some beautiful developments in the theory of computing through this cryptographic lens, and the role cryptography can play in the next successful shift to full blown cloud computing.
Submitted by Jesse Garrick on