Category Archives: Probability

Analysis of Boolean Functions week 5 and 6

Posted on October 7, 2013 by

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

Posted on September 18, 2013 by

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

Posted on September 8, 2013 by

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

Posted on August 8, 2013 by

   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). I am visiting now Poznań for the 16th … Continue reading →

Posted in Combinatorics, Conferences, Open problems, Philosophy, Probability | Tagged , | Leave a comment

BosonSampling and (BKS) Noise Sensitivity

Posted on August 1, 2013 by

Following are some preliminary observations connecting BosonSampling, an interesting  computational task that quantum computers can perform (that we discussed in this post), and noise-sensitivity in the sense of Benjamini, Schramm, and myself (that we discussed here and here.) BosonSampling and computational-complexity hierarchy-collapse Suppose that … Continue reading →

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

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

Posted on July 23, 2013 by

   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

Posted on May 17, 2013 by

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

Taking balls away: Oz’ Version

Posted on April 27, 2013 by

This post is based on a comment by Oz to our question about balls with two colors: “There is an interesting (and more difficult) variation I once heard but can’t recall where: You have a box with n red balls … Continue reading →

Posted in Guest post, Probability, Test your intuition | Tagged , , | 14 Comments

Answer to test your intuition (18)

Posted on April 23, 2013 by

You have a box with n red balls and n blue balls. You take out balls one by one at random until left only with balls of the same color. How many balls will be left (as a function of n)? … Continue reading →

Posted in Probability, Test your intuition | Tagged , , , , | 3 Comments

Itai Ashlagi, Yashodhan Kanoria, and Jacob Leshno: What a Difference an Additional Man makes?

Posted on April 19, 2013 by

We are considering the stable marriage theorem. Suppose that there are n men and n women. If the preferences are random and men are proposing, what is the likely average women’s rank of their husbands, and what is the likely average … Continue reading →

Posted in Economics, Games, Probability, Test your intuition | Tagged , , , , | Leave a comment