Category Archives: Probability

More Reasons for Small Influence

Readers of the big-league ToC blogs have already heard about the breakthrough paper An average-case depth hierarchy theorem for Boolean circuits by Benjamin Rossman, Rocco Servedio, and Li-Yang Tan. Here are blog reports on Computational complexity, on the Shtetl Optimized, and of Godel … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Open problems, Probability | 12 Comments

Two Delightful Major Simplifications

Arguably mathematics is getting harder, although some people claim that also in the old times parts of it were hard and known only to a few experts before major simplifications had changed  matters. Let me report here about two recent remarkable simplifications … Continue reading

Posted in Combinatorics, Probability, Updates | Tagged , , , , , | Leave a comment

Influence, Threshold, and Noise

  My dear friend Itai Benjamini told me that he won’t be able to make it to my Tuesday talk on influence, threshold, and noise, and asked if I already have  the slides. So it occurred to me that perhaps … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Conferences, Probability, Quantum | Tagged , , , , , , , | 4 Comments

Analysis of Boolean Functions week 5 and 6

Lecture 7 First passage percolation 1)  Models of percolation. We talked about percolation introduced by Broadbent and Hammersley in 1957. The basic model is a model of random subgraphs of a grid in n-dimensional space. (Other graphs were considered later as … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching | Tagged , | Leave a comment

Analysis of Boolean Functions – Week 3

Lecture 4 In the third week we moved directly to the course’s “punchline” – the use of Fourier-Walsh expansion of Boolean functions and the use of Hypercontractivity. Before that we  started with  a very nice discrete isoperimetric question on a … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching | Tagged , , | Leave a comment

Analysis of Boolean functions – week 2

Post on week 1; home page of the course analysis of Boolean functions Lecture II: We discussed two important examples that were introduced by Ben-Or and Linial: Recursive majority and  tribes. Recursive majority (RM): is a Boolean function with variables … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching | Tagged , | Leave a comment

Poznań: Random Structures and Algorithms 2013

   Michal Karonski (left) who built Poland’s probabilistic combinatorics group at Poznań, and a sculpture honoring the Polish mathematicians who first broke the Enigma machine (right, with David Conlon, picture taken by Jacob Fox). Update: Here is a picture from 2015, while … Continue reading

Posted in Combinatorics, Conferences, Open problems, Philosophy, Probability | Tagged , | 2 Comments

BosonSampling and (BKS) Noise Sensitivity

Update (Nov 2014): Noise sensitivity of BosonSampling and computational complexity of noisy BosonSampling are studied in this paper by Guy Kindler and me. Some of my predictions from this post turned out to be false. In particular the noisy BosonSampling … Continue reading

Posted in Computer Science and Optimization, Physics, Probability | Tagged , , , | 8 Comments

Lawler-Kozdron-Richards-Stroock’s combined Proof for the Matrix-Tree theorem and Wilson’s Theorem

   David Wilson and a cover of Shlomo’s recent book “Curvature in mathematics and physics” A few weeks ago, in David Kazhdan’s basic notion seminar, Shlomo Sternberg gave a lovely presentation Kirchho ff and Wilson via Kozdron and Stroock. The lecture is based on … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability | Tagged , , | 4 Comments

Oz’ Balls Problem: The Solution

A commentator named Oz proposed the following question: You have a box with n red balls and n blue balls. You take out each time a ball at random but, if the ball was red, you put it back in the box and take out … Continue reading

Posted in Probability, Test your intuition | Tagged , , , | 1 Comment