Recent Comments

Recent Posts
 Gil’s Collegial Quantum Supremacy Skepticism FAQ
 Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectationthresholds
 Starting today: Kazhdan Sunday seminar: “Computation, quantumness, symplectic geometry, and information”
 The story of Poincaré and his friend the baker
 Gérard Cornuéjols’s baker’s eighteen 5000 dollars conjectures
 Noisy quantum circuits: how do we know that we have robust experimental outcomes at all? (And do we care?)
 Test Your Intuition 40: What Are We Celebrating on Sept, 28, 2019? (And answer to TYI39.)
 Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google).
 Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube.
Top Posts & Pages
 Gil's Collegial Quantum Supremacy Skepticism FAQ
 Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectationthresholds
 TYI 30: Expected number of Dice throws
 Amazing: Hao Huang Proved the Sensitivity Conjecture!
 Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google).
 Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube.
 Amazing: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang made dramatic progress on the Sunflower Conjecture
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 Extremal Combinatorics I: Extremal Problems on Set Systems
RSS
Author Archives: Gil Kalai
Gil’s Collegial Quantum Supremacy Skepticism FAQ
The first 15 samples of Google’s 53 qubit flagship quantum supremacy experiment! After the sensationally successful Scott’s Supreme Quantum Superiority FAQ and Boaz’s inferior classical inferiority FAQ let me add my contribution, explaining my current skeptical view. (I was actually … Continue reading
Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectationthresholds
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 Bhargav Narayanan, Jeff Kahn, Jinyoung Park, Keith Frankston
3 Comments
Starting today: Kazhdan Sunday seminar: “Computation, quantumness, symplectic geometry, and information”
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
The story of Poincaré and his friend the baker
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 Google, Henri Poincaré, quantum supremacy
24 Comments
Gérard Cornuéjols’s baker’s eighteen 5000 dollars conjectures
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
Noisy quantum circuits: how do we know that we have robust experimental outcomes at all? (And do we care?)
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 chaos, chaos and computation, quantum supremacy
10 Comments
Test Your Intuition 40: What Are We Celebrating on Sept, 28, 2019? (And answer to TYI39.)
Update: We are celebrating 10 years anniversary to Mathoverflow Domotorp got the answer right. congratulations, Domotorp! To all our readers: Shana Tova Umetuka – שנה טובה ומתוקה – Happy and sweet (Jewish) new year.
Posted in Test your intuition, What is Mathematics
Tagged Mathoverflow, Test your intuition
6 Comments
Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google).
A 2017 cartoon from this post. 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 verifiable experiments (namely experiments … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Quantum, Updates
Tagged John Martinis
65 Comments
Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube.
Three isoperimetric papers by Michel Talagrand (see the end of the post) Discrete isoperimetric relations are of great interest on their own and today I want to tell you about a new isoperimetric inequality by Jeff Kahn and Jinyoung Park … Continue reading
Alef’s corner: Bicycles and the Art of Planar Random Maps
The artist behind Alef’s corner has a few mathematical designs and here are two new ones. (See Alef’s website offering over 100 Tshirt designs.) which was used for the official Tshirt for JeanFrançois Le Gall’s birthday conference. See also … Continue reading