## Jerusalem and Budapest

Monday, last week was the last day of lectures for the spring term here at the Hebrew U. One outcome of the long professors’ strike was a very fruitful year for research seminars. We ran them during the strike and we run when we taught. I heard about quite a lot of nice developments recently. Zeev Dvir gave a talk on the finite field Kakeya problem. The proof was extremely simple to start with (see Tao’s post ) and Zeev’s presentation was even simpler. It is a very interesting question how, given Dvir’s proof, we should now view the connection between the finite field version of the problem and the original problem. Does Dvir’s proof support the possibility that the original problem is not as hard as feared? Does it support the view that the finite case is not related to the continuous case? (Both Tao and Laba discuss these questions.)

I will tell you in very rough terms (which represent my partial understanding of the matter) one recent wonderful development I heard about. Kolmogorov and Sinai proved that the Entropy is an invariant for Bernoulli shifts under isomorphism. Ornstein celebrated isomorphism theorem asserts that entropy is the only invariant. Orenstein and Weiss studied other group actions, and extended these theorems to amenable groups. There were strong indications that free-group actions behave very differently. (There were examples where the entropy function went the wrong way for “factors”.) However, Lewis Bowen has just shown that for free-group action entropy is an invariant! (OK, I oversimplified matters here for the sake of telling the story.) And he further proved a similar result for all “sofic groups”, a strange notion of groups which is a mixture of amenable and residually finite groups that, as far as we know, may include all groups. Benji Weiss told us about it in the “basic notions seminar”, and a few weeks later another lecture was given by the man himself – Lewis Bowen – who came from Hawaii for a short visit.

And last week I participated in a meeting “Building Bridges” in Budapest honoring Laci Lovász for his birthday. A lot of interesting talks on extremal combinatorics, graph theory, optimization, probabilistic combinatorics, and theoretical computer science. I will come back to this meeting later but let me mention one talk which I found very surprising: Peter Winkler talked about his work with Rick Kenyon on branched polymers. Kenyon and Winkler found startling simple combinatorial proofs to starling results of Brydges and Imbrie, and proved further results. I hope to add a link to the actual presentation. Hungary is the discrete mathematics superpower and on top of that as Einat Wigderson recently made clear “The Hungarians are also much funnier”. It was nice to meet many old friends (and annoy them, at times, with silly jokes). Here is Micky Simonovits and here you can see Endre Szemeredi, Anna Szemeredi, Szemeredi’s jacket and Szemeredi’s tie. I followed the name of the conference and talked about mathematics of social choice.

##

## Plans

We had a few slow weeks on the blog and as the saying goes: “If you cannot do, plan, and if you cannot plan, plan plans.” Together with a little summary of previous posts, I will describe some of the things I plan to write next on this blog.

I plan five posts in the series about Extremal combinatorics. Part I was an introduction to the subject and dealt with extremal set theory. Part II was about simple extremal problems in plane geometry and additive number theory, and about difficult theorems which became quite easy in time. Extremal Combinatorics III will present several basic results in extremal set theory; Part IV will be about POSETS, and part V will present the Frankl-Wilson theorem, or, at least, special cases.

I gave four posts (I, II, III, IV) based on my lecture in Marburg, dealing with high dimensional Cayley formula. Richard Stanley gave a detailed remark on why the fantasy about weighted correct version of MacMahon’s conjecture for solid partitions is not what standard proofs of the plane partition case extend to. I plan a little series of posts on “f-vectors and homology,” which was the title of a paper with Bjorner in 1988 as well as of my talk in Stockholm. However, before that I want to describe the “g-conjecture for spheres” a central problem in algebraic combinaorics.

We had several posts on convex polytopes. I next plan to discuss the diameter problem for polytopal graphs (the Hirsch conjecture) and related questions on the simplex algorithm. (In fact, we already started.) The one proof I presented most often in lectures is my proof of the Blind-Mani theorem that asserts that simple polytopes are determined by their graphs. I will try to blog this proof, tell you some open problems around it, and write about a startling theorem of Eric Friedman who found a polynomial-time algorithm. I also updated the post on five open problems regarding convex polytopes and added two additional problems.

We talked about influence but not about a major technique which emerged in their study: Fourier Analysis of Boolean functions.” So we will discuss Boolean functions and their spectrum, and revisit influences and look at noise-sensitivity. Muli Safra will give a post on the Goldreich Levin theorem and related stuff.

So far our open discussion “Is mathematics a science” attracted a single (nice) comment, and the poem translation contest is still waiting for quality translations. Perhaps we can try an open discussion of a single theorem/problem and see how it goes. Meanwhile, have a look at the very successful discussion on Secret Blogging Seminar about the shy and secretive mathematicians, and how they triumph again and again.

Let’s talk some more on economics and rationality. And about sociel welfare functions and voting methods. We discussed some controversies related to rationality in this post, and the Notices book-review about economics and common sense supplied a source for two posts (1,2). I was just told that along with Landsburg’s book itself, my book review might be translated to Arabic. **Sababa**!

I will tell you about my ideas regarding detrimental noise for quantum computations, but only after trying to describe something about the beautiful, deep, and surprising subject of quantum computation and quantum information. I will not do it before having at least one post about classical computation complexity. Meanwhile, let me link you to the classical post by Aaronson “Reasons to believe” (on why we believe that NP is not P). And while at it, look at “Reason to believe II” (on why many of us believe that quantum computers are feasible.) Read also Bernard Chazelle’s thoughts about alorithms and science.

The most successful link we had so far was Continue reading →