Tokyo, Kyoto, and Nagoya








Kalai-stanley

Near Nagoya: Firework festival; Kyoto: with Gunter Ziegler; with Takayuki Hibi, Hibi, Marge Bayer, Curtis Green and Richard Stanly; Tokyo: Peter Frankl; crowded crossing. Added later: Mazi and I at the same restaurant taken by Stanley.

I just returned from a trip to Japan to the FPSAC 2012 at Nagoya and a workshop on convex polytopes in Kyoto. As in my first visit to Osaka in 1999 I found Japan stunning, and this time I was able to share the experience with my wife.

Kyoto: The week before FPSAC there was a workshop at RIMS devoted to convex polytopes. Some highlights: A classical result by Venkov and McMullen characterizes polytopes whose translates tile the Euclidean d-space.  Sinai Robins talked about his work with Nick Gravin and Dima Shiryaev about k-tilings (every point is covered k times).  Not a full characterization yet but already some impressive results. Gunter Ziegler talked about his work with Karim Adiprasito disproving an old conjecture by Shephard which asserts that there are only finitely many projectively unique d-polytopes for every dimension d. This is false above dimension 81.  Eran Nevo talked about his solution with Satoshi Murai of the generalized lower bound conjecture and some subsequent works on triangulated manifolds. There were several talks relating Ehrhard polynomials of polytopes with enumerative combinatorics,  and several talks on algebraic geometry, toric varieties, Fano varieties, and mirror symmetry. Here are the slides of my lecture entitled open problems on convex polytopes I’d love to see solved (but some further explanations for some parts are needed). I hope to return to some of the topics of the workshop in a later post.

Nagoya: FPSAC (Formal power series and algebraic combinatorics) is a central annual  combinatorial meeting with special emphasis on enumerative and algebraic combinatorics. This year it was the 24th such event although I could have swear that I took part in an FPSAC in Montreal already in 1985 but apparently this was a conference with a similar flavor and different name. Much is going on in enumerative and algebraic combinatorics. Cluster algebras, miraculously discovered a decade ago by Fomin and Zelevinsky are going strong in combinatorics as well as in other areas. Alternating sign matrices continue to offer amazing problems and answers. There were quite a few lectures on representation theory, symmetric functions, random matrices, and also on relations of enumerative combinatorics with hyperplane arrangements with polytopes and with physics. There were lectures involving massive computations and new computerized method and packages for symbolic computations  were described. Here are the slides of my lecture entitled Discrete isoperimetry: problems, results, applications and methods. The program page now contains slides for most lectures.

What are alternating sign matrices?

I suppose that you all know what a permutation matrix is (an n by n matrix with 0,1 entries and one non zero entry in each row and each column) and alternating sign matrices are amazing generalization of permutation matrices discovered by William Mills, David Robbins, and Howard Rumsey. (See also this article by Bressoud and Propp) They are integral n by n matrices with 0,1 and -1 entries. In every row and every columns  the non zero aliments (and there must be at least one such element)  should alternate between 1 and -1 and start and end with a ‘1’. Alternating sign matrices are in one to one correspondence with monotone triangle. Thos are triangles of integers starting with a row: 1,2,…,n. With the following rules: (a) all rows are strictly increasing; (b) every element in row i is weakly between the two elements above it.

The amazing thing is that the number of alternating sign matrices of order n is precisely

1!4!7!…(3n-2)!/n!(n+1)!…(2n-1)!

This was a conjecture by Mills, Robbins and Rumsey and it took over a decade until it was proved by Doron Zeilberger. Later Greg Kuperberg found a short proof and by now several proofs are known. If you have some information or ideas on alternating sign matrices that you would like to share or some questions about them, or about anything else, please contribute a comment.

Celebrations in Bar-Ilan, HU, and the Technion; A new blog: Windows on Theory; Turing’s celebration on “In Theory”; Graph Limits in Princeton

