First third of my ICM2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

Update: Here is a combined version of all three parts: Three puzzles on mathematics computations and games. Thanks for the remarks and corrections. More corrections and comments welcome.

I have a very strict December 20 deadline (self-imposed, I missed the official one)  for my ICM2018 paper. I plan to talk about three puzzles on mathematics, computation and games, and here is a draft of the first third. Corrections and comments are very welcome! This part is around the simplex algorithm for linear programming.


This entry was posted in Combinatorics, Computer Science and Optimization, Games, Updates and tagged . Bookmark the permalink.

12 Responses to First third of my ICM2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

  1. B. says:

    A very non-scientific comment: Your figures would be better if they were vectorial. Figure 3 looks very good, but Figure 1 only “quite good” and Figure 2 is really of bad quality. That is a shame to my taste that while using a very good quality typography through LaTeX you have non-professional-looking pictures!

    • B. says:

      And for a more scientific one: I feel that Spielman and Teng’s smooth analysis is strong evidence for the practical good behavior of the Simplex algorithm. In contrast, your paper gives the impression that the implications of this result are not so preeminent in the explanation for the good behavior. I would appreciate a lot if you could clarify this point!

    • Gil Kalai says:

      Very many thanks! In my view figures are very important. Actually I have better versions for Figure 1 and 3 but figure 2, I prepared myself with “paint.” It is better than figures I prepared for the other parts so I dont know what to do. (And I dont know even what vectorials mean.)

      • Johanna Steinmeyer says:

        I quite enjoy using TikZ, so I quickly drew something up for figure 2. You are welcome to use it and edit it (so long as you don’t tell my advisor that I spent time on this rather than writing my own paper).

        Here is the folder:

        If you include it into a document with code that looks something like this


        you will get nicely crisp images no matter how far you zoom in. That’s the nice part with vector graphics (svg, pdf), whereas with a file type using pixels (png, jpg) you may end up seeing those pixels in the document.

      • B. says:

        [Vector graphics]( describe a figure by vectors rather than bitmaps. The consequence is that you can zoom as much as you want (on a computer) without viewing the pixels. For printing, this means that the printer will “choose” the resolution based on its pixel size, so that you visually get lines and curves, not sequences of pixels.

      • Hi Gil. Instead of tinkering with the TikZ code directly, you can also consider using Geogebra ( for drawing pictures, which is almost as easy to use as paint, and in the end it gives you a TikZ code that you can copy paste to your latex file. (see this:

    • Gil Kalai says:

      Hi B. I did elaborate and evaluate on Spielman and Teng’s smooth analysis of LP in this paper and I think what I write in the present paper is consistent with the old one. (If not tell me!) In this new paper I zoom in on other developments. Certainly, the results by Spielman and Teng are great! As for the questions “what is the most preeminent explanation? and what is the quality of the overall explanation?” – those are very interesting… but for after the deadline 🙂

      One more remark: The chapter is about questions that directly or indirectly arose from an attempt to understand the success of the simplex algorithm, but these questions have interest and importance on their own and for other purposes. For example, in the list I made of 16 developments or so the one that I would regard as scientifically most important is perhaps Karmarkar’s interior point method, not for the added value in explaining the success of the simplex algorithm but because this was a new algorithm which in some cases compete well with the simplex (and the competition did well for both) and which dramatically changed both the theoretical and practical LP reality.

      • B. says:

        I did not know your other paper. I did not find any inconsistency! If I understand correctly, the aim of the present paper is to give one possible (set of) explanation(s) for the efficiency of the Simplex algorithm, and not all of them. Maybe my only concern is that this goal is not stated clearly enough, and I read the title of the puzzle as “let me give you all the known explanation for the good behavior of the simplex.” Well, you give them in the list so my comment is maybe irrelevant. 😉

        (I would be very much interested by your take on the after-deadline questions!)

      • Gil Kalai says:

        Hi B. , “let me give you all the known explanation for the good behavior of the simplex.”
        yes this is in the list (explanations and counter-explanation that I am aware of). I elaborated on topics which are closer to my research. All chapters are meant to describe mathematics which is either related or trigerred by the puzzle.

        For example, for me the question about diameters of polytopes is as interesting on its own right as the question on the simplex algorithm. The simplex algorithm have led Hirsch to the diameter question but different people have different views on the relevance.

  2. I would suggest defining the term “active facet” before using it.

  3. Yuzhou Gu says:

    Typo in bottom of page 4: (10) LP algorithms in fixed dimension. Megiddo (1984) was the first to find for a fixed value of d a linear time algorithm for LP problems with d variables and n variables.

    Should be n inequalities.

  4. Gil Kalai says:

    Dear Omar and Yuzhou, many thanks! I

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s