Moshe Vardi: What is Theoretical Computer Science?

080224.OP_.Moshe-Vardi-2400x1350-1

Moshe Vardi wrote a short interesting essay “What is theoretical computer science?” (It followed by interesting posts on Facebook.) Moshe argues that

Thinking of theoretical computer science (TCS) as a branch of mathematics is harmful to the discipline.

I personally do not regard TCS as part of mathematics and I also don’t think that thinking of TCS as part of mathematics is harmful. Certainly there are parts of TCS that are also parts of mathematics as well. (I will try to add a schematic Venn-diagram a bit later.)

Update: Moshe Vardi gave me pointers to two related works: a) The paper FPRAS Approximation of the Matrix Permanent in Practice by James E. Newman, Moshe Y. Vardi argues that the constants in the “rapid mixing” algorithms for approximating permanents are too large to be realistic (related to item 10 below). b) The 2003 paper: Random 3-SAT the plot thickens  describes experiments with SAT solvers on random 3-SATs.  

Here are some unorganized quotes from the essay, my thoughts and related links.

  1. Theory and practice in TCS; my ICM18 paper. Moshe raises interesting issues about the interface between theory and practice in computer science and more broadly in Science and Engineering. This is a topic that greatly interests me and I devoted my ICM18 paper Three puzzles on mathematics, computations, and games, to three examples:  linear programming, voting and games, and quantum computation.
  2. Aesthetic values as a primary motivation. Moshe advises to remember the warning of  John von Neuman regarding the danger of mathematics driven solely by internal esthetics: “There is a grave danger that the subject will develop along the line of least resistance.” (See here for the full quote of von Neuman). Personally, I don’t see alternatives to internal aesthetics as a major driving force on all scales for mathematics.
  3. Physics inspiration. Moshe writes: “As computer scientists, we should look for inspiration from physics rather than from mathematics. Theoretical physics is highly mathematical, but it aims to explain and predict the real world. Theories that fail at this “explain/predict” task would ultimately be discarded. Analogously, I’d argue that the role of TCS is to explain/predict real-life computing.”
  4. Physics heuristic methods. Theoretical physics is characterized by powerful non-rigorous mathematical methods that give amazing predictions. These predictions are quite often confirmed and sometimes refuted. Such methods had some influence for algorithms and theoretical computer science but so far their influence has been limited. One very nice area of applications is the study of algorithms for random SAT problems. Here is a famous 2002 paper Analytic and algorithmic solution of random satisfiability problems by Mézard, Parisi, and Zecchina.
  5.  SAT solvers. Moshe writes:Over the past 30 years, however, we have made tremendous progress in SAT solving, which is today an industrial reality. NP-completeness theory, however, does not explain or predict the unreasonable effectiveness of SAT solvers.”  In my view it is a great problem to understand when and why SAT solvers work. Probably mathematical ideas would be required to study this problem (but everything will go; in my three puzzles paper I suggested the gradual understanding over seven decades of the success of the simplex algorithm as a sort of  role model for understanding the success of SAT solvers). 
  6. Theory and practice: what is a proof? We talked about the practice and theory for proving mathematical theorems in this (sort of) debate between me and Avi Wigderson, and in several other posts (I,II,III).
  7. The very old debate: Karp’s committee vs. Wigderson & Goldreich. There was a related very interesting debate almost thirty years ago that is discussed in this blog post over the blog Computational Complexity (CC) that present the two positions as follows:

    (Karp’s committee:) In order for TOC to prosper in the coming years, it is essential to strengthen our communication with the rest of computer science and with other disciplines, and to increase our impact on key application areas.

    (Oded and Avi’s view:) In order for TOC to prosper in the coming years, it is essential that Theoretical Computer Scientists concentrate their research efforts in Theory of Computing and that they enjoy the freedom to do so. 

  8. Koblitz vs. Goldreich: In the context of Cryptography there was an interesting Koblitz-Goldreich debate, see this post from CC. Cryptography (including cryptanalysis) is a great subject, and I have a long term plan to write about it over here.
  9. The European “Theory A” and “Theory B”. Moshe mentioned that in Europe there are two types of “theoretical computer science” (“Theory A” and “Theory B”). I always found these different possibilities for a scientific theory of computer science quite exciting. Actually, some advances in linear programming (mentioned in my paper quoted above) grew from progress in both “Theory A” and “Theory B”.
  10. Computing volume in high dimensions. (This is a problem I heard from Moshe a decade ago.) Two of the greatest achievements in the theory of algorithms are the polynomial time algorithms for computing volume in high dimensions (Dyer, Friese, Kannan) and for approximating permanents of nonnegative matrices (Jerrum, Sinclair, Vigoda).  Let me mention that the current spectacular world record for volume computations is O^*(N^3) steps by Ben Cousins and Santosh Vempala. The question to be asked is: are there practically good algorithms for these tasks?
  11. Randomness, statistics, and derandomization.  A good place to check theory vs. practice is in the context of randomization. What are the TCS notions of “randomness” and how do they compare in theory and in practice with notions of randomness from probability theory and from statistics? How practical is the theory of “derandomization?”

