event
ARC Colloquium: Gil Kalai, Hebrew University of Jerusalem- Israel/Yale University - New Haven, CT
Primary tabs
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".
Groups
Status
- Workflow Status: Published
- Created By: Elizabeth Ndongi
- Created: 02/12/2013
- Modified By: Fletcher Moore
- Modified: 10/07/2016
Categories
Keywords
Target Audience