Journals: What Can Go Wrong

(This post is somewhat of a followup to Yehuda’s post, though coming at it from a different angle.)

I agree with Yehuda that full versions of papers are, generally speaking, extremely important. As has been discussed elsewhere (see here and here, for example), our community (both the TCS community as a whole, as well as the theoretical cryptography community in particular) seems to have a problem with its emphasis on paper quantity rather than quality. (Though the quality of the research is also at issue, I am speaking here particularly of the quality of exposition.) I think also that a lack of full versions hampers scientific progress in the long run: it is a barrier to entry for others, and allows mistakes to happen more frequently than they would otherwise.

In contrast to what others have said, though, I am not sure journals are the solution. What follows is one personal story that illustrates some of the problems.

I recently had a paper accepted to a journal, and it will be published next month. This paper was submitted in August 2004. So it took just shy of 5 years until the paper was accepted, and it will have been over 5 years between submission and publication. It wasn’t as if the paper needed heavy revision, either — the reviewers just sat on it for a very long time. Nor did I get any useful feedback from the reviewers: I’m not sure they even checked the proof (whether they did or did not, they had no comments about it), and the only substantive thing they made me change were the references to prior work. And I didn’t even agree with their recommended changes (but didn’t feel like fighting them either).

Because of the journal’s policy of having “new results”, I added results that (in my opinion) increase the length of the paper without increasing its quality. The journal’s typesetting rules made the paper even longer and, in my opinion, more difficult to read (due to font issues).

Ideally, I would have liked to maintain a different copy of the paper on my webpage, written the way I like. I know some people do that, but in practice it is a pain to keep track of different versions (and so I didn’t do it in this case).

The Future Role of Journals?

So if journals are not the answer, what is? Let me be first clear that I think journals do have an important role: they are immensely useful as a form of peer review (in terms of both correctness and level of interest in the results) — assuming reviewers do their jobs. We are also not going to more away from a journal-based system any time soon, not least of all because journals publications are still a part of hiring/tenure/raise/etc. decisions. Yet is also seems clear that journals will eventually die out, at least effectively, and probably within my career; I plan to say more on this in a future post.

Still, we don’t need journals, given the fact that we can post our papers on our webpage and put them in public archives.* It seems, then, that the most useful role of journals is to serve the role of being the “carrot” that motivates people to write full versions in the first place.

*Or write a book. See Goldreich’s intriguing essay: On Our Duties as Scientists (personal version), Section 4.1. His essay is worth reading for the other points it makes as well.

Another guest post by Yehuda Lindell. My reaction will be in a follow-up post.

Recently I thought about applying game-theoretic principles to our work as academics. What are our utility functions and how are they maximized? I have the following observations (if you don’t detect the cynicism below then this is a problem with written media):

1. The first observation is that the “best strategy” is to write papers that are just good enough to get into the conference that you want, but no better. This way you minimize your work while maximizing your publications. “Best paper prizes” can somewhat improve this situation, but it’s not clear that going for “best paper” is a good strategy (it involves much more work, decisions about best paper are rather arbitrary so the chances of winning aren’t that great, and it doesn’t make much of a difference for promotion).
2. The second observation is that you should spend as little time as possible writing. That is, your presentation should be as bad as is possible to have it accepted. Once again, wasting loads of time writing well just reduces your publication count.
3. If your university doesn’t require that you have journal papers, then not only should you not write such papers, you also shouldn’t bother writing up full versions with full proofs. Specifically, write proof sketches that are “just good enough” to convince the program committee and don’t bother fully verifying. It helps to repeatedly use “the full proof will appear in the full version”, but then make sure that you never actually write such a version.
4. I’m sure that one can argue that it’s best to research “easy questions” than hard ones and so on, but I’m not going to relate to this.
5. Finally, you should definitely not waste time writing a book. It seems that a book is considered a nice addition, but 5 papers would probably do more for your promotion.

So, what’s the result of all of the above? You’ll have a nice long CV full of papers that no one will want to read, let alone follow up on. Is it really worth it? After 25 years of research, will you be able to look back and say that you had an impact? What about publishing 1-2 really good papers a year? I personally believe that this will yield much more satisfaction and impact. (I actually did this exercise and looked back over the last 5 years and asked myself how many papers that I published I actually really like and think had a real contribution. I reached the conclusion of 1-2 papers a year, so I’m happy with that. One could always ask me why I bothered doing the others. First, you don’t always know how things will turn out, and there are other reasons. But I don’t want to get too personal with myself .)

I also argue that the strategy above of doing as bad a job as possible without being detected (which is really what 1-5 lead to) may “make sense” for researchers who are very borderline and may not get tenure. However, for all the rest of the community, it makes no sense whatsoever. I would rather publish much less, but have people be happy to read my papers because they have full proofs and are easy to read. What I would really like to argue is that researchers who don’t need to follow the above strategies (and let’s hope that this is the vast majority) should make sure not to get pulled into such behavior. I strongly believe that it will raise your long-term utility!