Moshe’s article is part of the opinion section of the Communication ACM, where Moshe has a regular column. Let me also mention the European counterpart “The Bulletin of the European association of Theoretical Computer Science”

cs-tcs3

A schematic Venn diagram of TCS, CS, Mathematics and other fields. Of course, every field represented here by a circle is by itself a complex fractal-like object. Avi Wigderson’s lovely book “Mathematics and Computation” gives a great description of some mathematical areas of TCS with a special chapter on connections between TCS and mathematics and another chapter on connections between TCS and other sciences. See also this post.

Posted in Applied mathematics, Computer Science and Optimization, Controversies and debates, What is Mathematics | Tagged | 3 Comments

Time for Peace (Song)

Time for Peace” (זמן לשלום), Lyrics: Amnon Abutbul, Yair Dalal, Fathi Kasem; Melody: Amnon Abutbul. Performing Shlomit Aharon and Yevgeni Shapovalov.

This year I had the rare event that the new Jewish year coincides with my birthday, and “time for peace” expresses my wishes for both these occasions.

Click here for the previous post on exciting mathematical irrationality news.

Posted in Poetry | Tagged , , , , | 1 Comment

Celebrating Irrationality: Frank Calegari, Vesselin Dimitrov, and Yunqing Tang Proved the Irrationality of 1/1²-1/2²+1/4²-1/5²+1/7²-1/8²+ …

There are very many irrational numbers but proving irrationality of a specific number is not a common event. A few weeks ago Frank Calegari, Vesselin Dimitrov, and Yunqing Tang posted a paper that proved the irrationality of 

\displaystyle L(2,\chi_{-3}) = \frac {1}{1^2} -\frac {1}{2^2} +\frac {1}{4^2}-\frac{1}{5^2} +\frac {1}{7^2}-\frac{1}{8^2}+\cdots.

In fact they proved even more: that 1, \zeta (2), and  L(2,\chi_{-3}), are linearly independent over \mathbb Q. This is, of course, a fantastic result.

According to the short abstract, “The argument applies a new kind of arithmetic holonomy bound to a well-known construction of Zagier.”

h/t to Ido Kaminer and members of the “Ramanujan machine team” who told about this result in a recent workshop.

Other number theory updates (Oct 26): Hector Pasten proved that the largest prime factor of n^2+1 is at least \log^2n/\log\log\log n. This improved the 1934 \log n bound by Chowla. (Here is a Quanta Magazine article.)  and 2136,279,841-1 is a newly discovered prime (largest known) by Luke Durant. Moving from CPU to GPU not only enabled AI, but also this discovery. (This can give a sense of pride and satisfaction to those enjoying computer games for decades.) 

irrationality

Shana Tova to all the readers: happy new (Jewish) year!

Some more links: Apéry’s 1979 theorem that ζ(3) is irrational. A blog post on Persiflage about the new irrationality result. A videotaped lecture by Frank Calegari.  

Posted in Analysis, Combinatorics, Geometry, Number theory, Rationality | Tagged , , | 1 Comment

Viterbo’s conjecture was refuted by Pazit Haim-Kislev and Yaron Ostrover

Viterbo conjecture – refuted

Claude Viterbo’s 2000 volume-capacity conjecture asserts that the Euclidean (even dimensional) ball maximizes  (every) symplectic capacity  among convex bodies of the same volume. In the recent paper A Counterexample to Viterbo’s Conjecture, Pazit Haim-Kislev and Yaron Ostrover disproved the conjecture. 

Haim-Kislev-Ostrover5

Pazit Haim-Kislev and Yaron Ostrover

