Recent Comments

Recent Posts
 Test your intuition 24: Which of the following three groups is trivial
 School Starts at HUJI
 A lecture by Noga
 Ehud Friedgut: Blissful ignorance and the KahnemanTversky paradox
 In And Around Combinatorics: The 18th Midrasha Mathematicae. Jerusalem, JANUARY 1831
 Mathematical Gymnastics
 Media Item from “Haaretz” Today: “For the first time ever…”
 Jim Geelen, Bert Gerards, and Geoﬀ Whittle Solved Rota’s Conjecture on Matroids
 Media items on David, Amnon, and Nathan
Top Posts & Pages
 Test your intuition 24: Which of the following three groups is trivial
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 Believing that the Earth is Round When it Matters
 Polymath 8  a Success!
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 Extremal Combinatorics VI: The FranklWilson Theorem
 Extremal Combinatorics III: Some Basic Theorems
 Why Quantum Computers Cannot Work: The Movie!
 Mathematical Gymnastics
RSS
Category Archives: Computer Science and Optimization
Analysis of Boolean Functions – week 1
Home page of the course. In the first lecture I defined the discrete ndimensional cube and Boolean functions. Then I moved to discuss five problems in extremal combinatorics dealing with intersecting families of sets. 1) The largest possible intersecting family … Continue reading
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
4 Comments
LawlerKozdronRichardsStroock’s combined Proof for the MatrixTree theorem and Wilson’s Theorem
David Wilson and a cover of Shlomo’s recent book “Curvature in mathematics and physics” A few weeks ago, in David Kazhdan’s basic notion seminar, Shlomo Sternberg gave a lovely presentation Kirchhoff and Wilson via Kozdron and Stroock. The lecture is based on … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Probability
Tagged David Wilson, Gustav Kirchhoff, Trees
4 Comments
The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
…while we keep discussing why mathematics is possible… The news Adam Marcus, Dan Spielman, and Nikhil Srivastava posted a paper entitled “Interlacing Families II: Mixed Characteristic Polynomials and the KadisonSinger Problem,” where they prove the 1959 KadisonSinger conjecture. (We discussed part … Continue reading
Why is mathematics possible?
Spectacular advances in number theory Last weeks we heard about two spectacular results in number theory. As announced in Nature, Yitang Zhang proved that there are infinitely many pairs of consecutive primes which are at most 70 million apart! This is a sensational achievement. … Continue reading
QSTART
Physics, Computer Science, Mathematics, and Foundations’ views on quantum information Inauguration conference for the Quantum Information Science Center (QISC), Hebrew university of Jerusalem Update: The news of our conference have made it to a bigleague blog. Update (July 2013): QStart … Continue reading
My Quantum Debate with Aram III
This is the third and last post giving a timeline and some non technical highlights from my debate with Aram Harrow. Where were we After Aram Harrow and I got in touch in June 2011, and decided to have … Continue reading
My Quantum Debate with Aram II
This is the second of three posts giving few of the nontechnical highlights of my debate with Aram Harrow. (part I) After Aram Harrow and I got in touch in June 2011, and decided to have a blog debate about … Continue reading
My Quantum Debate with Aram Harrow: Timeline, Nontechnical Highlights, and Flashbacks I
How the debate came about (Email from Aram Harrow, June 4, 2011) Dear Gil Kalai, I am a quantum computing researcher, and was wondering about a few points in your paper… (Aram’s email was detailed and thoughtful and at the … Continue reading