Recent Comments

Recent Posts
 The US Elections and Nate Silver: Informtion Aggregation, Noise Sensitivity, HEX, and Quantum Elections.
 Avifest live streaming
 AlexFest: 60 Faces of Groups
 Postoctoral Positions with Karim and Other Announcements!
 Jirka
 AviFest, AviStories and Amazing Cash Prizes.
 Polymath 10 post 6: The ErdosRado sunflower conjecture, and the Turan (4,3) problem: homological approaches.
 Polymath 10 Emergency Post 5: The ErdosSzemeredi Sunflower Conjecture is Now Proven.
 Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem!
Top Posts & Pages
 The US Elections and Nate Silver: Informtion Aggregation, Noise Sensitivity, HEX, and Quantum Elections.
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 Why Quantum Computers Cannot Work: The Movie!
 Auctionbased Tic Tac Toe: Solution
 Baggage Claim or Baggage Reclaim
 A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24
 Polymath 10 Emergency Post 5: The ErdosSzemeredi Sunflower Conjecture is Now Proven.
 Believing that the Earth is Round When it Matters
 יופיה של המתמטיקה
RSS
Category Archives: Probability
The US Elections and Nate Silver: Informtion Aggregation, Noise Sensitivity, HEX, and Quantum Elections.
Being again near general elections is an opportunity to look at some topics we talked about over the years. I am quite fond of (and a bit addicted to) Nate Silver’s site FiveThirtyEight. Silver’s models tell us what is the probability that … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Probability, Quantum
Tagged Donald Trump, Hillary Clinton, Nate Silver
5 Comments
TYI 26: Attaining the Maximum
(Thanks, Dani!) Given a random sequence , ******, , let . and assume that . What is the probability that the maximum value of is attained only for a single value of ? Test your intuition: is this probability bounded … Continue reading
More Reasons for Small Influence
Readers of the bigleague ToC blogs have already heard about the breakthrough paper An averagecase depth hierarchy theorem for Boolean circuits by Benjamin Rossman, Rocco Servedio, and LiYang Tan. Here are blog reports on Computational complexity, on the Shtetl Optimized, and of Godel … Continue reading
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
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). Update: Here is a picture from 2015, while … Continue reading
Posted in Combinatorics, Conferences, Open problems, Philosophy, Probability
Tagged Poznan, RSA
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 BosonSampling, Noise, Noisesensitivity, Quantum computation
8 Comments