Unfortunately, in my humble opinion there are too many people who do. Just for one example, I know of a number of great researchers with excellent papers and results that are ridiculously hard to read (and of course do not have full versions). I guess that this is my loss, because I usually don’t read such papers, but I assume that I’m not the only one…

Via Luca, a nice video on the IBM crypto group and homomorphic encryption. (Yes, the lunches are really like that!)

(Is this topic overdone? Why, I don’t think we’ve discussed this issue in at least a year…)

I was asked recently to list the top 10 theory departments in the US.* For the purposes of the ranking, I mainly considered the question What are the top schools a graduate student in theory should consider attending? After some discussion with colleagues, we came up with the following 9 (note this is unordered):
MIT
Cornell
Berkeley
CMU
GA Tech
Princeton
UT Austin
UCSD
U Washington

We had a hard time choosing the 10th. Not that there aren’t other good theory schools, just that the next 5-7 in our ranking were all roughly in the same equivalence class. (I won’t tell you what those 5-7 were; I’ll let you guess them in the comments.)

Thoughts?

* Yes, this really is how the US News and World Report rankings are done, at least at the graduate level.

Cleaning out my queue…several articles of interest from the NYT over the past few days:

Friedman claims that the dismal job market can be blamed in part on the poor public education system in the US. While I agree that there are several serious problems with the US public-school system, I think Friedman’s arguments are silly. (In case you’re interested, I am commenter #284.)

Fish records some depressing observations about the negative public perception (in the US, at least) of academics and academia. (Is there some relation to the state of public education at the pre-university level?) Here, too, some of Fish’s arguments are a bit silly. Read in particular his comments justifying the “bait and switch tactics” of university course offerings. But my interest here is not in his counter-arguments (some of which are indeed valid) but with the prevalence of this negative attitude in the first place.

Finally, a lighter article (with no political ramifications) about Martin Gardner. How many of us read his books when we were younger? (Actually, I’m curious whether he is as well known outside the US…)

Much as I’m not in favor of shameless self-promotion, I had to mention that you can now get a free copy of my book (Introduction to Modern Cryptography, co-authored with Yehuda Lindell) if you’re willing to review it.

Open questions:

The Eurocrypt deadline is today, which gives me an excuse to talk about a recent paper of mine that I had been promising to talk about for a while.

In the setting of distributed computation, a protocol is fair if all parties receive their outputs even in the event of malicious behavior by some of the other parties (in particular, even if they abort the protocol early). Unfortunately, Cleve showed in 1986 that complete fairness is impossible — even for some very simple functions — whenever an honest majority is not present. In particular, fairness is impossible, in general, in the two-party setting. (Although complete fairness turns out to be possible for some non-trivial functions, as discussed here.)

As such, there has been a significant amount of work trying to achieve partial fairness. I won’t survey all this work here; instead, I will just note that (1) several papers on the topic don’t give any formal definition of what they are trying to achieve; (2) a few papers give definitions that are either ad-hoc, or are not very easy to understand (to put it mildly); (3) protocols suggested in many of the papers have significant drawbacks.

Expanding a little on this last point, one line of work has studied protocols guaranteeing something of the following form: at any point in the protocol, the computational efforts required by each party to recover their output are within a constant factor of each other. While at first appealing, one severe drawback of this approach is that it leaves ambiguous what the honest party is supposed to do in case of an abort! If the honest party always tries to recover its output, then it can be forced to run for exponential time. On the other hand, if there is some cut-off round before which point the honest party does not invest the time to recover its output, then the adversary can always abort the protocol just before that point.

In a recent paper by Dov Gordon and myself, we suggest for the first time a simulation-based definition of partial fairness within the standard real/ideal world paradigm. (A slightly outdated version of our paper is available here.) Our definition is as follows: we take the usual ideal-world model (used when defining secure computation with complete fairness) and require that the real-world execution of the protocol and this ideal world be indistinguishable up to to an additive distance of (for some specified polynomial ). We refer to this notion as “-security”. Note that -security is technically incomparable to (but intuitively more appealing than) the standard approach (“security with abort”), which weakens the ideal model to one where fairness is not guaranteed at all but requires full-fledged computational indistinguishability (with respect to this weaker ideal model). Also, although the definition of -security allows privacy to be violated with probability , in fact all our protocols are completely private. (Some of them will also be secure with abort.)

In addition to introducing this new definition, we also completely settle the question of feasibility of partial fairness (with respect to this definition) in the two-party setting. Namely, we show:

Positive results:
Let be a (randomized) functionality, where player 1 provides input and receives output , and player 2 provides input and receives output .

1. As long as one of is polynomial-size, then for any polynomial there is a protocol computing that is both -secure and secure-with-abort.
2. As long as one of is polynomial-size, then for any polynomial there is a protocol computing that is -secure.

Negative results:
Our negative results show that the above are optimal:

1. There is a (deterministic) function where each of have super-polynomial size, such that there is no protocol computing that is both -secure and secure-with-abort.
2. There is a (deterministic) function where each of have super-polynomial size, such that there is no protocol computing that is -secure.

This line of work (continuing the earlier work on complete fairness) is among my favorites of the things I’ve worked on recently. Fairness is a natural and basic problem that we still don’t fully understand; questions in the area are easily accessible, yet resolving these questions is difficult and seems to require new techniques. Several compelling questions remain; here are some of my favorites:

• Partial fairness in the multi-party setting is wide open. The only positive results I am aware of (besides those functions for which complete fairness is possible) are for coin tossing, and the only negative results I know about are those that can be derived as extensions of the impossibility results from the two-party case.
• Determining the exact round complexity of protocols achieving fairness or partial fairness seems interesting — not just in its own right, but because I suspect it will shed light on the issue of fairness itself. The round complexity of partially fair, two-party coin tossing was recently resolved by Moran, Naor, and Segev; other than that, the question is completely open.

The latest NSF Future Internet Architecture Summit is taking place in Virginia this week.

Though I applied and was invited to attend, I was unfortunately not able to make it. In my application (which required a statement of “how your research ideas might contribute to an overall network architecture…”) I said that formal modeling and analysis of the security provided by various system components, as well as by the system as a whole, would be an essential part of designing and developing a new Internet architecture. I hope some other cryptographers and/or theorists made it there to get this point across. =)

