Wednesday, August 29, 2007

How Mathematicians View Computer Science?

Luca Trevisan points to an article in the AMS by Neal Koblitz on modern cryptography that I think everyone in theoretical computer science (TCS) should read, as it exposes how at least some mathematicians view the culture in TCS. In summary, it's very negative. While I think the article is flawed on many levels, I'd argue that we ought to consider it as constructive criticism, and think about what, if anything, we might learn from it.

For example, one statement I found fairly misguided is the following:
Math departments usually believe the
Conjecture. For the development of mathematics it is better for someone to publish one excellent paper in n years than n nearly worthless papers in one year.
In certain other fields of science - including, unfortunately, computer science and cryptography - the analogous conjecture, while most likely true, is not widely believed.
I accept the constructive criticism that in computer science we perhaps publish too quickly, and too many incremental things. On the other hand, this conjecture has little to nothing to do with reality. For every Wiles, who spent essentially a decade on what is a very important result, there are probably 100 mathematicians who spent a decade on the problem getting essentially nowhere and publishing what in retrospect are worthless papers. And the implication that TCS is producing only a stream of worthless papers is fundamentally incorrect. The question is really whether the culture should be that a person works only on big problems with the goal of having a very small number of big results (say, 1) over their lifetime, or that a person helps the community make progress through smaller and quicker increments (as well as the occasional larger contribution). Given the important tie between TCS and real-world applications, there's a clear reason why the community has developed with a larger focus on small/quick progress, although as a community we are also supportive of people who want to work the other way as well. The phrasing of the conjecture is clever, but I actually think TCS progresses much better with the culture it has than the one Koblitz favors. (Just like sometimes fast local heuristics are much better than slow exact algorithms.)

Rather than just start a tirade against Koblitz, however, I think we'd be best off dissecting the article and understanding what aspects of the TCS culture has led to his opinions and, in many cases, misperceptions. We may find some things worth changing, either to improve our culture, or at least to present ourselves differently to other sciences.

23 comments:

Anonymous said...

I think the conjecture is intentionally stated in misleading way. Of course, if I had to choose if I write one truly amazing paper or n worthless papers, I'll probably choose the former. But nobody really has this choice. And if everybody works only on hard problems, most people will not have papers at all.

The "right" balance seems to be to divide up your time working on 1 or 2 really hard problems (say, 30% of time), and spend the remaining time on interesting, but more manageable papers.
I agree, however, that one should TRY not publish truly incremental papers. For example, where one take some bogus paper from a weak conference like RSA/PKC/Asiacrypt/etc., applies some known technique, and get a cheap improvement. However, in some cases even such papers are worthwhile. For example, if you are helping a beginning student to write up his first small result and get some confidence. Or if you really correct some silly mistake that could do harm if not corrected ASAP (say, some silly scheme could get into a standard). So it's not all black and white.

I think the minimal threshold for the paper should be to have one good idea. By good I mean new and interesting, even if simple and obvious in retrospect (in fact, those are my favorite papers!). To put some spice into this blog, I know of a brilliant senior researcher who said something along these lines:

Thesis: a good paper should have ONLY ONE great idea (and, perhaps, a bare minimal amount of supporting ideas to make the main idea work). If you have a paper with two ideas, then write two papers.

The rational of this senior person is not in increasing one publication count. Instead, I think the person honestly believes that an average Joe (not the leading expert in the field, but a beginning student or a practitioner trying to implement something in real life) might have hard time getting two ideas of a paper. Instead, you should take one idea, explain it really well, and make people understand it.

Once again, I do not completely agree with this thing as well: if two ideas are needed to solve an important problem, I'd rather write one great paper solving the problem, than two smaller papers the first of which only makes partial progress.

In any event, Koblitz' article is very harmful to cryptography. To his credit, he is a smart guy and a good writer, so his misleading, but well written claims might convince many non-experts that cryptography is not really serious mathematics - an absurd statement for anybody working in the field. I wish somebody (maybe Oded again :)) would make the time and refute the stupid claims one by one in the next issue of the AMS.

Another idea would be to make a panel discussion with Koblitz and several serious cryptographers at some big conference. Then we could tape the debate, which should prove all his views as exaggerating and counter-productive.

Anonymous said...

Just to add to my previous post. I do not want to sound hypocritical, so I want to clarify that most of Koblitz's arguments have some valid underlying points (many incremental papers, occasional mistakes in proofs, some disconnect between theory and practice, hasty refereeing, etc.). My "beef" with him that all his arguments were exaggerating, one-sided, and usually misleading. And since they were vaguely based on some valid points, they are harmful, since they sound convincing to non-experts.