We discussed some background on symplectic geometry in this post.  Gromov’s non-squeezing theorem(1985) asserts that a ball of radius R cannot be “squeezed” by a symplectic map to a cylinder whose base is a circle of radius r,  for R > r. 

Gromov’s theorem can be seen as the starting point of a rich theory of symplectic “capacities”.  The main property of a symplectic capacity is that it does not decrease under symplectic embeddings. The theorem immediately led to two definitions of symplectic capacity for one of which the assertion of Viterbo’s conjecture is obvious while for the other it was unknown. The Gromov width of U is the largest radius (in fact, the supremum of radii) of a ball that can be symplectically embedded in U.  The cylindrical capacity is the infimum over all radii of cylinders that U can be embedded into.   

Viterbo further conjectured that all symplectic capacities coincide on convex bodies of dimension 2n. It was known that several symplectic capacities do coincide for convex bodies.  The paper studied the Ekeland–Hofer–Zehnder (EHZ) capacity which refers to different capacities that coincide for convex sets. Their value is related to important properties of billiards; more precisely, Minkowski billiards introduced by Ugene Gutkin and Sergei Tabachnikov. Let me remark that my convexity fellows Dániel Bedzek and Károly Bedzek found a useful way to compute billiard trajectories and, believe it or not, Helly’s theorem plays a role there.  

Remark: Even after our semester long Kazhdan seminar (with Dorit, Leonid, and Guy) on symplectic geometry and quantum computing my intuitions about symplectic capacities are very poor. Experts warned me that symplectic capacities are very different from volume-based measurements. (For example, in the axiomatic definition of symplectic capacities, the “symplectic size” of the infinite cylinder B^2(r) \times C^n is \pi r^2 – in particular, it is finite!) 

The Example

viterbo

The example is a direct product of two pentagons.

Computing symplectic capacities of polytopes

In the paper On the symplectic size of convex polytopes Pazit Haim-Kislev found a combinatorial formula to calculate the symplectic capacity (EHZ) of polytopes (this was her M. Sc. thesis), and in her home page she provides an implementation.

In addition to this computer computation the new paper by Pazit and Yaron provides a short “human” proof for the capacity of the example. 

The connection to Mahler’s conjecture

Some connections to convex geometry were mentioned in this post. The Mahler conjecture asserts that for every centrally symmetric body K

\displaystyle vol (K) vol (K^*) \ge \frac {4^d}{d!},

Here K^* is the polar dual of K. Shiri Artstein-Avidan, Roman Karasev and Yaron Ostrover found in 2013 a remarkable connection to the Mahler’s conjecture:

Theorem (Artstein-Avidan, Karasev, and Ostrover): For centrally symmetric convex bodies the Mahler conjecture is equivalent to the special case of Viterbo conjecture for convex bodies of the form K \times K^*, where K is a centrally symmetric convex body. 

An early paper on from 2006 on the connection between convex geometry and symplectic geometry was written by Shiri Artstein-Avidan, Vitali Milman, and Yaron Ostrover. Here is its short abstract:

In this work we bring together tools and ideology from two different fields, Symplectic Geometry and Asymptotic Geometric Analysis, to arrive at some new results. Our main result is a dimension-independent bound for the symplectic capacity of a convex body by its volume radius.

The connection to the 3ᵈ conjecture and the flag conjecture.

Let K be a centrally-symmetric convex d polytope and let BK be its barycentric subdivisions. I conjectured that f_k(BK) attains its minimum for the d-cube. Two special cases for k=0,d-1 are:

The 3ᵈ-conjecture: Let P be a centrally symmetric d-polytope. Then P has at least 3ᵈ non-empty faces.

The flag conjecture: Let P be a centrally symmetric d-polytope. Then P has at least 2ᵈd! saturated flag of faces. 

Equality for the Mahler conjecture, The 3ᵈ-conjecture, and the flag conjecture are attained for a large class of polytopes called Hanner polytopes (and perhaps only for them). For more on these conjectures see this post.

Dmitry Faifman, Constantin Vernicos, and Cormac Walsh proposed in their paper Volume growth of Funk geometry and the flags of polytopes an exciting conjecture that interpolates between Mahler’s conjecture and my flag conjecture. I hope to come back to this conjecture in a future post.

Could it be that all these conjectures are wrong?

Experts hope (and I certainly share these hopes) that Viterbo’s conjecture holds for centrally symmetric convex domains (as well as Mahler’s conjecture, the 3^d, and the Flag conjecture). But we have to prepare for other possibilities as well. 

 

 

