Monthly Archives: October 2019

Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectation-thresholds

Posted on October 30, 2019 by Gil Kalai

This post describes a totally unexpected breakthrough about expectation and thresholds. The result  by Frankston, Kahn, Narayanan, and Park has many startling applications and it builds on the recent breakthrough work of Alweiss, Lovett, Wu and Zhang on the sunflower … Continue reading →

Posted in Combinatorics, Probability | Tagged , , , | 4 Comments

Starting today: Kazhdan Sunday seminar: “Computation, quantumness, symplectic geometry, and information”

Posted on October 27, 2019 by Gil Kalai

Sunday, 27 October, 2019 – 14:00 to 16:00 Repeats every week every Sunday until Sat Feb 01 2020 Location: Ross 70 See also: Seminar announcement; previous post Symplectic Geometry, Quantization, and Quantum Noise. The Google supremacy claims are discussed (with … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Geometry, Physics, Teaching | Tagged , , , | Leave a comment

The story of Poincaré and his friend the baker

Posted on October 13, 2019 by Gil Kalai

Update: After the embargo update (Oct 25): Now that I have some answers from the people involved let me make a quick update: 1) I still find the paper unconvincing, specifically, the few verifiable experiments (namely experiments that can be … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Probability, Quantum, Statistics | Tagged , , | 25 Comments

Gérard Cornuéjols’s baker’s eighteen 5000 dollars conjectures

Posted on October 13, 2019 by Gil Kalai

Gérard Cornuéjols Gérard Cornuéjols‘s beautiful (and freely available) book from 2000 Optimization: Packing and Covering is about an important area of combinatorics which is lovely described in the preface to the book The integer programming models known as set packing … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Open problems | Tagged , , , , | 3 Comments

Noisy quantum circuits: how do we know that we have robust experimental outcomes at all? (And do we care?)

Posted on October 3, 2019 by Gil Kalai

In a recent post we discussed Google’s claim of achieving “quantum supremacy” and my reasons to think that these claims will not stand. (See also this comment for necessary requirements from a quantum supremacy experiment.) This debate gives a good … Continue reading →

Posted in Computer Science and Optimization, Quantum | Tagged , , | 10 Comments