Tag Archives: Mobius randomness

Open Collaborative Mathematics over the Internet – Three Examples

After much hesitation, I decided to share with you the videos of my lecture: Open collaborative mathematics over the internet – three examples, that I gave last January in Doron Zeilberger’s seminar at Rutgers on experimental mathematics. Parts of the 47-minutes talk is  mathematical, while other parts are about mathematics on the Internet, blogs,  the polymath projects, MathOverflow, etc.

Here is the video of part I (30 minutes) and here is the video of  part II (17 minutes).

I tried to give some homage to Doron’s own lecture style, but when I saw the video, I could not ignore some aspects of my own style – complete indifference between plus and a minus, between x^2 and \sqrt x, between multiplying by something and dividing by the same thing, between subscripts and superscripts, between what are “rows: and what are “columns”, etc., and, in addition, randomly ending English words with an ‘s’ regardless of what English grammar dictates. Apologies. This was a rare occasion of giving a talk about “meta” matters of doing mathematics.

My first (and main) example was Erdős discrepancy’s problem, and I mentioned some experimental aspects, and heuristic arguments. The second example was Möbius randomness,  continued with some comments on MathOverflow, some  of the “goodies” one can earn participating in MathOverflow, and some comments on a debate regarding polymath projects organized by I.A.S a few years ago.  The third example was about mathematically oriented skepticism. This time not about my debate with Aram Harrow and quantum computing skepticism (that I briefly mentioned), but about my “Angry Birds” skepticism. The lecture was a mixture of a blackboard talk and presentation of various Internet site.

Summary and links

Here are the links to the Internet pages I presented with an outline of the lecture:

Video I (Erdős discrepancy problem)

00:00-00:43 Doron’s introduction; 00:43-4:00 On the screen: Erdős discrepancy problems: showing this post (EDP22) from Gowers’s blog. I talked  about the chaotic nature of mathematics on the Internet. Then I explained what are polymath projects, mentioned polymath1 and density Hales-Jewett, other polymath projects, and polymath5.

4:00-12:00 Polymath5, discrepancy of hypergraphs, and The Erdős Discrepancy problem. [6:06 “There is nothing more satisfying in a lecture than seeing attempts by the speaker to move an unmovable blackboard”]; Some basic observations, random signs, Mobius functions, the log n example.

12:00-16:00 Plan for the next fifteen minutes: a) Greedy methods, b)Heuristic approaches, c) Hereditary discrepancy

17:00 – 18:40 Alex Nokolov and Kinal Talwar’s work on hereditary discrepancy. On the screen: Talwar’s post discrepancy to privacy and back on Windows on Theory

18:40 -23:00   Greedy approaches. On the screen:  My question on MathOverflow – on a certain greedy algorithm for Erdős discrepancy problem; The MO answer by ‘rlo'; a follow up question

23:00 – 27:00 What is MathOverflow. On the screen: my old MO page. (Here is the new one.) What is  “MO- reputation,” which “badges” you can earn and for what; Earning “hats” in more advanced site: On the screen:  hat champions from TCS-Stackexchange, winter 2012. (This webpage is no longer available.)

27:00 – 30:00 My heuristic approach for EDP

Video II (Möbius randomness, and angry birds)

On the screen: My MO question on Möbius randomness of the Walsh functions

00:00-02:00 Diversion: The IAS debate on polymath projects between Gowers and Sarnak, and comments  by me and by Noga Alon.

02:00-05:40  Möbius randomness and computational complexity. What is Mõbius randomness (MR);  Peter Sarnak’s Jerusalem talk on MR, his belief regarding the hardness of factoring, and my opinion; The AC^0 prime number conjectures and Walsh functions. My MO question; Ben Green’s MO-answer to one problem and Bourgain’s result answering a second question.

05:40-7:50 A remaining question on MR of Rudin-Shapiro sequences. On the screen – my MO question Mobius randomness of the Rudin-Shapiro sequence; What is a bounty in MathOverflow; Diversion: The power that comes with high reputation on MO. Who won my bounty.