Posted in Convex polytopes, Convexity, Geometry, Open problems | Tagged , , , , | 2 Comments

Timothy Chow’s Amazing Fifteen Boxes Puzzle (TYI 56)

Timothy2

TYI56 asked the following question of Timothy Chow: You have fifteen boxes labelled with the English letters from A to O. Two identical prizes are placed in two (distinct) boxes chosen at random. Andrew’s  search order is  ABCDEFGHIJKLMNO. Barbara’s search order is AFKBGLCHMDINEJO.  (For the full description see the original post.) The first player to hit one of the prizes is declared the winner (ties are possible).

Test your intuition 56: Is Andrew more likely to win this game, or is Barbara? Or are they equally likely to win?

We ran a poll over twitter (589 votes).  The most popular answer by a small margin (45.3%) was that Andrew and Barbara are equally likely to win. I suppose that this reflects several intuitions. One intuition is that the ordering cannot matter but there are simple examples where the ordering does matter. Another intuition is that if the ordering does not matter for one prize then it does not matter for two prizes.  In our poll 41.1% answered that Andrew is more likely to win and 13.6% that Barbara is more likely to win.

The correct answer is that Andrew is more likely to win. It is indeed correct that if there is just one prize, then Andrew and Barbara are equally likely to win.

Below the fold I will tell you more about the origin of the puzzle and some links and also about related puzzles by Daniel Litt.

The origin of the Chow’s puzzle

The puzzle (or, in fact, a small variation) was proposed by Timothy Chow in 2010. Here is the relevant item from Timothy’s home page: Continue reading

Posted in Games, Probability, Riddles, Test your intuition | Tagged | 5 Comments

Pictures from Our 2024 Annual Meeting of the Israel Mathematical Union and Student Day

To me and to many mathematicians in Israel, the Annual meeting of the Israeli Mathematical Union is a dear event and we try to take part. (Here we briefly described the 2017 meeting in Acre, and here the 2014 meeting in Tel Aviv and Ramat Gan.)  In recent years, there was an extra day of students talks. Here are some pictures from the events this year at the Weizmann Institute (and a few additional picture). I took pictures of three main lectures and there were dozens of additional lectures. 

On the train to Rehovot I met Itai Benjamini

IMG-20240908-WA0001

Day I: Misha Sodin’s and Amir Abboud’s lectures

Misha Sodin‘s lecture

20240908_102536

20240908_101031

Misha started his lecture with some sad notes about the hopes of yesterday and the reality of today. He then continued to discuss a fascinating problem in harmonic analysis arising from a discovery of Radchenko and Viazovska. 

20240908_101353(1)

The starting point for Misha’s lecture was the magic function discovered by Viazovska in her proof for the densest sphere packing in eight dimensions. (I wrote about it in this post.) In 2017 Radchenko and Viazovska discovered a remarkable uniqueness result in terms of conditions for the “physical” and Fourier properties of functions. The question was to understand the general Fourier-theoretic phenomenon behind the theorem. 

Amir Abboud’s lecture

Screenshot_20240908_112855_Gallery

Continue reading

Posted in Algebra, Analysis, Computer Science and Optimization | Tagged , , | Leave a comment

Two Events

events2

Israeli Mathematical Union annual meeting and student talks day, Sunday and Monday, September 8 – 9, 2024.

The Annual meeting of the Israeli Mathematical Union will be held on Sunday, September 8th 2024 at the Weizmann Institute. The main speakers will be Misha Sodin and Amir Aboud (the 2024 Erdos Prize recepient). There will also be seven parallel sessions. The IMU student talks day 2024 will be held on Monday, September 9 at the same location. The Day will feature Plenary talks by  Lior Yanovski and by  Ohad Klein  and contributed talks by twenty eight graduate students.

The 2024 Rothschild Prize Symposium, Thursday, 19 September 2024.

The 2024 Rothschild Prize Symposium will be held at the National Library of Israel on 19 September 2024, 9:00-17:00. This year the Rothschild Prize in Mathematics is awarded to Tamar Ziegler and the Mathematical Session of the Symposium features Emmanuel Breuillard, Sarah Peluse, Noam Lifshitz and Amichai Lampert. The Rothschild Prize in Computer Science is awarded to Moni Naor and the CS Session features Omer Reingold, Shafi Goldwasser and Eylon Yogev.  

 

