Recent Comments

Recent Posts
 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
 Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes
 Happy Birthday Ervin, János, Péter, and Zoli!
 My Mathematical Dialogue with Jürgen Eckhoff
 Test Your Intuition (23): How Many Women?
 Happy Birthday Richard Stanley!
Top Posts & Pages
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 Believing that the Earth is Round When it Matters
 Mathematical Gymnastics
 Media Item from "Haaretz" Today: "For the first time ever..."
 Why Quantum Computers Cannot Work: The Movie!
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 Analysis of Boolean Functions
 Two Math Riddles
 The Ultimate Riddle
RSS
Author Archives: Gil Kalai
Simons@UCBerkeley
Raghu Meka talking at the workshop I spend the semester in Berkeley at the newly founded Simons Institute for the Theory of Computing. The first two programs demonstrate well the scope of the center and why it is needed. One program … Continue reading
Posted in Conferences, Updates
1 Comment
Analysis of Boolean functions – week 2
Post on week 1; home page of the course analysis of Boolean functions Lecture II: We discussed two important examples that were introduced by BenOr and Linial: Recursive majority and tribes. Recursive majority (RM): is a Boolean function with variables … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching
Tagged Boolean functions, Tribes
Leave a comment
Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture
Borsuk asked in 1933 if every bounded set K of diameter 1 in can be covered by d+1 sets of smaller diameter. A positive answer was referred to as the “Borsuk Conjecture,” and it was disproved by Jeff Kahn and me in 1993. … Continue reading
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
Open Collaborative Mathematics over the Internet – Three Examples
After much hesitation, I decided to share with you the videos of my lecture: Open collaborative mathematics over the internet – three examples, that I gave last January in Doron Zeilberger’s seminar at Rutgers on experimental mathematics. Parts of the 47minutes … Continue reading
Poznań: Random Structures and Algorithms 2013
Michal Karonski (left) who built Poland’s probabilistic combinatorics group at Poznań, and a sculpture honoring the Polish mathematicians who first broke the Enigma machine (right, with David Conlon, picture taken by Jacob Fox). I am visiting now Poznań for the 16th … Continue reading
Posted in Combinatorics, Conferences, Open problems, Philosophy, Probability
Tagged Poznan, RSA
Leave a comment
BosonSampling and (BKS) Noise Sensitivity
Following are some preliminary observations connecting BosonSampling, an interesting computational task that quantum computers can perform (that we discussed in this post), and noisesensitivity in the sense of Benjamini, Schramm, and myself (that we discussed here and here.) BosonSampling and computationalcomplexity hierarchycollapse Suppose that … 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
Auctionbased Tic Tac Toe: Solution
Reshef, Moshe and Sam The question: (based on discussions with Reshef Meir, Moshe Tennenholtz, and Sam Payne) Tic Tac Toe is played since anciant times. For the common version, where the two players X and O take turns in marking … Continue reading
Some old and new problems in combinatorics and geometry
Paul Erdős in Jerusalem, 1933 1993 I just came back from a great Erdős Centennial conference in wonderful Budapest. I gave a lecture on old and new problems (mainly) in combinatorics and geometry (here are the slides), where I presented twenty … Continue reading