A Discussion and a Debate

Heavier than air flight of the 21 century?

The very first post on this blog entitled “Combinatorics, Mathematics, Academics, Polemics, …” asked the question “Are mathematical debates possible?” We also had posts devoted to debates and to controversies.

A few days ago, the first post in a discussion between Aram Harrow, a brilliant computer scientists and quantum information researcher (and a decorated debator), and myself on quantum error correction was launched in Dick Lipton and Ken Regan’s big-league blog, Gödel’s Lost Letter and P=NP.

The central question we would like to discuss is:

Are universal quantum computers based on quantum error correction possible.

In preparation for the public posts, Ken, Aram, Dick, and me are having very fruitful and interesting email discussion on this and related matters, and also the post itself have already led to very interesting comments. Ken is doing marvels in editing what we write.

Dick opened the post by talking on perpetual motion machines which is ingenious because it challenges both sides of the discussion. Perpetual motion turned out to be impossible: will quantum computers enjoy the same fate? On the other hand (and closer to the issue at hand), an argument against quantum mechanics based on the impossibility of perpetual motion by no other than Einstein turned out to be false, are skeptical ideas to quantum computers just as bogus? (The answer could be yes to both questions.) Some people claimed that heavier-than-air flight might is a better analogy. Sure, perhaps it is better.

But, of course, analogies with many human endeavors can be made, and for these endeavors, some went one way, and some went the other way, and for some we don’t know.

Although this event is declared as a debate, I would like to think about it as a discussion. In the time scale of such a discussion what we can hope for is to better understand each other positions, and, not less important, to better understand our own positions.  (Maybe I will comment here about some meta aspects of this developing discussion/debate.)

A real debate

A real emerging debate is if we (scientists) should boycott Elsevier. I tend to be against such an action, and especially against including refereeing papers for journals published by Elsevier as part of the boycott. I liked, generally speaking,  Gowers’s critical post on Elsevier, but the winds of war and associated rhetoric are not to my liking.  The universities are quite powerful, and they deal, negotiate and struggle with scientific publishers, and other similar bodies, on a regular  basis. I tend to think that the community of scientists should not be part of such struggles and that such involvement will harm the community and science. This is a real debate! But it looks almost over.  Many scientists joined the boycott and not many opposing opinions were made. It looks that we will have a little war and see some action. Exciting, as ever.

Gina Says Part two

Download the second part of my book “Gina Says.”

Link to the post with the first part.



 “Gina Says,”

Adventures in the

Blogosphere String War

selected and edited by Gil Kalai


Praise for “Gina Says” 


After having coffee  at the n-category cafe,  Gina moved to  Clliford Johnson’s blog “Asymptotia” where she mainly discussed Lee Smolin’s book “The Trouble with Physics.”

Among the highlights:  Too good to be true (Ch 17); Dyscalculia and Chomskian linguistics (Ch 19); Baker’s fifteen objections to “The Trouble with Physics” (Ch. 25); Maldacena (Ch. 28);  High risks endeavors for the young (Ch 31);How to treat fantastic claims by great people (Ch. 33); Shocking revelations (Ch. 38); How to debate beauty (Ch 41.)

Some little chapters appeared also as posts: Continue reading

Alarming Developments In Tel Aviv University

Update (July 24): A detailed new article in Hebrew and English.

Dr. Leora Meridor, who replaced  Dov Lautman in March (just four months ago)  as chair of TAU’s executive council is quoted saying: ” I’d give him (Zvi Galil) a list of things that had to be done, and nothing would happen.” and “In such a situation, you can’t just keep on doing what was done before, only to a lesser extent. You have to make decisions: what should be severed with one sharp blow, and what should be strengthened. This is the ABC of management.”

Again, I should repeat that even direct quotes taken from a newspaper are not always accurate. If accurate,  a management style of executive counsil chairperson who gives the president of the university  a “to do list, ” expects him to “close units with one sharp knife blow” (here I translate from the Hebrew version) and fires him within three month at office, is highly unorthodox.    


Look at these articles:

(English)   http://www.haaretz.com/hasen/spages/1096958.html

(Hebrew) http://www.haaretz.co.il/hasite/spages/1096752.html

A follow-up article in Hebrew:

(Hebrew) http://www.haaretz.co.il/hasite/spages/1097204.html

(I did not find the English version of the second article.)

The articles discuss the recent resignation of Tel Aviv University’s president Zvi Galil. They mention changes in the institution’s constitution which reduced the authority of academic staff in the university administration in favor of “representatives of the public,” primarily businesspeople. The new provisions, claim the articles, reduce the number of votes needed to cut short the term of the university president.