7:50-09:30  My debate with Aram Harrow on my Quantum computers skepticism. On the screen the debates first post and then the post “can you hear the shape of a quantum computer?

09:30-14:30 Example 3: Another mathematically related skepticism – Angry Birds. On the screen this page from Arqade : Most voted questions (a few are very amusing); Introduction to the game “Angry Birds”; My skeptical theory: “Angry Birds” is becoming easier with new versions, and the statistical argument for it. I mentioned the Arqade’s question “Is angry Birds deterministic” that got (then) 143 upvotes, and was a role-model for me.

abd

14:30-17:00 My Arqade question, my hopes, and how it was accepted by the computer-games community;  On the screen: my Arqade question:

Continue reading

The Quantum Debate is Over! (and other Updates)

Quid est noster computationis mundus?

Nine months after is started, (much longer than expected,) and after eight posts on GLL, (much more than planned,)  and almost a thousand comments of overall good quality,   from quite a few participants, my scientific debate with Aram Harrow regarding quantum fault tolerance is essentially over. Some good food for thought, I hope. As always, there is more to be said on the matter itself, on the debate, and on other”meta” matters, but it is also useful to put it now in the background for a while, to continue to think about quantum fault tolerance in the slow pace and solitude, as I am used to, and also to move on in other fronts, which were perhaps neglected a little.

Here are the links to the eight posts: My initial post “Perpetual Motion of The 21st Century?” was followed by three posts by Aram. The first “Flying Machines of the 21st Century?” the second “Nature does not conspire” and the third “The Quantum super-PAC.” We had then two additional posts “Quantum refutations and reproofs” and “Can you hear the shape of a quantum computer?.” Finally we had  two conclusion posts: “Quantum repetition” and “Quantum supremacy or quantum control?

EDP 22-27

We had six new posts on the Erdos Discrepancy Problem over Gowers’s blog (Here is the link to the last one EDP27). Tim contributed a large number of comments and it was interesting to follow his line of thought.  Other participants also contributed a few comments. One nice surprise for me was that the behavior of the hereditary discrepancy for homogeneous arithmetic progression in {1,2,…,n} was  found by Alexander Nikolov and  Kunal Talwar. See this post From discrepancy to privacy and back and the paper. Noga Alon and I showed that it is {\tilde{\Omega}(\sqrt{\log n})} and at most {n^{O(\frac{1}{\log\log n})}}, and to my surprise Alexander and Kunal showed that the upper bound is the correct behavior. The argument relies on connection with differential privacy.

Möbius randomness and computation

After the AC^0-prime number theorem was proved by Ben Green, and the Mobius randomness of all Walsh functions and monotone Boolean function was proved by Jean Bourgain, (See this MO question for details) the next logical step are low degree polynomials over Z/2Z . (The Walsh functions are degree 1 polynomials.) The simplest case offered to me by Bourgain is the case of the Rudin-Shapiro sequence. (But for an ACC(2) result via Razborov-Smolensky theorem we will need to go all the way to polynomial of degree polylog.) I asked it over MathOverflaw. After three months of no activity I offered a bounty of 300 of my own MO-reputations. Subsequently, Terry Tao and Ben Green discussed some avenues and eventually Tao solved the problem (and earned the 300 reputation points). Here is a very recent post on Möbius randomness on Terry Tao’s blog.

Influences on large sets

In my post Nati’s Influence I mentioned two old conjectures (Conjecture 1 dues to Benny Chor and Conjecture 2) about influence of large sets on Boolean functions. During Jeff Kahn’s visit to Israel we managed to disprove them both. The disproof is inspired by an old construction of Ajtai and Linial.

Tel Aviv, New Haven, Jerusalem

Last year we lived for a year in Tel Aviv which was a wonderful experience: especially walking on the beach every day and feeling the different atmosphere of the city. It is so different from my Jerusalem and still the people speak fluent Hebrew. I am now in New Haven. It is getting cold and the fall colors are getting beautiful. And it also feels at home after all these years. And next week I return to my difficult and beautiful  (and beloved) Jerusalem.