Jacob Fox will be giving a public talk on February 1, 2018 ,as part of the program on combinatorics and complexity hosted by the CMSA during AY17-18.The talk will be at 5:00pm in Askwith Hall, 13 Appian Way, Cambridge, MA.
Title: Arithmetic patterns, games, and the quest for fast algorithms
Abstract: In this talk, I will discuss recent advances on three seemingly disparate questions and how they relate to each other.
1. What patterns can we find in prime numbers?
2. How many cards do we need in the popular card game SET® to guarantee a valid set?
3. Can we find faster algorithms to better analyze large networks?
Finding patterns like arithmetic progressions in prime numbers has fascinated mathematicians for many centuries. More recently, people have enjoyed playing the card game SET®, and natural questions that arise from this game have been shown to be closely related to longstanding open problems in mathematics and computer science. Over the last few decades, as we strive to better understand the world through large networks, analyzing enormous data sets has become a priority. Traditional algorithms are insufficient for these purposes, and the need for faster algorithms has become apparent.
Advances (some quite surprising) on these questions have used tools from a variety of areas of mathematics, including combinatorics, analysis, algebra, probability, geometry, and number theory. No prior knowledge is assumed.