ARC Colloquium: Gil Kalai, Hebrew University of Jerusalem- Israel/Yale University - New Haven, CT

Add to Calendar
Date:
February 25, 2013 1:00 pm
Location:
Klaus 1116

Title: Probability and Algorithms - Examples of open collaborative research over the Internet

Abstract:

 I shall discuss examples of recent Internet research oriented math activities:

 1) Polymath5 - Erdos discrepancy problem.

The problem is to find a function from the natural numbers to {-1,1} such that the sum of values on any sequence of the form {a,2,3a,...,ra} is bounded. Erdos conjectured that no such function exists. It is still open even after many individual attempts and an attempt to solve it collectively in a polymath project.

Background: please look at this MO problem

http://mathoverflow.net/questions/105383/the-behavior-of-a-certain-greedy-algorithm-for-erds-discrepancy-problem  (and the blog post linked there.)

 2) The study of Mobius randomness over blogs and MathOverflow.

 A function defined on the natural number is Mobius-random if its correlation with the Mobius function tends to zero. The prime number theorem asserts that the constant one function is Mobius random. I will discuss the result by Ben Green that functions described by bounded depth circuits are Mobius-random.

Here is one link

MO posts: http://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function, which contains more links.

I may briefly mention a couple more examples. One is my debate with Aram Harrow on the feasibility of quantum computers. It took place over the blog "Goedel's lost letter and NP=P" (The first post the last post ) and the other is probability-motivated questions regarding the computer game "angry birds".

I will try to give some taste of the mathematical problems/issues and also a little taste of this way of "doing mathematics".