By now, there been lots of discussion in the blogosphere ridiculing the fact that video feeds from US UAVs (unmanned aerial vehicles) are unencrypted. (See here, here, and here.)

Bruce Schneier has another take on the issue, arguing that the military made the right choice not to encrypt. Schneier makes two points: (1) encryption is not the problem; key management is; (2) it’s not much of a concern whether the enemy can eavesdrop on the video feed. The second point seems right to me — it is no secret what areas the UAVs are monitoring, so it doesn’t really matter whether others can see the video. As for the first point, I agree to an extent: just to illustrate the point, consider that although it may be cheap to add encryption to the UAV, doing so would require providing decryption capability to everyone in the field looking at the feed; I have no idea how expensive or difficult that would be. On the other hand, the first point also reflects some of the endemic problems the military has in dealing with crypto in general.

More reading here.

A sensible discussion regarding whether “simple” algorithms should appear at SODA has been derailed in the comments by people arguing whether computer scientists have destroyed mathematics by using the notation “” to refer to the integer in that is congruent to modulo .

Although I find the opinions expressed in the comments extreme, and see nothing wrong with using in the sense above as long as it is clear to the reader, I have to say that I myself sometimes find the notation confusing. When Yehuda and I wrote our textbook, we noticed this and decided to write to refer to reduction of modulo , as opposed to for the “standard” mathematical notion of equality modulo . (As a personal preference, I don’t like using \pmod to write though I can understand others who choose to use it.) For that matter, we also distinguished between an assignment operator “” and the equality predicate “”. That way, the expressions “” and “” and “” can all be distinguished from each other.

While it’s ok to be pedantic and obsessive in one’s own writing (as I am), it seems wrong to require it of others especially if there is no danger of misinterpretation.

In case you haven’t noticed, I’ve added a twitter feed to this blog.

I’ve never been a big fan of twitter as a social networking tool. (Believe me, the last thing people need to know is what I’m doing every half hour.) I’ve had an account for a while — I wanted to reserve the name (and I still couldn’t get jkatz) — but my first tweet was today. It seems to provide a useful way to link to relevant articles without having to write a whole blog post.

On the other hand, so far I find it kind of “dry” since no one can post comments about the stuff I’m linking to — i.e., there is no two-way communication. What do the readers think? (Feel free to also use this space to comment on any of the tweets I’ve posted so far.)

In recent news, Microsoft New England has apparently hired Boaz Barak. (Though I could not find any announcement by Microsoft, or any indication on Boaz’s webpage.) This comes on top of Microsoft’s recent hires of Madhu Sudan and Omer Reingold (in Silicon Valley). One could argue that were MSR New England an academic department, it would rank among the top 3 in theoretical computer science. (Of course, one could also argue that were MSR New England an academic department many of the people would leave and the productivity of those who remain would be cut by half…)

I have to admit to feeling a bit jealous, as MSR New England is one place I would love to go… (and yes, I’ve “applied”).

I don’t want to re-hash the debates about academia vs. industry. (Anyway, it is not a fair comparison in any of these cases since Boaz, Madhu, and Omer are getting the benefits of industry without having to give up the benefits of tenure.) I’m more interested in the question of what Microsoft expects to get out of these hires? Or, more bluntly, how does Microsoft expect any of these hires to impact its bottom line? I am not asking about the value of TCS research in general, which I think is clear. I am asking, in particular, about hiring people who are about as far from practice as possible. I don’t think comparisons to “the old Bell labs” work here: the fundamental physics work done at Bell labs seems, to me, much closer to yielding practical benefits than fundamental work on complexity theory. I also don’t buy the arguments about these hires being public relations coups: how many people, outside of the attendees of STOC/FOCS, would recognize these people’s names? And for how many people will this affect their decision of whether to apply to Microsoft for a job, or buy Microsoft products?

But maybe I’m missing something. Any thoughts?

I’m not suggesting any connection between the Women in Theory workshop and an article I saw recently in the Washington Post, but posting about the former reminded me of the latter.