Disclaimer: Not everything written in a newspaper is correct.

Remark: The issues which are debated in Israel regarding governance of the universities and related matters are similar in nature to trends in various other places. Continue reading

Chess can be a Game of Luck


Can chess be a game of luck?

Let us consider the following two scenarios:

A) We have a chess tournament where each of forty chess players pay 50 dollars entrance fee and the winner takes the prize which is 80% of the the total entrance fees.

 B)  We have a chess tournament where each of forty chess players pay 20,000 dollars entrance fee and the winner takes the prize which is 80% of the the total entrance fees.

Before dealing with these two rather realistic scenarios let us consider the following more hypothetical situations.

C) Suppose that chess players have a quality measure that allows us to determine the probability that any one player will beat the other. Two players play and bet. The strong player bets 10 dollars  and the waek player bets according to the probability he will win. (So the expected gain of both player is zero.)

D)  Suppose again that chess players have a quality measure that allows us to determine the probability that any one players will beat the other. Two players play and bet. The strong player bets 100,000 dollars and the weak player bets according to the probability he will wins. (Again, the expected gain of both players is zero.)

When we analyze scenarios C and D the first question to ask is “What is the game?” In my opinion we need to consider the entire setting, so the “game” consists of both the chess itself and the betting around it. In cases C and D the betting aspects of the game are completely separated from the chess itself. We can suppose that the higher the stakes are, the higher the ingredient of luck of the combined game. It is reasonable to assume that version C) is mainly a game of skill and version D) is mainly a game of luck.

Now what about the following scenarios: 

E) Two players play chess and bet 5 dollars.chessnyc

Here the main ingredient is skill; the bet only adds a little spice to the game.

F) Two players play chess and bet 100,000 dollars. 

 Well, to the extent that such a game takes place at all, I would expect that the luck factor will be dominant. (Note that scenario F is not equivalent to the scenario where two players play, the winner gets 300,000 dollars and the loser gets 100,000 dollars.)

Let us go back to the original scenarios A) and B). Here too, I would consider the ingredients of luck and skill to be strongly dependant on the stakes. The setting of scenario A) can be quite compatible with a game of skill where the prizes give some extra incentives to participants (and rewards for the organizers), while in scenario B) it stands to reason that the luck/gambling factor will be dominant.  

One critique against my opinion is: What about tennis tournaments where professional tennis players are playing on large amounts of prize money? Are professional tennis tournaments  games of luck? There is one major difference between this example and examples A and B above. In tennis tournaments there are very large prizes but the expected gain for a player is positive, all (or at least most) players can make a living by participating. This changes entirely the incentives. This is also the case for various high level professional chess tournaments.

For mathematicians there are a few things that sound strange in this analysis. The luck ingredient is not invariant under multiplying the stakes by a constant, and it is not invariant under giving (or taking) a fixed sum of money to the participants before the game starts. However, these aspects are crucial when we try to analyze the incentives and motives of players and, in my opinion,  it is a mistake to ignore them.   

So my answer is: yes, chess can be a game of luck.

Now, what about poker? Continue reading

Links and Comments


The link  L10n74 

(click on the picture to see L10n74’s Braid representation, its Morse link presentation, its Alexander and Jones polynomials, its Khovanov homology, and more, much more.)

Here are some links and further comments regarding the last four posts. (Mainly for the post about controversies.)



This is probably the most important issue as far as direct policy implications. (And it is a clear-cut scientific debate.) I have very little first-hand knowledge on the climate change debate. I found links to two blogs on “shtetl-optimized” (Both representing the common views regarding the issue – namely that global warming is caused by humans). The first is RealClimate  (that made a good impression on me), and the second is Climate change denial (that did not make a good impression on me). 

An interesting paragraph from the second blog in a post about “Israeli climate change denial”  (written by Lucy Michaels) is:

“A further aspect of Israeli climate denial, argued by [Pinhas] Alpert and supported by my own research, is that there is a relatively high number of climate skeptics in Israel such as astrophysicist Nir Shaviv who still persists with his Cosmic Ray theory despite it being roundly rebutted by the scientific community. A personal friend at the Israel Meteorological Service is yet to be convinced of the anthropogenic causes. Alpert argues that climate skepticism in Israel represents a Jewish trait based on traditions of Jewish critical learning – to constantly dispute and find alternative explanations. This, I think, is a polite way of saying that Israelis in general are an argumentative and contrary bunch.”

Hmm! (Actually I know Nir Shaviv quite well, here is his blog.)  The notion “climate denial” is especially cute.