Last monday we had the annual meeting of the Israeli Mathematical Union (IMU) that took place this year in Bar-Ilan University in Ramat Gan. (IMU is famously also the acronym of the International Mathematical Union but in this post IMU will stand for “Isreali Mathematical Union.”) The first IMU meeting that I participated was in 1972 and I try to participate every year.  One year, Nati Linial and me were the treasurer and secretary of the IMU and were assigned (by the IMU president at the time, Yisrael Aumann) the task of organizing the meeting. The IMU meetings have different formats and usually they are very successful and this year was no exception. So I will tell you a little more about it later. Five more short items for today:

  1. Last Wednesday two new research centers were inaugurated. Here at the Hebrew University of Jerusalem the new Quantum Information Science Center  had its kick-off workshop on Wednesday. Here are the slides of the lecture I gave  devoted to my debate with Aram Harrow. (As always, remarks and corrections are most welcome.)
  2. In Haifa at the Technion , the newly founded Technion-Microsoft Electronic-Commerce Research Center held a one day workshop on electronic-commerce .
  3. There is a new research blog Windows on Theory devoted to research in theoretical computer science. It is run by theory people from Microsoft Research, most from the Silicon Valley. The last post mentioned a nice story of Ehud Friedgut about hitting a rotating sphere from a 1997 paper of mine.
  4. Last month, Luca Trevisan was the Erdos’ Lecturer of the center for Discrete Mathematics and Theoretical Computer Science, here at HU. Luca is one of the world leaders in theoretical computer science and also the author of a famous blog: In Theory.   Luca Trevisan’s blog’s celebration of Alan Turing’s 100th birthday, spanned over several posts,  will be devoted to a big part of Turing’s life  – being gay.
  5. Starting on monday: A conference on graph limits (“Graphs and Analysis“) at IAS, Princeton. Many great talks are expected. Our blog is negotiating with Itai Benjamini for letting us post the slides of his lecture on Euclidean versus graph metrics.

The Bar-Ilan Meeting

David Kazhdan gave a talk about the classic master equation.

The abstract of his lecture read:

We formalize the construction by Batalin and Vilkovisky of a solution of the classical master equation associated with a classical action, a regular function on a nonsingular affine variety. We introduce the notion of stable equivalence of solutions and prove that a solution exists and is unique up to stable equivalence. A consequence is that the associated BRST cohomology groups are independent of choices and are uniquely determined up to unique isomorphism by the classical action.

David, however, decided to give a talk about the background to a talk described in the abstract. He gave a quick mathematical introduction to classical and quantum mechanics, leading to the Faddeev-Popov method, described in as elementary and jargon-free as possible  differential geometry language. Beautiful talk!

Let’s glimpse at the lecture: Quantum mechanics is about calculating integrals of the form \int_X e^{is(x)/h} \nu (x). While classical mechanics is the study of the stationary points of s(x). (In cases where the stationary point is unique, the derivative at a stationary point x_0 is well-defined and the Hessian is non-zero, and other pleasant things occur  we can approximate the integral by a normalized value of s(x_o).)

When there is a group G (gauge symmetry) acting on X  then we can try to make the computation on the quotient X/G . (This computation leads to expansion in terms of Feynman diagrams.) Faddeev-Popov method is based on the idea: don’t take quotients but rather enlarge your space! So you replace X by the Cartesian product of X with the associated Lie algebra of G. (Here, a structure of a “supermanifold” emerges.) At this point a) some differential geometry enters into the picture, b) this allows to the master equation promised in the title to emerge, and c) The computation has some cohomological nature.

After David’s talk Jonathan Wahl gave a talk  on Topology versus geometry of complex singularities. There is a famous book by Milnor on this topic and a lot have been learned since. Then there was a brief prize awards session. Our annual  Erdos’ prize for a mathematician under 40, was awarded to Irit Dinur, and the Haim Nessiyahu prize for excellent doctoral thesis was awarded to Alexander Sodin on his work on random matrices.  Ran Raz gave a talk about PCP and, in particular, on Irit’s contribution.  This is the 20th anniversary of the PCP Theorem. Heartily Congratulations to Irit and Sasha.

And then we separated into ten parallel sessions: Algebra and number theory; Analysis; Discrete Math and Computer Science; Dynamics and Ergodic Theory;  History and Philosophy of Mathematics; Homotopy Theory;  Mathematical Education; Topology and Geometry; Probability; Nonlinear Analysis and Optimization. To avoid being torn between too many good options my policy is usually to stay with the combinatorics session. But this year since my flight was brutally delayed and I landed only at five in the morning I had to choose the option of going home to sleep.

 

Celebrations in Sweden and Norway

Celebrations for Endre, Jean and Terry

Anders Bjorner presents the 2012 Crafoord Prize in Mathematics 

