Recent Comments

Recent Posts
 Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes
 Happy Birthday Ervin, János, Péter, and Zoli!
 My Mathematical Dialogue with Jürgen Eckhoff
 Test Your Intuition (23): How Many Women?
 Happy Birthday Richard Stanley!
 Influence, Threshold, and Noise
 Erdős Lectures 2014 – Dan Spielman
 Answer to Test Your Intuition (22)
 Test your intuition (22): Selling Two Items in a Bundle.
Top Posts & Pages
 Why Quantum Computers Cannot Work: The Movie!
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 Polymath 8  a Success!
 Believing that the Earth is Round When it Matters
 Emmanuel Abbe: Erdal Arıkan's Polar Codes
 Another Forgotten Bet: Is Don Zagier About to Owe Me 1000 Shekels For The Proof of the ABC Conjecture?
 About
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 In how many ways you can chose a committee of three students from a class of ten students?
RSS
Category Archives: Probability
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
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 ndimensional space. (Other graphs were considered later as … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching
Tagged Arrow's theorem, Percolation
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 FourierWalsh expansion of Boolean functions and the use of Hypercontractivity. Before that we started with a very nice discrete isoperimetric question on a … Continue reading
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 BenOr 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 Boolean functions, Tribes
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). I am visiting now Poznań for the 16th … Continue reading
Posted in Combinatorics, Conferences, Open problems, Philosophy, Probability
Tagged Poznan, RSA
Leave a comment
BosonSampling and (BKS) Noise Sensitivity
Following are some preliminary observations connecting BosonSampling, an interesting computational task that quantum computers can perform (that we discussed in this post), and noisesensitivity in the sense of Benjamini, Schramm, and myself (that we discussed here and here.) BosonSampling and computationalcomplexity hierarchycollapse Suppose that … Continue reading
Posted in Computer Science and Optimization, Physics, Probability
Tagged BosonSampling, Noise, Noisesensitivity, Quantum computation
4 Comments
LawlerKozdronRichardsStroock’s combined Proof for the MatrixTree 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 Kirchhoff and Wilson via Kozdron and Stroock. The lecture is based on … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Probability
Tagged David Wilson, Gustav Kirchhoff, Trees
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 Erosion, J. F. C. Kingman, Probability, S. E. Volkov
1 Comment
Taking balls away: Oz’ Version
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 Oz, Probability, Test your intuition
14 Comments
Answer to test your intuition (18)
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 Itai Benjamini, Probability, random permutation, Ronen Eldan, Test your intuition
3 Comments