Tag Archives: Noise-sensitivity

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

Noise Sensitivity and Percolation. Lecture Notes by Christophe Garban and Jeff Steif

Posted on November 6, 2011 by

Lectures on noise sensitivity and percolation is a new beautiful monograph by Christophe Garban and Jeff Steif. (Some related posts on this blog: 1, 2, 3, 4, 5)

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

Noise Stability and Threshold Circuits

Posted on February 10, 2010 by

The purpose of this post is to describe an old conjecture (or guesses, see this post) by Itai Benjamini, Oded Schramm and myself (taken from this paper) on noise stability of threshold functions. I will start by formulating the conjectures and … Continue reading →

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

The Intermediate Value Theorem Applied to Football

Posted on April 20, 2009 by

My idea (in my teenage years) of how to become a professional basketball player was a bit desperate. To cover for my height and my athletic (dis)abilities, I would simply practice how to shoot perfectly from every corner of the … Continue reading →

Posted in Mathematics to the rescue, Sport, Taxi-and-other-stories | Tagged , , , , , | 11 Comments

Noise Sensitivity Lecture and Tales

Posted on March 6, 2009 by

  A lecture about Noise sensitivity Several of my recent research projects are related to noise, and noise was also a topic of a recent somewhat philosophical post.   My oldest and perhaps most respectable noise-related project was the work with Itai Benjamini and Oded … Continue reading →

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