A great lecture by Tammy Ziegler on Mobius Randomness

Posted in Combinatorics, Computer Science and Optimization, Conferences, Number theory | Leave a comment

Test Your Intuition 56: Fifteen Boxes Puzzle

Andrew and Barbara are playing a game. Fifteen boxes are arranged in a 3-by-5 grid, labeled with the letters A through O, as shown below.

A B C D E
F G H I J
K L M N O

The organizers of the game have chosen two boxes randomly and placed a prize in each of the two chosen boxes. (It is the same prize in both boxes.) Andrew and Barbara each secretly submit to the organizers a search order, meaning the order in which they wish to examine the boxes. Andrew decides to search the boxes row by row, from left to right, top to bottom. His search order is therefore ABCDEFGHIJKLMNO. Barbara, however, decides to search the boxes column by column, from top to bottom, left to right. So her search order is AFKBGLCHMDINEJO.

After receiving the two search orders, the organizers now step through the two search orders in parallel. The first player to hit one of the prizes is declared the winner (ties are possible). For example, suppose that K and E happen to be the boxes with prizes in them. Then Barbara will hit the prize in box K on step 3, whereas Andrew won’t hit a prize until step 5, when he reaches box E, so Barbara wins in this case. For another example, suppose that the prizes are in boxes H and N. Then both Andrew and Barbara will hit the prize in box H on step 8, and the result will be a tie. For a third example, suppose that the prizes are in boxes E and G. Then Andrew will reach box E on step 5 and Barbara will reach box G on step 5, and again it will be a tie.

Test your intuition: Is Andrew more likely to win this game, or is Barbara? Or are they equally likely to win?

A poll over Twitter   (update) interesting discussion over facebook.
h/t Timothy Chow

5boxesb

I tried to instruct an AI image creator: “Draw me 15 boxes in three rows with the letters A,B,C,D,… on top of the boxes ordered from left to right, top to bottom”. It gave me four rows of boxes with random letters. (The picture here required editing.) Try for yourself…

Posted in Probability, Riddles, Test your intuition | Tagged , | 41 Comments

Five Perspectives on Quantum Supremacy

 

“Quantum supremacy is important both in its own right and as a benchmark or step toward something further.

But my theory is that quantum supremacy cannot be achieved, and this is based on analysis of the stochastic behavior of samples coming from quantum computers in the intermediate scale. 

It is a bit complicated, but if you take a quantum computer like the ones people build now all over the world, what they produce is a combination of something very sensitive to noise, which is useless for computation, and something stable to noise, which is a very primitive computational device. If you have this combination, you cannot achieve quantum supremacy. This is my theory.” 

— Gil Kalai,

This is an insightful summary by science journalist Anna Kramer of our recent zoom conversation.  Anna interviewed me alongside four other experts – Scott Aaronson, Sergey Frolov, Joseph Emerson, and Shivaji Sondhi for our view on quantum computational supremacy. See this article on “Aventine”. It is one in a series of articles  titled “Five Ways to Think About….”

qs5w

The five views

All of us agreed that achieving quantum computational supremacy is a notable yet elusive goal worth pursuing. Some of us pointed out that despite its grandiose name, it represents a fairly early threshold in the path to quantum computing. None of us offered the view that quantum supremacy has already been achieved (although Scott said that “Quantum supremacy can be achieved and then unachieved later”).

Scott expressed the view that we will eventually reach a place of a firm and decisive quantum supremacy (where it will be achieved on a routine basis). I expressed the opposite view that quantum supremacy cannot be achieved and offered a brief explanation in support of my view. The other three experts did not make firm predictions for the future.

Sergey made a general point about science that “we are given a few years per idea, and then if that doesn’t work, either we fade away or need to come up with a completely different idea for what we might want to do.” This is very different from my experience as a mathematician.

Adding some balance and diversity

Personally, I would have been happy to see female experts among the participants contributing their opinion. To do some justice both to the many eminent women scientists in quantum information theory and to the prevalent optimistic view about the future of this endeavor, I would like to refer the readers to Dorit Aharonov’s brilliant lecture described in this post where, among other very interesting topics,  she shares her optimistic perspective on the future of quantum computing.

Sergey Frolov and I