Aaron said...

I certainly found Koblitz's article entertaining, what with the drama, intrigue and biblical quotations. I find it interesting that his main criticism of the TCS folks who work in the field is that they are too theoretical for his practical concerns about crypto.

I admit that I'm sympathetic to his critique of conference publications as compared to journal pubs. I've been fortunate in that the fields I work in mainly focus on journals rather tha conference, which has allowed me to avoid ever feeling rushed to complete a paper (except for that nagging feeling that I might get scooped). I much prefer this way of working, and wish that computer science had more of a culture of journal pubs than it seems to.

Finally, re: anonymous's suggestion that a good paper should have maybe one fundamentally novel idea in it (or at most a handful of related ones), I tend to be sympathetic to this view, too, but for a different reason. My experience has been that if your paper says several novel things, it will tend to only be cited for one of them. And, since academics everywhere frequently cite papers without reading them (I think mainly by copying the citation from another article), your paper becomes known for just that one result, rather than the others.

Jeff said...

A strict reading of Koblitz's conjecture yields an obvious truth. For the development of mathematics (or computer science), it is better for someone to publish one excellent paper in n years than n nearly worthless papers in one year. That someone is Andrew Wiles.

Of course, it would better still to publish n excellent papers in sqrt{n} years, but it appears that Koblitz has as little faith in his fellow mathematicians as he does in the amazingly homogeneous community of computer scientists.

Anonymous said...

For the development of mathematics it is better for someone to publish one excellent paper in n years than n nearly worthless papers in one year.

In certain other fields of science—including, unfortunately, computer science and cryptography—the analogous conjecture, while most likely true, is not widely believed.


Of course not, as it is provably false. Say semi-hypothetically, MM has developed a slight but practical improvement to hash functions used in today's routers. According to Neil, computer science would be better off it MM sat on his improvement for ten years, while he completes a definitive monograph in the subject. There are no reasons why to hold back this incremental improvement, theoretical or practical.

Kurt said...

To my (admittedly naive) mind, publishing a lot of incremental results, while perhaps not as satisfying emotionally, is likely to advance a field faster than holding out for fewer, more fully developed results. To take the example of Andrew Wiles: While the idea of being the person to prove FLT was undoubtedly a great motivator, if he had published partial results after, say, three years' work, there's a good chance that the whole proof would have been developed sooner. (Whether that would be a good or a bad thing would depend, I suppose, on one's view of the whole 1 paper/n years issue.)

Taking this idea to an extreme, you have Michael Nielsen's model of micropublication and open source research, where you cede some control over what direction your ideas take in order to gain the power of community intelligence.

Anonymous said...

1. Young areas in mathematics also feature huge publication lists. As areas grow older, less problems are open, the field tends to splinter into many directions, people can talk to each other less and less, and it's harder to get results. (Although results seem less trivial, because there's more background to know).

So, we're lucky to be in a young field, where easy and nice results are plentiful, and new ways of thinking arise every day. We're like the gold-diggers ariving in Cali in the beginning of the gold-rush.

2. There are some areas in CS, such as combinatorial algorithms, where people publish lots of small papers that nobody reads and do not make progress on any _important_ problem. These are somewhat useless, in my eyes.

Anonymous said...

Young areas in mathematics also feature huge publication lists.

That's certainly true in a relative sense, that combinatorialists publish more papers than algebraic geometers, for example. (Algebraic geometry is just harder.) However, there's a huge quantitative difference from CS.

If a mathematics graduate student publishes a couple of papers, that's considered quite good. Ten papers is considered an enormous number. If they are ten good papers, this is considered very impressive. If they are ten OK papers, this doesn't impress hiring committees nearly as much as writing two or three really good papers.

In theoretical CS, a top student who only publishes a couple of papers has to explain their apparent lack of productivity. (You can get away with it, but it looks odd.) Ten papers is not unusual. I've known four graduate students who had at least thirty to forty publications each. In mathematics that would be considered ludicrous.

Anonymous said...

"Although as a community we are also supportive of people who want to work the other way as well."

Can you actually think of someone considered a top researcher in who has less than 20 publications?

"And if everybody works only on hard problems, most people will not have papers at all."

I think you're being a bit hyperbolic here. If someone in *theory* can't produce any notable theorems, perhaps they should not be a theorist. Probably you could take 75% of the people out TCS and it wouldn't hurt the subject.

"Instead, you should take one idea, explain it really well, and make people understand it."