Our local Institute for Advanced Study will hold starting today a large workshop on “Reducing the Uncertainty in the Prediction of Global Warming” about (mainstream) climate-change science.


Interesting papers by the famous statistician Ronald Fisher  who was critical regarding the connection between smoking and cancer can be found here.

Economics, games and psychology 

A very skeptical view on the normative or descriptive value of economic theory and game theory (even in principle) is expressed by Ariel Rubinstein (here, and here).  Robert Aumann has a very different view.  (Look at this paper  .)

Rationality and psychology. Continue reading

Amazing Possibilities


Happy new 2009, everybody! 


An understanding of our fundamental limitations is among the most important contributions of science and of mathematics. At the same time, various fundamental limitations stated by many great minds turned out to be wrong, sometimes rather quickly.

There are quite a few cases where things that were considered to be impossible turned out to be possible. Immanuel Kant claimed:  “No finite Reason can hope to understand the production of even a blade of grass by mere mechanical causes.” This quote is from the Critique of Judgment (1790). Elsewhere Kant wrote: “It is absurd to hope that another Newton will arise in the future who shall make comprehensible by us the production of a blade of grass according to natural laws which no design has ordered.”

 Auguste Comte claimed: “Of all objects, the planets are those which appear to us under the least varied aspect. We see how we may determine their forms, their distances, their bulk, and their motions, but we can never know anything of their chemical or mineralogical structure; and, much less, that of organized beings living on their surface …” (The Positive Philosophy, Book II, Chapter 1 (1842)).

Spectroscopy was developed by Gustav Kirchhoff in the 1840s, and the first spectroscopic analysis of the sun appeared about ten years later, less than 20 years after Comte’s statement.

A slightly different example relates to the philosopher Wittgenstein. Continue reading



Debates are fascinating human activities that are a mixture of logic, strategy, and show. Not everybody shares this fascination. The German author Emil Ludwig considered debates to be the death of conversation. Jonathan Swift regarded debates as the worst sort of conversation, and debates portrayed in books as the worst sort of reading. Public debates pose various interesting dilemmas. Continue reading

Controversies In and Near Science

Controversies and debates in and around science – between researchers within the same discipline, between competing theories, between competing fields, and between accepted scientific viewpoints and viewpoints rooted outside science – are common. 

Is there global warming and is it caused by high emissions of CO2 by humans? Or is global warming perhaps a myth, or rather an established fact caused by changes in the sun’s radiation, which has little to do with us? Is quantum physics correct? Can quantum computers, which have superior computation power that can crack the codes used for most commercial communication, be built? Are the teachings regarding free-market economy scientifically based?  What is rationality?  What is the weight of psychology in understanding economics?  What is the value of mathematical tools in the social sciences? What are the limits of artificial intelligence? Is string theory promising as the ultimate physics theory of everything?

What is the origin of the Scrolls of Qumran (the Dead Sea scrolls)? Were they written by a sectarian group living in a village close to the caves where they were discovered, as the dominant theory asserts?  Magen Broshi, a senior Jerusalem-based archaeologist and the ex-curator of the “Shrine of the Book” who subscribes to the central theory regarding the scrolls, said once in a public lecture: “There are  twelve theories regarding the origins of the Qumran scrolls. Continue reading

Detrimental Noise

 “Imagine there’s no heaven, it’s easy(?) if you try,”   

John Lennon 


Disclaimer: It is a reasonable belief  (look here, and here), and an extremely reasonable working assumption (look  here) that computationally superior quantum computers can be built.   

(This post and the draft will be freely updated) I am struggling to meet the deadline of a week ago for a chapter regarding adversarial noise models for quantum error correction. (Update Nov 20: here is the draft; comments are welcomed. Update April 23: Here is the arxived paper, comments are welcome! ) My hypothetical model is called “detrimental.” (This is a reason substantial math postings are a bit slow recently; but I hope a few will come soon.) This project is quite central to my research in the last three years, and it often feels like running, over my head, after my own tail that might not be there. So this effort may well be a CDM (“career damaging move”) but I like it nevertheless. It is related to various exciting conceptual and foundational issues. 

I do have occasionally a sense of progress, (often followed by a backtrack) and for this chapter, rather than describing detrimental noise by various (counterintuitive) properties as I always did, I think I have an honest definition of detrimental noise. Let me tell you about it. (Here is a recent useful guide: a zoo of quantum algorithms, produced by Stephen Jordan.)

Detrimental noise

Consider a quantum memory with n qubits at a state \rho_0. Suppose that \rho_0 is a tensor product state. The noise affecting the memory in a short time interval can be described by a quantum operation E_0. Lets suppose that E_0 acts independently on different qubits and, for qubit i with some small probability p_iE_0 changes it state to the maximum entropy state \tau_i.

