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

Event Details
  • Date/Time:
    • Monday February 25, 2013
      12:00 pm
  • Location: Klaus 1116
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

ndongi@cc.gatech.edu

Summaries

Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

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".

 

 

Additional Information

In Campus Calendar
No
Groups

College of Computing, School of Computer Science, ARC

Invited Audience
No audiences were selected.
Categories
No categories were selected.
Keywords
No keywords were submitted.
Status
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Feb 12, 2013 - 7:52am
  • Last Updated: Oct 7, 2016 - 10:02pm