As Koblitz points out, most TCS people don't even sit down and write individual incremental results clearly. They write them poorly in the eleventh hour to make a deadline rather than wait and actually write them up clearly.

"but it appears that Koblitz has as little faith in his fellow mathematicians as he does in the amazingly homogeneous community of computer scientists."

The right one to dispell one authors overgeneralization and hyperbole is with your own.

"Of course not, as it is provably false. Say semi-hypothetically, MM has developed a slight but practical improvement to hash functions used in today's routers. According to Neil, computer science would be better off it MM sat on his improvement for ten years, while he completes a definitive monograph in the subject. There are no reasons why to hold back this incremental improvement, theoretical or practical."

Actually, he seems most critical of incremental results that stand little to no chance of being useful in practice. And people who are too lazy to do some calculation to decide if their incrementalism is remotely helpful.

I think a good question is will this result actually be interesting or relevant to some modest number of people in the field or at large. If the answer is YES, it definitely ought to be published. If however, your paper is likely to be read in detail by two people who arent obligated to, it is probably just junk you're writie to win grants and advance your career.

"In theoretical CS, a top student who only publishes a couple of papers has to explain their apparent lack of productivity. (You can get away with it, but it looks odd.)"

DING. This is exactly what is so upsetting to mathematicians. That someone would be scrutinized over because of the number of their papers, not their quality.

Anonymous said...

Koblitz's uneasy relationship with the truth

I find two facts amazing: that the Notices of the AMS chose to publish the Koblitz manuscript. Did anyone there actually read it before?

The second fact is the M. Mitzenmacher actually thinks that this article is a starter for any sort of discussion (giving some qualifiers such as While I think the article is flawed on many levels...).

This article is so fallacious and misleading that will require a very lengthy counter article to correct.

While Michael's labels it as how at least some mathematicians view the culture in TCS, which is technically correct, given that Koblitz can be described as such, a better label is how one vicious person manages to manipulate so many forums into publishing his diatribes.

Michael Mitzenmacher said...

Anonymous #10 above said --

I find two facts amazing... The second fact is the M. Mitzenmacher actually thinks that this article is a starter for any sort of discussion

If you look at the comments here and in other blogs, I think you'll find that there are clearly others who think Koblitz has salient points about TCS and are quite eager to agree. (Are they all mathematicians? Hard to tell, since unlike Koblitz and myself, they tend to remain anonymous. But let's assume so.) Indeed, since Koblitz gets this stuff published, we might further assume that a non-trivial fraction of the AMS (members and/or editors) agree or at least have sympathy to these views.

So for us not to use the article as a point of discussion -- for us just to stick our heads in the sand and dismiss Koblitz as a "vicious person" or, as I've seen in comments elsewhere, dismiss the article as the "rants from a mathematician past his prime", seems irresponsible, a waste of an opportunity to improve the situation. Sure, we don't agree, and we can bring counter-arguments to the table. But shouldn't we also ask how this article got to be accepted in the first place, and why so many people seem to agree with at least part of it?

