Tag Archives: Noise-sensitivity

Inaugural address at the Hungarian Academy of Science: The Quantum Computer – A Miracle or Mirage

Posted on November 5, 2022 by Gil Kalai

(Picture: János Pach) The Quantum Computer – A Miracle or Mirage inaugural address of Gil Kalai honorary member of the MTA, Budapest, 15 June, 2022, 15:00 Abstract: On February 12, 2002, Michel Devoret’s lecture entitled “The Quantum Computers: Miracle or … Continue reading →

Posted in Academics, Computer Science and Optimization, Physics, Quantum | Tagged , , | 3 Comments

Itai Benjamini and Jeremie Brieussel: Noise Sensitivity Meets Group Theory

Posted on July 15, 2019 by Gil Kalai

The final  version of my ICM 2018 paper Three puzzles on mathematics computation and games has been available for some time. (This proceedings’ version, unlike the arXived version has a full list of references.)  In this post I would like to … Continue reading →

Posted in Algebra, Combinatorics, Probability | Tagged , , | 1 Comment

Second third of my ICM 2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

Posted on December 15, 2017 by Gil Kalai

Update: Here is a combined version of all three parts: Three puzzles on mathematics computations and games. Thanks for the remarks and corrections. More corrections and comments welcome. Dear all, here is the draft of the second third of my paper … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Games | Tagged , , , , , | 6 Comments

Influence, Threshold, and Noise

Posted on June 14, 2014 by Gil Kalai

  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 , , , , , , , | 6 Comments

BosonSampling and (BKS) Noise Sensitivity

Posted on August 1, 2013 by Gil Kalai

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, Quantum | Tagged , , , | 8 Comments

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

Posted on November 6, 2011 by Gil Kalai

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 Gil Kalai

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 , , , , | 14 Comments

The Intermediate Value Theorem Applied to Football

Posted on April 20, 2009 by Gil Kalai

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 , , , , , | 20 Comments

Noise Sensitivity Lecture and Tales

Posted on March 6, 2009 by Gil Kalai

  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 , , , , , , | 14 Comments