I am in Sweden for two weeks to work with colleagues and to take part in two celebrations. Jean Bourgain and Terence Tao are the 2012 laureates of the Crafoord Prize in mathematics which was awarded  last Tuesday at Lund. Along with them the 2012 Crafoord Prize in Astronomy was awarded to Reinhand Genzel and Andrea Ghez.  I took part in the symposium entitled “From chaos to harmony” to celebrate the event.

Next Friday the Swedish Royal academy will celebrate with a mini-symposium in honor of the 2012 Abel prize winner Endre Szeméredi. (Here are the slides of my future talk looking at and around the Szeméredi-Trotter theorem. Please alert me of mistakes if you see them.) The Abel prize symposium and ceremony in Oslo are  Tuesday (Today! see the picture above) and Wednesday of this week.

(Copyright: Crafoord foundation.)

Congratulations again to Jean, Terry and Endre for richly deserved awards.

Crafoord days at Lund

Owing to the passing of Count Carl Johan Bernadotte af Wisborg, H.M. King Carl XVI Gustaf was unable to attend the Crafoord Days 2012. The prizes were presented by Margareta Nilsson, daughter of the Donors, Holge and Anna-Greta Crafoord. Ms Nilsson’s kind hospitality, deep devotion to science, culture and other noble social causes, and moving childhood memories shared at the dinner,  have led Reinhard Genzel in his moving speech on behalf of the winners in Astronomy to refer to Margareta Nilsson by the words: “You were our King these past two days!”.

The one day symposium itself was very interesting, and so were the four prize lectures on Tuesday morning. In a few days The videos of the two days’ lectures will be are posted here. Here are the slides of my talk on analysis of Boolean functions, featuring, among other things a far-reaching conjectural extension of a recent theorem by Hamed Hatami.

Gothenburg and Stockholm

From Lund I continued to a short visit of Gothenburg hosted by Jeff Steif with whom I share much interest in noise sensitivity and many other things. I then continued to Stockholm where I visit Anders Björner who is a long-time collaborator and friend since the mid eighties. For me this is perhaps the twelfth visit to Stockholm and it is always great to be here.

We will celebrate on this blog these exciting events with a rerun of the classic, much-acclaimed piece by Christine Björner on the Golden room and the golden mountain.

Speakers at Crafoord symposium, (from right to left) Carlos Kenig, Ben Green, Jean Bourgain, Terry Tao, me and Michael Christ. Copyright: Crafoord foundation.

 

Update(Oct 2014): Here is a picture of me and  Jean at IHES 1988

JeanGil88

Günter Ziegler: 1000$ from Beverly Hills for a Math Problem. (IPAM remote blogging.)

Scanned letter by Zadeh. (c) Günter M. Ziegler

left-to-right: David Avis, Norman Zadeh,  Oliver Friedmann, and Russ Caflish (IPAM director). Photo courtesy Eddie Kim.

Update: The slides for Friedmann’s talk are now available. The conference schedule page contains now the slides for most presentations.

This post is authoured by Günter Ziegler with some help by David Avis. A German (slightly expanded) version can be found on Günter’s blog.

Oliver Friedmann, a Computer Science graduate student at Munich University, will defend his thesis next month. It contains a proof, that “Zadeh’s rule” for linear optimization is “exponential”, that is, it may take an awfully long time on relatively small problems.

 

Why is this remarkable?

“Linear Optimization” problems are extremely important computational tasks that arise in all kinds of larger planning processes. Such tasks are usually solved on a computer using a method known as the “simplex algorithm”, invented by George Dantzig in 1947. The simplex method needs a prescription for making local choices in its search, known as the “pivot rule”. And it is known about mostsuch pivot rules that they can be extremely slow and inefficient on particular optimization problems. One would like (and need) a rule that is “provably fast”.

One candidate for this was the “Zadeh rule” — until today. When Zadeh was a postdoc in the Department of Operations Research at Stanford he published a technical report on the worst case examples of the simplex method. Continue reading

IPAM Remote Blogging: Santos-Weibel 25-Vertices Prismatoid and Prismatoids with large Width

Here is a web page by Christope Weibel on the improved counterexample.

The IPAM webpage contains now slides of some of the lectures. Here are Santos’s slides. The last section contains some recent results on the “width of 5-prismatoids”  A prismatoid is a polytope with two facets containing all the vertices. The width of a prismatoid is the number of steps needed to go between these two facets where in each step we move from a facet to an adjacent one. Santos’s counterexample is based on findng 5-dimensional prismatoid with width larger than 5. It is observed that the width of a 5-prismatoid with n vertices cannot exceed 3n/2 and it is shown (by rather involved constructions) that there are examples where the width is as large as \sqrt n.