This is a very simple form of noise that can be regarded as basic to understanding the standard models of noise as well as of detrimental noise.

In the standard model of noise, E_0 describes the noise of the quantum memory regardless of the state \rho stored in the memory. This is a quite natural and indeed expected form of noise.

A detrimental noise will correspond to a scenario in which, when the quantum memory is at a state \rho and \rho= U \rho_0, the noise E will be U E_0 U^{-1}. Such noise is the effect of first applying E_0 to \rho_0 and then applying U to the outcome noiselessly.

Of course, in reality we cannot perform U instantly and noiselessly and the most we can hope for is that \rho will be the result of a process. The conjecture is that a noisy process leading to \rho will be subject to noise of the form we have just described. A weaker weaker conjecture is that detrimental noise is present in every natural noisy quantum process. I also conjecture that damaging effects of the detrimental noise cannot be canceled or healed by other components of the overall noise.When we model a noisy quantum system either by a the qubits/gates description or in other ways we make a distinction between “fresh” errors which are introduced in a single computer cycle (or infinitesimally when the evolution is described by a continuous model) and the cumulative errors along the process. The basic insight of fault tolerant quantum computing is that if the incremental errors are standard and sufficiently small then we can make sure that the cumulated errors are as well. The conjecture applies to fresh errors.

 (Updated: Nov 19; sorry guys, the blue part is over-simplified and incorrect; But an emergency quantifier replacement seemed to have helped; it seems ok now)  The definition of detrimental noise for general quantum systems that we propose is as follows:

A detrimental noise of a quantum system at a state \rho commutes with every some non-identity quantum operation which stabilizes \rho.

Note that this description,

Just like for the standard model of noise, we do not specify a single noise operation but rather gives an envelope for a family of noise operations.

In the standard model of noise the envelope \cal D_{\rho} of noise operations when the computer is at state \rho does not depend on \rho. For detrimental noise there is a systematic relation between the envelope of noise operations {\cal D}_\rho and the state \rho of the computer. Namely,

 {\cal D}_{U\rho} = U {\cal D}_\rho U^{-1}.

Why is it detrimental?

Detrimental noise leads to highly correlated errors when the state of the quantum memory is highly entangled. This is quite bad for quantum error-correction, but an even more devastating property of detrimental noise is that the notion of “expected number of qubit errors” becomes sharply different from the rate of noise as measured by fidelity or trace distance. Since conjugation by a unitary operator preserves fidelity-metric, the expected number of qubit errors increases linearly with the number of qubits for highly entangled states.

Here is another little thing from my paper that I’d like to try on you:

A riddle: Can noise remember the future?

Suppose we plan a process and carry it out up to a small amount of errors. Can there be a systematic relation between the errors at some time and the planned process at a later time? Continue reading

Rationality, Economics and Games

1. The “Center for Rationality”

“Founded in 1991, the Hebrew University’s Center for the Study of Rationality  [at first it was simply called “Center for Rationality”] is a unique venture in which faculty, students, and guests join forces to explore the rational basis of decision-making. Coming from a broad sweep of departments — mathematics, economics, psychology, biology, education, computer science, philosophy, business, statistics, and law — its members apply game- theoretic tools to examine the processes by which individuals seeking the path of maximum benefit respond to real-world situations where individuals with different goals interact.” 

Game theory was always strong at the Hebrew University of Jerusalem, and a nice aspect of it is the combination of mathematics and debating. As an undergraduate I was quite interested in game theory along with combinatorics and convexity, and my first published paper was on game theory, with Michael Maschler and Guillermo Owen. Later I moved in other directions, but more recently, in part because of my membership in the Center for the last ten years and in part because of my collaboration with economists Ariel Rubinstein (who was my classmate in my undergraduate years) and Rani Spiegler, I am trying to do research and write papers in theoretical economics. Not having the basic instincts of an economist, and lacking some basic background, makes it especially difficult.

Let me also mention that there are very interesting connections between computer science and economics and a very large emerging research community.  

2. Many many controversies

Among the many issues discussed and debated in seminars at the Center (the regular ones are the “Game Theory Seminar” on Sundays and the “Rationality on Friday” seminars on… Fridays,)  roundtables, the annual retreat, Sunday’s sandwich gatherings, and ample debates over e-mail were:

The controversy over expected utility theory (we will come back to it below); (Little updates: May, 21)

The role of psychology in economics;

The relevance of “neuroeconomy”;

Continue reading