Of the four other experts I know Scott and Sergey personally. Sergey and I have crossed paths in the context of the replication crisis (aka the reproducibility crisis; it is the fourth item in this post), which is relevant to several experiments in quantum computation (and all over science). In our last meeting in Tel Aviv, Sergey kindly gave me a T-shirt from a recent conference on Reproducibility in Condensed Matter Physics that he organized. 

sergey-gil

Some more details of my view

Here is a somewhat more detailed (but still short) description of my view that I prepared for the interview.

Quantum supremacy refers to demonstrating on a quantum computer something which is extremely hard or even impossible to produce with a classical computer. Achieving quantum supremacy would be a notable landmark on its own and it could also serve well as a useful benchmark (among others) for progress towards the creation of good quality quantum error correcting codes that are needed for large scale quantum computation. In reality, the claims about classical hardness are much trickier than we thought and the claims by Google and other groups from 2019 and 2020 about quantum supremacy were largely refuted. Specific assertions and predictions regarding past and future progress offered by the Google “supremacy paper” also turned out to be false.

The key for both quantum supremacy and quantum error correction are substantially better “quantum gates”. My theory asserts that this is physically impossible and consequently both a convincing demonstration of quantum supremacy and of good quality quantum error correcting codes are not possible. My argument is based on analyzing the stochastic and computational behavior of quantum computers at the intermediate scale. For a large range of error rates the computers will express a combination of computational primitive robust outcomes along noise sensitive components of no use to any computation. This theory will be tested in the next decade and we can expect conflicting and confusing evidence in this period.

The temptation to immaturely present fantastic experimental breakthroughs is large, and, in my view, specific experimental claims should be carefully scrutinized. With Rinott and Shoham I carefully scrutinized the Google 2019 experiment and in view of our study I tend to regard this and other related experiments from 2019/2020 as “mock-up demos” rather than as complete scientific demonstrations. Putting quantum supremacy aside, the question of what can be achieved with superconducting quantum computers in the 10-30 qubit range is still unsettled and specifically, the gap between Google’s and IBM’s experimental claims is not understood.

There are recent interesting experimental claims also for ion trapped quantum computers, neutral atoms quantum computers, and other technologies. These claims should also be carefully scrutinized and in the meanwhile be taken with a grain of salt.

Update: There was a nice discussion over Facebook. Gali Weinstein criticized the term “mock-up” in this context and wrote: “The definition of a scientific experiment is broad, encompassing a wide range of activities, from preliminary investigations to highly controlled and reproducible studies. Even experiments with flaws, limitations, and the need for further refinement still fall within the domain of legitimate science as long as they are conducted with the intent to explore, test, and validate hypotheses using systematic methods.”

More Updates: Phan Ting commented here in the comment section about a new demonstration of quantum error correction by the Google team (and superconducting qubits) using distance-7 surface codes. This is very interesting, and it adds up to earlier quantum error correction and other NISQ experiments that I mentioned at the end of this post.  There is also a new cautiously optimistic post over SO about these developments. 

Update: There is a new very nice blog post Quantum Computing: Between Hope and Hype on “Shtetl Optimized”.

Posted in Computer Science and Optimization, Controversies and debates, Quantum | Tagged , , , , , , | 4 Comments

Test Your Intuition 55: The Case of Two Screening Tests

Here is a great question invented by Michele Piccione and Ariel Rubinstein. (Let me use this opportunity to recommend their mind boggling 1997 paper on the absent-minded driver.)

The question (TYI 55)

The proportion of newborns with a specific genetic trait is 1%. Two conditionally independent screening tests, A and B, are used to identify this trait in all newborns. However, the tests are not precise. Specifically, it has been found that:

70% of the newborns who are found to be positive according to test A have the trait.
20% of the newborns who are found to be positive according to test B have the trait.

Suppose that a newborn is found to be positive according to both tests. What is your estimate of the probability that this newborn has the trait?

I will try to conduct a poll over Twitter (X). (It looks as it is no longer possible to have a poll over here.) Here is going to be the link to the twitter poll. (Seven days only.)

mpar

Michele Piccione and Ariel Rubinstein

Click here for the previous post on Christian Elsholtz, Zach Hunter, Laura Proske, and Lisa Sauermann’s remarkable improvement for Behrend’s construction.

I have a feeling that TYI55 has the potential to be a blockbuster like TYI30 on Mossel’s amazing dice problem.

Continue reading

Posted in Probability, Rationality, Test your intuition | Tagged , | 2 Comments