Remote Blogging: Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?

Here are some links and posts related to some of the talks in IPAM’s workshop “Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?” I will be happy to add links to pdf’s of the presentations and to relevant papers. Descriptions and remarks on individual lectures are very welcome. In particular you are most welcome to post here the posters/abstract/papers from the poster session. (Because of some technical matters I will have to miss the workshop. I hope to be able somehow to follow it from far away.)

Following is a description of some of the lectures and some useful links for a few lectures:

A counterexample to Hirsch’s conjecture: Posts related to Paco Santo’s lecture (Tuesday morning) describing a counter example to Hirsch’s conjecture are here and here The second post contains a link to Paco’s paper. Fred Holt’s second lecture will describe some new consequence to Paco’s construction. 

Acyclic USO: Acyclic unique sink orientations (Acyclic USO) of cubes and more general polytopes are mentioned in this post about abstract linear objective functions as well as this one about telling simple polytopes from their graphs. Acyclic USO are mentioned discussed in David Avis’s Wednesday morning talk and a few others.

Stochastic games: Stochastic games relevant to Yinyu Ye’s and Oliver Friedmann’s Thursday morning talks are discussed in this post. Some background (and links to the papers) for the new subexponential lower bounds for randomized pivot rules that will be described in Friedmann’s lecture can be found in this post. 

Polynomial Hirsch conjecture: Ed Kim’s (Thursday afternoon) and Nicolai Hähnle’s  (Friday’s morning) talks are related to polymath3. David Bremner will discuss (Tuesday afternoon) the combinatorics and geometry of path complexes. Jonathan Kelner will propose (Friday morning) a geometric/probabilistic method based on smoothed analysis to attack th epolynomial Hirsch conjecture.

Bad behavior of the simplex algorithms. Examples for the bad behavior of simplex type algorithms (mainly in three dimensions) will be described in Günter Ziegler’s talk (Tuesday afternoon). Here is the link to Günter’s slides which are rather detailed. Bernd Gärtner (Wednesday morning) will demonstrate how Goldfarb’s cubes can be used to refute a conjecture regarding an algorithm for machine learning. 

Interior point methods: Since the mid 80s interior point methods for linear programming are as important theoretically and practically as simplex type algorithms. (I will add a link for a good wide-audience description of interior point methods HERE.) Jim Renegar’s Thursday afternoon lecture will describe some new advances on  Central Swaths (a generalization of the central path a central notion for interior point methods. ) Santosh Vampala closing lecture will propose a hybrid vertex-following interior-type algorithm.

Continuous analogs: There are several interesting continuous analogs for combinatorial notions and questions related to the simplex algorithms. Yuriy Zinchenko will discuss (Wednesday afternoon) continuous analogs of the Hirsch conjecture

Walking on the arragements: Consider the entire arrangement of hyperplanes described by the inequalities of an LP problem. The simplex algorithm can be described as a walk on vertices of this arrangements. Those are very special vertices – the vertices of the feasible polyhedron. The dual simplex algorithm can also be described as a walk on vertices of the arrangement. This time the relevant vertices (I think) are dual-feasible, namely those are vertices of the arrangement which optimize the objective function w.r.t. a subset of the inequalities.  What about LP algorithms based on more general type of walks?  Kumei Fukuda Thursday’s afternoon talk will discuss this issue.  

A new polynomial LP algorithm:  Sergei Chubanov (Thursday afternoon) will propose a strongly polynomial relaxation-type algorithm which either finds a solution of a linear system or decides that the system has no 0,1-solutions. If the system is feasible and the bounds on variables are tight, the algorithm always finds a solution. Sergei will continue to show that the algorithm can be used as the basis for the construction of a polynomial algorithm for linear programming. Here is a link to the paper. Tamás Terlaky (Wednesday afternoon) will review several algorithms for linear programming including elimination and pivot algorithms, interior point methods and the perceptron algorithm.

Complexity of Delaunay Triangulation:  Nina Amenta’s Friday talk will describe what we recently learned about the the complexity of Delaunay triangulations as function of the distribution of their vertices, and will raise the question “how much of this can be applied to polytopes in general?”

Among the additional presentations: Christophe Weibel presented an improvement to Paco Santos’ counterexample. Jésus de Loera presented a paper with Bernd Sturmfels, and Cynthia Vinzant on the centeral curve in linear programming.

  

 