I would love to hear more details from anyone who was able to attend. There does not appear to be any information about the current summit on the web.

I asked Jon to allow me to write a guest blog about an issue that I have been thinking a lot about lately. The question is whether there is a place for “algorithmic cryptography research” within the crypto community. Of course, I need to explain what I mean. Algorithmic research is all about finding increasingly more efficient solutions to problems. If the best algorithm known for a problem is n^5 and you find an algorithm that takes less time, then this is progress even if the solution takes n^4 and this is still quite expensive. Eventually, experience shows that this methodology yields solutions that are more and more efficient, until they are “optimal” or at least much better.

In crypto, things seem more complicated. It is relatively easy for me (and I guess for others) to judge a pure theory paper. I understand the contribution, whether it is conceptual or technical, and so on (of course, there are papers that are easier and harder to judge, but overall it’s not too problematic). However, it seems much more difficult to judge a paper that constructs a “more efficient protocol”. Once again, I don’t mean a protocol that is the first to achieve a constant number of rounds, because this is again a theoretical achievement. I mean a protocol that is more efficient in terms of round complexity, number of exponentiations, and so on than other previously-known protocols. Working in this area seems to be very dangerous. Sometimes such papers are very well received, and sometimes they are not. The question is what distinguishes the well-received and less well-received papers? Well, I have some ideas. First, a protocol with a clear asymptotic improvement often has a better chance. Second, introducing significantly new techniques seems to be almost crucial to getting such a paper accepted. The problem with judging new protocols in this way is twofold. First, there are some asymptotically efficient protocols out there that perform really badly on concrete parameters. Second, if I take a problem and come up with a more efficient solution than anything known (and of course provide a rigorous proof), then should I throw it out because the technique isn’t new?! I’ll even go as far as to venture that it’s better to have a less efficient protocol with new techniques than a more efficient protocol that uses old techniques in a better way. What about using the old techniques but coming up with a much better analysis that shows that a smaller security parameter can be used? All of these “achievements” are hard to judge, and generally hard to sell, unless we explicitly state that we want to have algorithmic cryptography.

In my opinion, if we don’t encourage algorithmic improvements (that don’t have radically new techniques, but are still often very hard to achieve), then we won’t ever reach the goal of having really efficient secure protocols. At the moment, I’m hesitant to work on such problems, because I’m not sure that I’ll have an audience. (I stress that it’s being in the middle that’s a problem. If I come up with a protocol that’s really efficient and can be used in practice, then I can sell it to the ACM CCS community. However, I also think crypto should be interested in it, and this is also really my community. Furthermore, it will take many years to get practical protocols and we need to respect small improvements in that direction, or we’ll never get there.)

Your thoughts?

I don’t want to discuss politics on this blog, but had to react to the news this morning.

Let me preface my remarks by saying that I am fairly liberal, voted for Obama, and still generally agree with his policies (though I am more sour on him than I was last November).

But giving him the Nobel peace prize?! Come on. This is a blatantly political decision, and an unjustifiable one at that. And if I, a liberal, can see that, one can only imagine what the reaction on the right will be. And it will be hard to blame them for the inevitable backlash…