Perhaps after you calm down (and I think it's a perfectly natural reaction to be angered by the article), you might be more amenable to my conclusion, which I stand by:

Rather than just start a tirade against Koblitz, however, I think we'd be best off dissecting the article and understanding what aspects of the TCS culture has led to his opinions and, in many cases, misperceptions. We may find some things worth changing, either to improve our culture, or at least to present ourselves differently to other sciences.

Anonymous said...

Why is the Koblitz article a non starter

Koblitz's main point in the article is that TCS way of thinking (define what your goals, suggest a construction, prove that is satisifies the desired properties) is completely irrelevant to cryptography. This viewpoint is shared to some extent by a few computational number theorists and it is a worthwhile effort to demonstrate that it is false.

In addition, he makes a few personal attacks on people who criticized his work, attacks that are wholly unjustified. In particular the HMQV paper is a wonderful demonstration of the power of the TCS method (the fact that it was easy to find a minor bug in a variant of the main proposal shows that).

This is the main stuff that goes on in the article. What Michael M. concentrated on is the way Koblitz describes the Crypto submissions. For starters, the vast majority of crypto submissions are not in theory (this is less true wrt the accepted papers, which causes some tension within the crypto community). Then, he is saying something quite obvious - that there is a lot of junk submitted to the IACR (Crypto) conferences.

So to take such a vicious article and think that if it contains somewhere in it some criticism of TCS that you tend to agree with and hence view it as a worthwhile starting point is very disappointing.

If you (MM) are so concerned about these issues (at what stage of research one should publish, incrementality, etc.), then express your opinion and let people comment. But do not rely on such a diatribe as a launching pad. Similarly if you think (hopefully not!) that his attacks on Hugo Krawczyk and Oded Godlreich have any merit, say so explicitly. Otherwise, by viewing the article as a discussion starter you are just lending credibility to Koblitz's views on the other matters.

Anonymous said...

"Can you actually think of someone considered a top researcher in who has less than 20 publications?"

Well, Steven Rudich has fewer than 30 publications if you discount double-copies of conference/journal publications ("http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/r/Rudich:Steven.html"), but he just won this years Godel Prize, so I think that qualifies him as a "top researcher".

Anonymous said...

"Can you actually think of someone considered a top researcher in who has less than 20 publications?"

Whitfield Diffie. The question however fails to address the fact that in a young field such as CS it is very difficult for a bright person not to publish at least one or two papers a year. The big theorems are out there for the taking, and it would be foolish to pass on them.

IMHO the CS person whose record happens to be closest to Neil Koblitz supposed "ideal" is Leslie Valiant. Most of his papers are of very high quality and relatively few and far between as compared to the rest of CS, yet he still has 94 publications as per DBLP.

Lastly, Koblit'z "ideal" of "only superstars may publish" has yet to be proven superior (or inferior for that matter) to the one currently in place in CS. Neither of these systems arose by design, or even with the best intentions of the field in mind.

Going back in history one can see that math publishing practices today were heavily influenced by the German and British academic traditions. Quite a bit of the snobbery of the Oxonian system percolated into the "pure math" school of the second half of the XX century and seemingly remains there today, if we are to judge from Koblitz article.

Anonymous said...

I would not consider Diffie a "top researcher" by a long shot. He has had no significant research contributions since his paper with Hellman. (Granted, his paper with Hellman was groundbreaking. Still, the point holds.)

Anonymous said...

One thing that is not in the current Koblitz article but was in another article he wrote was his perceived dishonesty of some people submitting to crypto conferences and how the community dealt with the issue--stating that he encountered people, some quite well known, who openly flouted the rules about anonymity, etc. Mind you, I have heard similar complaints from others, especially with respect to IACR sponsored conferences--this cannot necessarily be taken as a blanket criticism of all of CS, but I think it has some validity w.r.t. the field of cryptography.

Anonymous said...

...he encountered people, some quite well known, who openly flouted the rules about anonymity...

If you (he?) are referring to the fact that authors make copies of their papers available (on their webpage, eprint, etc.) concurrently with submitting an anonymous version of their paper, then this is indeed an issue to be dealt with --- though I don't consider it problematic --- but is far from being an ethical violation.

Anonymous said...

To clarify, I wasn't referring to papers being available on eprint.iacr.org or similar preprint servers. I was referring to a few prominent researchers in the field having their name on the title of the paper submitted, i.e., a clear violation of the rules, and in my opinion unethical.

Anonymous said...

NSA began to remove public key crypto implementations from weapons in about 1991.

Sandia cryptographer Gus Simmons suggested to NSA and Sandia that NSA replace the shift register-based Benincasa algorithm in the ctbt data authenticator with public key.

I was ordered by my supervior, Dr John Holovka [chemist] to explain what Simmons was talking about.

http://www.prosefights.org/nmlegal/mcconnell/pacer/Payne%20Tutors%20RSA%20and%20NSA.htm

While I was project leader of the missile secure cryptographic unit in the 1980, NSA cryptographer Brian Snow gave some of us Sandians a lecture on NSA crypto units. Snow showed actual devices and schematics. Snow also commented on field failures.

NSA algoritms I saw were based on shift register and combinatoric algorithms.

regards
http://www.prosefights.org/nmlegal/dcvoid/dcvoid.htm#feehan3

http://www.alineshat.com/PDF/Nojeh-LawSuit-Doc.pdf

My interests these day are in peak energy.

Please check to see if my differentiation are correct or not!

http://www.prosefights.org/pnmelectric/pnmelectric.htm#normaldistribution

Anonymous said...

Well, Steven Rudich has fewer than 30 publications if you discount double-copies of conference/journal publications ("http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/r/Rudich:Steven.html"), but he just won this years Godel Prize, so I think that qualifies him as a "top researcher".

Is Rudich actually an active researcher?

Term Papers said...

After a long time I have read something like this keep sharing..!

Anonymous said...

The problem with pure mathematics is that you are most likely to publish n useless papers in n years.

Needless to point out that the little progress that's presently done in mathematics is mostly achieved through TCS.

Anonymous said...

In any case, Goldreich's attempt to block their already-accepted article from being published is highly unethical.