To Life, to Science and to Innovations

ICS2011 at ITCS, Tsinghua University, Beijing, China

The title of this post “To life, to Science and to Innovations” was Silvio Micali’s toast at the second conference on Innovations in Computer Science and Silvio’s words have a good chance of becomeing the official toast of this emerging event.  ICS2011 which took place in Beijing was a very interesting conference, and ITCS at Tsinghua University is a great research institute. I completely share the sentiments and excitements of Noam Nisan’s (who is freezing with me against the background of the forbidden city in the picture below) about ITCS from this post from June 2009. 

My talk entitled “Influence and Noise” was meant to be (to the horror of some friends, perhaps as much horror as was elicited by my outfit) even more non-technical than the talk shown at this post. I tried to avoid formulas at all costs. (But formulas are fairly efficient, I must say. Explaining things in words is lengthier.) The planned five parts of the talk were: I. Cause and influence, II. Choice, power, and manipulation, III. Randomness, IV Noise and V Computational complexity. This was too ambitious and I ended in the middle of IV.  Here are the slides. (Additional verbal explanation is needed for quite a few slides.)

In the last evening of the meeting after Bernard Chazelle and Amy Yuexuan Wang sang a Chinese song together, it was time for a new innovation: singing TCS-oriented songs. Clearly, the Rolling Stones’ “I Can Get No Satisfaction” refers to 3-SAT and the NP \ne P problem and, twenty years after our first public appearance, Bernard and I sang this song adding background voices “because P is not equal to NP”.  Then Peter Bro Miltersen joined us for “when I will be 2^6“.

Budapest, Seattle, New Haven

Here we continue the previous post on Summer 2010 events in Reverse chronological order.

Happy birthday Srac

In the first week of August we celebrated Endre Szemeredi’s birthday. This was a very impressive conference. Panni, Endre’s wife, assisted by her four daughters, organized a remarkable exhibition by mathematicians who are also artists. Panni also organized tours and activities for accompanying people which my wife told me were great. A few mathematicians chose to attend the tours rather than the lectures. In Hungary, Endre has a nickname “Srac” which means “kid”, and, to my amazement, people (including young people) really call him Srac.

Szemeredi Kati and Zsuzsa

After-dinner speech. The distinction between surprising and amazing, and the question of do we age when it comes to our emotions and inner soul experiences

Being asked to give the after-dinner speech for Endre in the festive boat dinner ranks second in my life among cases where I was chosen for a job for which so many others were much, much more deserving and qualified. Continue reading

Mabruk Elon, India, and More

I am starting this post in Jaipur. My three children are watching a movie in our Jaipur hotel room and I watch them while I begin to write this post. Hagai is in the middle of a long-planned three-month trip to India, and when I told my family about the ICM in Hyderabad, my two other children Neta and Lior jumped at the opportunity, and decided to come to India for three weeks, and in the last week give me a taste of India.  Hagai started his visit in Leh and experienced the flooding there. By the time we heard about it, already two days after the flooding, the Israeli foreign office’s emergency room had already made contact with the Israelis in Leh, including Hagai.  Hagai decided to stay in Leh to help clean houses and (mainly) the local hospital of the huge amounts of mud. He spent almost a month there and took a bus to meet me at Delhi. Neta and Lior were in Hampi, before we all met in Agra.

India is overwhelming and I do not even begin to comprehend her. Perhaps it will be easier to comprehend why so many young Israelis fall in love with India.

In this post (which I split to two parts), I wish to describe some of my Summer 2010 excitements in reverse chronological order.

Before that, here are the slides of my lecture on combinatorial and topological aspects of Helly-type theorems from the Szemeredi birthday conference, and my laudation paper and lecture slides on Dan Spielmen’s work from ICM 2010.

ICM 2010, India

Monday evening was the end of the fourth day in ICM 2010. ICM stands for the International Congress of Mathematicians. This is an event that has taken place once every four years for over a century. This was the second meeting of the Combinatorics session featuring Henry Cohn, Brendan McKay and Benny Sudakov as invited speakers.  It was followed by a session of short 15-minute communications in combinatorics. Laci Lovasz, the president of IMU, had a lot on his mind in these four days. Due to his duties he had to miss many important lectures and events, but he nevertheless set aside time to attend this “contributed talks” session and I found it very nice. Continue reading