According to the article, admissions data from several colleges in the DC region will be reviewed to determine whether preferential treatment was given to male applicants. It seems that, at these universities, the number of women applying was much higher than the number of men; therefore (allegedly) these universities were admitting men at higher rates in an effort to achieve gender balance.

Why is it ok to have “affirmative action” when it increases the representation of women in fields where they are under-represented, but not when it does the same for men?

I’ve been busy wrapping up the semester (and working on grant applications), in addition to traveling to Tokyo for Asiacrypt last week.

In lieu of a “real” post, here are two announcements.

• The second Women in Theory (WIT) Workshop will be held at Princeton on June 19-23, 2010. The format will be similar to the WIT 2008 workshop; video here
• A Workshop on Statistical and Learning-Theoretic Challenges in Data Privacy will be held February 22-26, 2010 at the Institute for Pure and Applied Mathematics, UCLA. Limited funding is available for students and junior researchers to attend.

  This workshop is being organized by Adam Smith, and looks really exciting — I’m hoping to attend.

We all know about Gentry’s breakthrough this past year where he showed the first construction of a fully homomorphic encryption scheme. Gentry’s scheme is hard to understand and seems challenging to implement, and was/is viewed as a feasibility result only.

More recently, two new fully homomorphic encryption schemes have been proposed, by van Dijk, Gentry, Halevi, and Vaikuntanathan and Smart and Vercauteren. No paper is available for the first one, but the abstract explicitly claims conceptual simplicity. As for the second, a paper (with implementation results!) is available; I have not yet read the paper, but they claim that their scheme can be viewed as a generalization of Gentry’s scheme to algebraic number fields.

I was asked recently whether fully homomorphic encryption would become remotely practical within the next 10 years. While it’s still too early to say for sure, the fact that there are (at least) two relatively quick improvements to the original scheme gives hope.

In contrast to the market for tenure-track jobs, the market for postdocs in our field seems woefully inefficient. From the potential postdoc’s perspective — and I have a student going through the process now — there are generally no advertisements for postdoc positions and so one has to resort to some combination of word-of-mouth (with the help of one’s advisor) and sending random emails to people asking if they might be hiring. And the inefficiency goes both ways. Two out of the past three years I have tried to hire a postdoc: the first year I was unsuccessful (and so the grant money I had went unspent), and this past year I was unable to find somebody until late May. (Strange as it might sound, part of the issue may be that it is a very strong market for candidates “in the know”: over the past 3 years I have made several postdoc offers to people who took postdocs [or, in one case, a faculty position] elsewhere.)

Surely there must be something we can do about this? Note that I’m not talking about increasing the number of postdoc positions, I’m talking about better matching people looking for positions to whatever positions already exist. How about a wiki where applicants can post their application materials, and advisors can post openings? Any ideas how best to set this up?

Recently I submitted a paper and found that someone else was working on the same problem. (In this particular case there was more involved, as well as a possible breach of ethics, but none of that is relevant to the point I am trying to make in this post.) I don’t have any statistics here, but this seems to happen relatively often in our field. It has happened to me at least 3 times — once on a problem that I would consider relatively obscure — with the result being a merged paper each time. Sometimes the results obtained were incomparable, but it was determined that a merge was in everyone’s best interests as well as the right thing to do scientifically. Other times the results were essentially the same.

I know I am not alone in this. At just about every conference there is at least one merged paper (I am aware of one at the upcoming TCC). An example from the summer that caught my attention was a set of three overlapping results showing constructions of HIBE based on lattices: here, here, and here. I am aware of several other examples as well, though will refrain from mentioning them since sometimes the authors don’t want information about the way a paper was written to become public. (Feel free to share your own stories in the comments…)

What does it mean? Are there too few [good] problems to work on, so that we are all mining the same ground? If so, is this an indication that the community is stuck in a rut, or have we all just collectively identified what are the most important problems? While I think this explains part of the issue, many of the cases I am aware of involve, as I said, pretty obscure problems that are not the type I would expect everyone to jump on. Perhaps the social nature of our field, with people discussing their latest results at workshops, and open problems being “in the air”, encourages people to focus on similar sets of problems. Is this a good thing or a bad thing?

What do you think?

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.