Wednesday, August 05, 2009

STOC/FOCS complete versions [Guest Post by Mikkel Thorup]

STOC/FOCS complete versions
Guest Post by Mikkel Thorup

I would like to congratulate PCs that have requested authors to submit appendices with complete proofs. I would like to suggest going one step further. For accepted papers, I think these complete proofs should be posted as reports on a place like ArXiv.

My basic interest is the case where STOC/FOCS deals with problems that are so important that we actually want them solved (contrasting cases that are just about exchanging conceptual ideas). In that case, the most damaging conference abstract is one that claims a solution but with an incomplete sketch of a proof that can neither be verified, nor falsified, and where the authors never themselves provide the details. Since the credit is already given out, there is no incentive left to really solve the problem. I have seen good research areas killed this way. The situation is much better when a paper has a clear bug, for then it is well-justified to look for a true solution. This is why I would like the complete proofs posted on ArXiv. It is OK that they are not so well-written. The important thing is that we have a place where people can go and check the details if in doubt.

I think this would have some positive side-effects. First of all, I do not think people should claim solutions to important problems if they do not have some complete proofs. The PC may not have time to read the complete versions, but knowing that your complete version will be public will most likely make people think twice before submitting (I think this is positive).

Having the first complete versions along with comments and questions should also pave the way for more and better journal versions.

47 comments:

Anonymous said...

Isn't it fairly typical to publish a proofless version at a conference (perhaps citing a tech report with the proofs) and then the complete version, with proofs, in a journal?

Suresh said...

that second step is the problem. it's not uncommon for journal versions NEVER to appear, or take years and years, while informal claims of bugs in the conference version circulate among those in the know, making it difficult to actually write a new paper, as Mikkel mentions

Andrew said...

The whole thing of "I have discovered a truly marvellous proof of this, which this abstract/margin/whatever is too narrow to contain" is bogus. The community should refuse to accept such claims.

The arXiv publication idea is a good one. On the other hand, why not insist on full papers in the proceedings? ISIT went in this direction a few years ago, going from 1-page abstracts to 5-page papers in the proceedings. CD-ROMs are cheap.

Michael Mitzenmacher said...

I'm assuming anonymous #1 is from some different field. :)

Andrew -- most ISIT papers don't come close to containing full proofs. 5 pages isn't enough to put a lot of info.

I think Mikkel has a worthwhile idea, but it gets to a challenging issue -- how do we handle errors in papers? I think the CS community tends to bury its head and ignore them, which leads to the problems that Mikkel brings up.

A challenge I brought up with Mikkel -- but which by no means detracts from his point -- is that if we moved to such a system, we'd have to find some way to differentiate between bugs -- by which I'll mean a fixable but non-trivial error, where the author should have some time to work out a suitable correction -- and incorrect statements. I think we'd still as a community face the challenge of how to handle errors (and responses to errors), but the system would be much more open and transparent.

Anonymous said...

I think the whole issue again boils down to the one that was raised recently regarding the merits (or lack thereof) of conference proceedings as publication venues.

Theoretical CS is a mathematical field, which aspires to the same standards of mathematical proofs as other areas of mathematics. This makes it essential that publications go through a careful and thorough refereeing process with multiple revisions if necessary -- which is standard in mathematics. The conference publication cycle, with its emphasis on quick turn-around and dissemination, is important in engineeering-type disciplines (and indeed borrowed from them) but clearly unsuitable for TCS.

I suspect that most people in the core areas of TCS know and secretly acknowledge this -- but how to change the publication culture overnight is not so clear. A white paper by the senior people in the field addressed to the Deans and Faculty tenure/hiring committees urging them not to consider conference proceedings publications (not backed up by a follow-up journal article) as publications would be a start.

Anonymous said...

I would like to go a step further than Mikkel. Authors should be required to post a full paper to ArXiV or ECCC or one of those online fora, and then submit a 1-2 page abstract (with a link to the full version) to STOC/FOCS (this "submission" is merely an indication that the authors would like to be considered for a presentation at the meeting). The conference will merely be a venue to make a public presentation and meet other researchers.

Naturally, online fora allow for revisions, updates, etc.

I think that the very act of making a manuscript "fully public", as opposed to being available for reviewers only, will make authors write better, supply all necessary details, be careful with attributions, etc.

Anonymous said...

I agree that papers including full proofs should be posted on the arxiv, but for slightly different reasons. Mikkel emphasizes the importance of posting full papers to avoid the propagation of errors. But it is more than that. Even if your claimed result is fully correct, if you do not have a full proof then you do not have a proof at all. If the full proof of a result is not available, then it is not a result. Fermat's Last Theorem was not a theorem.

Since the submissions required full proofs, there is no good reason why the full proofs should not be placed on the arxiv. Unfortunately, I think that a lot of the FOCS papers are not available online anywhere even now, which I find inexcusable. If an author hasn't managed this minimal effort in four months, then perhaps the PC should ask if he or she wouldn't rather withdraw the submission from FOCS.

"we'd have to find some way to differentiate between bugs -- by which I'll mean a fixable but non-trivial error, where the author should have some time to work out a suitable correction -- and incorrect statements"

There should not be errors, "fixable" or not. The fact that this situation arises so commonly I think is a side effect of us accepting abbreviated proofs, and it should become less common. Additionally, making the full proofs available on the arxiv sooner means that any errors will be caught faster, so that the corrections can be incorporated into later versions and the journal version.

"The conference publication cycle, with its emphasis on quick turn-around and dissemination, is important in engineeering-type disciplines (and indeed borrowed from them) but clearly unsuitable for TCS."

Clearly unsuitable? I do not agree at all.

"how to change the publication culture overnight is not so clear."

A good way to start is with Mikkel's proposal. Require full proofs in the submissions. As a community, we should also move to the point where every paper is posted on the arxiv (like in much of mathematics). Unfortunately, I think that there is not much leadership being shown on this. For example, the ECCC seems determined to keep TCS electronic archives fragmented, even though it is inferior to the arxiv for the archival function. I guess this is because the editors want to boost their resumes. But the fragmentation hurts the field, because it slows or prevents the development of community standards for electronic preprints.

js said...

I agree that full proofs of all published claims must be available somewhere.

But in many cases the simplest option would be to have the full proof in the final conference paper! Something like 10 pages in ACM's 2-column layout is a lot of space – if you use it carefully.

I think the problem is that people prepare the final version of their accepted conference paper hastily. If you have a 10-page paper with a 10-page appendix, and you must fit it in 10 pages, you just leave out the appendix (with full proofs) and the end result is a typical hand-wavy conference abstract.

But it does not have to be like that. The paper has already been accepted, so you can safely remove everything that only served the purpose of getting the paper through the review process. This might include most of the motivation, discussion, references that are there only to keep potential reviewers happy, etc.; you can give the sales-speech in the conference talk. But even more importantly, it would include all unnecessary complications and extensions that are there just to make the math look more impressive and difficult.

Take the main result, make it as simple and straightforward as possible, and give a full proof for that. I claim that more often than not, the result would be a self-contained conference paper that fits easily in the given page quota.

Why most aren't authors doing this, then? (1) No incentive; the paper has already been accepted and no-one will check the final version. (2) Too little time between acceptance and the deadline for preparing the camera-ready version.

Anyway, I recommend trying this approach next time you are preparing a final version of your conference paper. Naturally you can arXiv the full version, too.

Anonymous said...

No anonymous #1 is not from some different field. Why do you think he is?

Morrisett said...

In the PL world (e.g., POPL, ICFP), there's a shift happening where many people are formalizing their proofs in a proof assistant (e.g., Coq, Isabelle/HOL, Twelf) and in the paper, posting a link to the code, so that readers can download the code and have a proof assistant check the development. That gives the best of both worlds in that we get very strong assurance of correctness of the details (machine checked), and have an English description of the interesting bits in the conference paper.

Of course, the proofs we do are quite shallow compared to what happens in STOC/FOCS and constructing the proofs is extremely tedious in spite of a lot of advances, so this isn't going to be useful for you guys.

Anyway, one other option to consider is two categories of papers: a "strong" category, where authors provide a link to a detailed proof as suggested, and a "weak" category where they don't. Reflecting the categories in the titles of the paper will send a clear message.

Mihai said...

The paper has already been accepted, so you can safely remove everything that only served the purpose of getting the paper through the review process. This might include most of the motivation, discussion, references that are there only to keep potential reviewers happy, etc.; you can give the sales-speech in the conference talk.

Oh yeah, screw the students that might try to understand the field after the conference happened. Our goal is to generate pieces of mathematical proof; any understanding of what they mean is unnecessary.


Having just been on a FOCS PC, I can certainly say that: (1) for most papers, the first 10 pages could be very informative; (2) for many papers, they aren't.

The way to fix this is to change the culture inside the PC (this is the only group with real power). I was advocating for the following rule: for each accepted paper, a champion PC member has to spend 4 minutes explaining how it works, and what the new ideas were. Today, PC members are very forgiving of the fact that no proof idea can be extracted from the paper (they do complain about it, but still happily recommend acceptance).

Needless to say, such a scheme would force the authors to write a very good description of the the main ideas in the first few pages, which would be most helpful to the readers. But this requires other changes before it can be implemented, especially reducing the load of PC members (which right now, is ridiculous, and introduces a lot of randomness in the decisions).

Mihai said...

A white paper by the senior people in the field addressed to the Deans and Faculty tenure/hiring committees urging them not to consider conference proceedings publications (not backed up by a follow-up journal article) as publications would be a start.

Good luck with that :) Our senior people are off in the other direction, creating conceptual conferences, where full proofs are not required, and possibly even discouraged. (If you heard Silvio's presentation during STOC, he was saying something like "We don't want you to submit the formal proof of your hybrid argument. Everybody knows how to make a hybrid argument. Just tell us how your proof is different from the previous ones.")

The distinction that Mikkel alludes to is very real. There is a segment of TCS that is mainly driven by problems (there are problems we all agree are important, and the goal is to solve them). And there is another segment where the motivation to most problems is kind of artificial (more Math-style: the motivation only comes from within the field; if you solve a problem in an easy way, it's not a nice surprise, it's just boring). In the latter segment, correctness is good, but incorrectness will not kill your contribution.

Anonymous said...

Of course, the proofs we do are quite shallow compared to what happens in STOC/FOCS ...

Actually, if one is to follow Grothendieck's advice, one should try to
define the right objects to study (this is by no means trivial), and when this is done properly the theorems should become trivial.

The reason that TCS (but not just TCS) papers look difficult is that TCS people are busy trying to win cheap fame by proving new results, instead of devoting their time to building proper foundations for their theory (lets say in the style of EGA/SGA). If they do so,
down the line many of these "difficult results" might become indeed trivial (as well as completely transparent). But of course there is much less "cheap rewards" in such foundational work.

Anonymous said...

And there is another segment where the motivation to most problems is kind of artificial (more Math-style: the motivation only comes from within the field; if you solve a problem in an easy way, it's not a nice surprise, it's just boring).


This might be so, but this is not "Math style". Mathematics is indeed driven mostly by internal motivations (which discipline isn't ?), but a simpler proof in math is never considered inferior to a more complicated proof, and in fact mostly mathematicians favor simpler proofs over complicated ones. The phenomenon you are referring to is probably caused by certain TCS people who want to pose as mathematicians but does not have the wherewithals to do so -- so they hide behind "sophisticated' math in ther papers.

Mihai said...

Mathematics is indeed driven mostly by internal motivations (which discipline isn't ?)

I would like to think we are much better at this, since we study a natural object (computation on computers), and maintain some connection to reality.

This is the reason I originally went to Computer Science, not Mathematics. Then again, the latest trends in TCS make me wonder.

, but a simpler proof in math is never considered inferior to a more complicated proof

A simpler proof after a complicated proof gets a lot of respect in Maths (and somewhat less in TCS). But if you're motivation is internal, and you want to start a new direction, the first proof in that direction better look hard / surprising. Otherwise, I don't see how you can reasonably convince people to follow your direction.

Anonymous said...

I would like to think we are much better at this, since we study a natural object (computation on computers), and maintain some connection to reality.

Mathematicians of a platonist-bent think they are studying "natural objects" -- others don't. But these philosophical questions do not enter in the daily chores of mathematicians -- neither should it in TCS. In any case, the "objects of study" in TCS are not really different from objects studied by mathematicians such as groups, numbers, manifolds etc. Hence, the way research is conducted and disseminated in TCS should not be that different (in fact should be identical) to other areas of mathematics.


But if you're motivation is internal, and you want to start a new direction, the first proof in that direction better look hard / surprising. Otherwise, I don't see how you can reasonably convince people to follow your direction.


People will follow in your direction if they think that the new proof or method has an insight or connection with deeper phenomenon that should be explored. It does not mean that the initial paper has to be very deep and complicated. For instance, the initial papers of Erdos and Renyi on the "probabilistic method" were quite simple. The foundational papers of Riemann (on Riemannian manifolds) or Poincare (algebraic topology) were quite simple, full of holes etc. But this did not prevent people from realizing their import.

Anonymous said...

This is the reason I originally went to Computer Science, not Mathematics. Then again, the latest trends in TCS make me wonder.


In this case you should consider moving to a Math department. Before you do so though you should do a few things -- primarily start publishing in mathematics journals rather than CS proceedings and go to math meetings instead of or in addition to TCS ones. There are plenty of mathematicans these days who are genuinely interested in TCS (minus the bs parts of it) as a math discipline, and I am sure they will gladly have you in their departments.

Suresh said...

In Mihai's unintentional troll-comment about math-style publishing, we've lost track of a point that Mikkel made that I think is a good one.

Why not require arxiv submissions at submission time ? Physics does this already: I believe that there some physics journals where the "submission" consists of a link to the arxiv page.

But the other problem that Mihai refers to is real: even if authors provide 100-page detailed manuscripts with all proofs worked out in copious detail, who has the time to read and verify these in a conference review format ? with the kinds of loads we have (I'm doing 50 for SODA), there's no way to evaluate papers really well, and you have to trust the author, unless you ditch the conference format entirely.

stasys said...

"Proof or not a proof? This is the question." Full proof in appendix, in ArXiv, in ECCC or elsewhere -- is a nonsense. It must be there, in the paper. As for now, conference papers look like "I've solved this, you don't need to push this problem further, anyway I am the owner." That the (owned, not published) proof is probably wrong -- who cares?

Is it the way TCS want go further? See Fortnov's on why we should not.

Anonymous said...

There is a list of the FOCS accepted papers, with links to any available online versions, at http://graph-theory.blogspot.com/2009/07/focs-2009-accepted-papers-with-pdf.html Of the 73 papers, 26 still have no online version available! It is possible that some of these papers are available under new titles, though. For a large majority of these 26 papers, at least one author is advertising the paper on his or her homepage, while keeping the actual paper private. Several actually have very nice individual web pages set up as advertisements.

It is good that there are online versions available for 2/3 of the accepted papers. I did not check whether these versions include full proofs. We will also see how this changes in the next week or two, after the final conference versions have been turned in. If the authors still have not made an online version available, or if the online version does not include full proofs, then that would seem to provide damning examples of the "I've solved this, you don't need to push this problem further, anyway I am the owner" notion. It would also begin to raise correctness suspicions. Submissions including full proofs were supposed to have been written up by April 2, four months ago now. The proofs should not be kept hidden.

The two papers below have online versions that Google found, that are not linked to by the above website. Aside from these two, though, none of the papers without pdf/arXiv links have online versions available. Perhaps some of the authors in industry have extra barriers to releasing their work to the TCS community. Even if so, that would explain only a few of the missing papers.

Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
Ankur Moitra
http://people.csail.mit.edu/moitra/docs/logk.pdf

Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks
Yossi Azar, Benjamin Birnbaum, L. Elisa Celis, Nikhil R. Devanur and Yuval Peres
http://arxiv.org/abs/0907.4356

Paul Beame said...

I like Mikkel's idea. The downside is low since authors can always update their posted versions easily to add polish that they might have missed at conference submission time.

It could be particularly useful in a few tricky instances but it will not eliminate the worst problems - when authors incorrectly state something as a completely obvious extension that they may not view as important and so might not be inclined to write out details for even in a full paper.

Such a requirement also won't change much for conference PCs. I have seen full papers submitted of 50 or 100 pages or more. Unless each reviewer only gets a handful of papers to review there is no way they can check everything.

Requiring posting on the arXiv or ECCC might have a small benefit even during the review process, namely a community of readers acting in parallel with the PC and checking details, but this only would work if there were an appropriate way to comment in case there is an error. Unfortunately the arXiv lacks such a comment/thread feature; this feature is available on ECCC, but it is rarely used and comments require the vetting process that papers do which can be slow.

Anonymous said...

RE Anonymous August 6, 2009 10:11 PM

The FOCS final versions were not due yet. Sometimes authors get quite detailed comments back they want to incorporate. This is a good thing. If you are really interested in the paper (or even omitted proofs), have you tried to just write a mail to the authors? I have done this more than once and always got the submitted version within a day.

It seems a bit harsh to say authors are keeping there papers secret when everything you have to do is either to wait a little or to spend half a minute to write an email.

Anonymous said...

In Mihai's unintentional troll-comment...

Actually, I thought Mihai's comments were right on the mark:

There is a segment of TCS that is mainly driven by problems...And there is another segment where the motivation to most problems is kind of artificial...if you solve a problem in an easy way, it's not a nice surprise, it's just boring.

The second case seems to describe most of the crypto research (and almost all the STOC/FOCS crypto research) going on today.

stasys said...

I think Paul touched an interesting point. So, a concrete suggestion:

1. Open at ECCC something like "conference series."

2. Authors are required to post there full (preprint) versions of their conference submission *prior* to the actual submission. With *full proofs*. (After all, proofs must be there, if one submits.)

3. These "series" should be handled by ECCC differently than "regular" submissions. In particular, *everything* submited should be posted.

4. Comments to the preprints in these "series" should also be free, "blog type", no screening from the side of the ECCC board.

5. PC members can use all this for their decision.

6. Authors, whose papers were *not* accepted by PCs have an option to withdraw their preprints from ECCC.

Of course, I see here several problems.

1. People often don't have full proofs when they submit to conferences, just an idea "this should hold."

2. Conferences are often "battle places" -- people don't want to show "too early" what they are doing right now.

3. The copyright issues. These however should not be a big problem -- versions at ECCC are just *preprints* (technical reports).

4. People at ECCC should be willing to run this. But this also should not be a problem if there would be such a wish from the PCs of FOCS/STOC/CCC/etc. After all, this would just mean for ECCC just to make some *technical* changes, no additional load for the ECCC board.

I am in ECCC board (actually, it was my idea to create this site 15 years ago ... I was inspired by "El. J. of Combinatorics") and I would try to actively push this "conference series" stuff further, if people (especially those handling as PC members) would find it useful.

Anonymous said...

I would support using Arxiv but not ECCC, since it has unfair selection policy: it does not referee and it does not post everything.

Either 1) be selective and referee or
2) do not referee and publish everything

Anything in between is biased.

Anonymous said...

"It seems a bit harsh to say authors are keeping there papers secret when everything you have to do is either to wait a little or to spend half a minute to write an email."

I agree that we should not judge them harshly. (However, I still do not believe in advertising papers that you are not willing to distribute except privately.) If in a week or two from now, their papers are still not available online, then they should be judged harshly.

stasys said...

"I would support using Arxiv but not ECCC, since it has unfair selection policy: it does not referee and it does not post everything."

ArXiv is OK, but there you will not get a feedback. About "unfair selection:" these are eliminated by items (3) and (4) of my suggestion.

One of us (there are too many "anonymous" to say "who") said: "ECCC seems determined to keep TCS electronic archives fragmented." How often have you looked for things you need in the "cellar?" Is it not better to have things a bit "fragmented" (pre-selected by someone) knowing what I can find where? Not just somewhere in an ArXiv (=celler of everything)?

Warren said...

I generally agree with Mikkel's post. One caveat: Mikkel's suggestion makes conference publications a bit more like journals. It's better for conferences to serve the journal role than for nothing to, but it would be even better if journals served the journal role.

To move the field towards journals how about the following two community standards:

(a) one cannot include conference papers on CVs unless one of the following applies:
(i) Less than 5 years old
(ii) Journal version has been published or accepted for publication
(iii) A follow-on paper or book, by self or by others, proves the main results (or something better) in full detail.
(b) If a result has a hole large enough that filling that hole would *not* be a reasonable homework assignment, and is over 2 years old, then that result is reclassified as a conjecture with proof ideas. Others would then be free to publish their own proofs and claim priority.

The purpose of a.iii is to allow people to skip journalizing results that get rapidly superseded and hence would not likely be read.

Warren said...

ECCC's charter is currently limited to complexity. It would be sort of odd to have all ECCC accept all sorts of papers if they're submitted to STOC/FOCS but only complexity otherwise.

stasys said...

"ECCC's charter is currently limited to complexity."

Warren, this is true. But currently we only have two choices: ArXiv or ECCC. One is too big, the other is too small, in its scope. But having no "place for full proofs" in TCS, we could start with something. The "conference series" in ECCC would not be restricted to complexity. Perhaps, all this thing would then grow to something "more global", perhaps outside of ECCC. We should just start somewhere ...

Anonymous said...

But currently we only have two choices: ArXiv or ECCC. One is too big, the other is too small, in its scope.


In what sense is arXiv:cs.cc bigger in scope than ECCC ? ArXiv is currently being used by mathematicians, physicists etc.
The subject classification clearly makes it useable for them -- so why not for TCS ?

Anonymous said...

"ArXiv is OK, but there you will not get a feedback. "

There is no feedback for ECCC either.

Anonymous said...

"stasys" is vigorously (and illogically) promoting eccc over arxiv. Please note that he says earlier that ECCC was his idea, thus the illogical reasons (e.g. conflict of interest) for using ECCC over Arxiv.

Having a conference series in ECCC and not arxiv and having ECCC continue to only publish CC papers otherwise, may lead to the CC results as getting more visibility by everyone and being unfairly viewed as most important.

Thus, if you believe that all areas of TCS should be treated equally, just support arxiv.

Anonymous said...

Stasys said: "One of us (there are too many "anonymous" to say "who") said: "ECCC seems determined to keep TCS electronic archives fragmented." How often have you looked for things you need in the "cellar?" Is it not better to have things a bit "fragmented" (pre-selected by someone) knowing what I can find where? Not just somewhere in an ArXiv (=celler of everything)?"

NO. I very strongly disagree.

Read Greg's comment at the other blog http://blog.computationalcomplexity.org/2009/07/eccc.html

The ECCC was fantastic and it is cool that you helped to found it. I think it is now hurting the field, though, both because of its antique problems (its recent update catches up with the arxiv from five to ten years ago) and, more importantly, because the fragmentation has resulted in fewer TCS papers being made available online.

If the ECCC converted into an overlay for the arxiv, then that would be very useful and I would start to agree with you.

Anonymous said...

Somehow the URL was truncated in my last comment. It should have ended

/2009/07/eccc.html

stasys said...

I agree with ALL the critics on my comments. Especially with:

"Having a conference series in ECCC and not arxiv and having ECCC continue to only publish CC papers otherwise, may lead to the CC results as getting more visibility by everyone and being unfairly viewed as most important."

Indeed, this is a serious problem I've missed in my spontaneous suggestion. This, perhaps, would be the reason why also ECCC board members wouldn't support this my "suggestion."

"If the ECCC converted into an overlay for the arxiv ..." Actually, I do not understand quite well what this "overlay" should mean? If this would mean
something like as "arXiv platform mirroring ECCC papers", what could be bad with this? One can access more papers from one place (from arXiv). But under "overlay" is meant something more: mix everything in one pot.

Just for fun: Why do we not have just one "mega-journal" or just one "mega-conference?"

moshe said...

See http://delicious.com/fortnow/Conferences.

Moshe

Mikkel Thorup said...

I am happy to see this discussion. I want to add some technical points to my proposal.

1) EASY TO IMPLEMENT. No-one has to do anything different. All we need is an automatic system posting all submissions of accepted papers at some agreed place, e.g., on ArXiv. Of course, today we know that the PC will never read page 35 of the appendix, but now authors risk that someone gets really interested and study the details later providing comments, questions, and bugs.. Authors can always make improved versions, e.g., as they make the camera-ready conference version.
I do not think we can/should demand that authors post papers that are not accepted.
We are not going to agree on some perfect system, but if we can agree that
this is an improvement, then it is basically ready to go.

2) CONFERENCES versus JOURNALS. I think our selective conferences play a great role in quick dissemination of what is regarded as the most significant recent work. Journal refereeing of complex papers takes a long time, e.g.,
as an extreme example, take the graph minor stuff. Getting a complete version out for discussion together with the conference announcement would be most useful. The real journal version is likely going to end up being of much better quality.
In connection with copy-right and journal policy, posting the submitted version has the "legal" advantage that
it is clearly not refereed, just selected.

Best, Mikkel

Anonymous said...

Stasys,

By "overlay" is meant that the papers (and their latex source) would all be hosted on the arXiv, while the ECCC would link to a selection of those papers. This simplifies the technical issues for the ECCC, and it still lets ECCC readers see the same papers without being overwhelmed by the arXiv.

Hi Mikkel,

I don't think the arXiv would be a good place for automatic posting. There are too many problems. For example, many papers have already been posted. Also the arXiv discourages submissions except directly from the authors, and discourages submissions that do not include the latex source code. It would be better to post the papers on another web site (potentially like the ECCC, but I am not sure permanent hosting is necessary).

What is wrong with requiring all *submissions* to be links to arXiv papers? A problem I can think of is that some people might not be able to get author credentials at the last minute. (Generally, credentials are granted automatically to email addresses from universities, but non-university submitters might need a reference first, I don't know.) This would also certainly change the dynamics of how people prepare their submissions, but it doesn't seem to be a bad thing.

stasys said...

"By "overlay" is meant that the papers (and their latex source) would all be hosted on the arXiv, while the ECCC would link to a selection of those papers."

I see. So, the role of ECCC board would be to clean up a junk (to put a stamp "screened at/by ECCC" or something similar). I doubt whether(actually, don't believe that) these people would agree to be just "junk cleaners" ... Especially, in this "P-NP provers madness". Do you really think this could work?

But I still cannot see why not to arrange things just in oposite direction: ArXiv mirrors ECCC papers?" That is, just fetches the ECCC archiv (PDF files + abstracts) to their archiv?

I often hear only *one* argument against this: ArXiv keeps LaTeX sources, so that the papers can be accessed after many, many years. But I don't think this is a convincing argument. Preprints are PRE-PRINTS. Their "lifetime" (=being actual) is not so long (2-3 years) until the PRINT version appears. Servers like ArXiv or ECCC are not "for ages." This role is played (and will be played in the nearest future) by journals. Server's role is to show hot, fresh results. Something like "online, not so arrogant conferences." To save researchers time when checking personal home pages.

So, why not "ArXiv mirrors ECCC" (includes its papers on their site under CC), and hence, allows people to access also ECCC papers from one place (from ArXiv)?

I would also like to react to yet another claim:

"I think it (the ECCC, my note) is now hurting the field, though, both because of its antique problems (its recent update catches up with the arxiv from five to ten years ago) and, more importantly, because the I think it is now hurting the field, though, both because of its antique problems (its recent update catches up with the arxiv from five to ten years ago) and, more importantly, because the fragmentation has resulted in fewer TCS papers being made available online."

I couldn't understand the last claim: papers in ECCC are still available online. Perhaps you mean "available from one place?" But then this is not our problem rather that of ArXiv (see above).

P.S. Technical problems with the access could be stipulated by people using a 15 years old Web address of ECCC (in Trier). This old link is indeed too often down. But 6-7 years ago the ECCC server moved (together with its manager, Christoph Meinel) to a more relable place (like ArXiv has done some time ago):

http://eccc.hpi-web.de/

stasys said...

... I am sorry: the last citation was doubled via cut and paste ... Is there any "clean" way to cite the claims you want to replay to in blogs?

(My excuse: I've never participated in blog discussions before this summer. Am just a "beginner.")

Anonymous said...

No, I do not think the ECCC board would agree to it. I think that hosting papers at the ECCC gives some a sense of ownership over the papers that they will not give up. Converting the ECCC to an overlay would not in any way diminish the usefulness of the ECCC to the bigger community, and would bring many technical advantages. But there are too many egos involved for that to matter.

It cannot work in the other direction because the arXiv covers fifty different areas, from mathematical finance to high-energy physics, and is not going to make special arrangements for CS complexity theory. The arXiv also has many technical advantages over the ECCC. One of these is, as you say, that the ECCC web server is too unreliable.

"I couldn't understand the last claim: papers in ECCC are still available online. Perhaps you mean "available from one place?" But then this is not our problem rather that of ArXiv (see above)."

No, I did mean that fewer papers are available online because of the ECCC. Greg's post on the other blog (http://blog.computationalcomplexity.org/2009/07/eccc.html) explains this better than I can.

I have serious problems with the way the ECCC works right now. We learned on Lance's blog that it sometimes keeps submitted papers private only to editorial members for two months before accepting them so the public gets access. As papers are not being refereed for correctness, I find this outrageous.

Anonymous said...

The thing that makes me mad about ECCC is that was apparently always run in this unfair model (holding onto and then possibly rejecting papers even though it does not referee for correctness) and many people in the community were never aware of this. I thought that some papers take a while to be posted, but it is like this for all papers, which is not the case.

This level of non-transparency is not acceptable.

Jonathan Katz said...

Why do we need to restrict to arXiv or ECCC? Why couldn't someone start a new one (specifically for full versions of submitted papers, if one wants to distinguish from ECCC), along the lines of what was done (originally) for the eprint archives?

stasys said...

"The thing that makes me mad about ECCC is that was apparently always run in this unfair model (holding onto and then possibly rejecting papers even though it does not referee for correctness) and many people in the community were never aware of this."

How it works is not hidden, it is in ECCC Call for Papers:

http://eccc.hpi-web.de/colloquium/call_for_papers/

Submisions "holded and the rejected" -- they are waiting until a board member interested in it (if any) takes it for screening.
Only if within two months the paper waked nobody's interest, it is rejected "by default." But only in this case.

I support Jonathan's idea. It would be great to have online conference (full) versions. Where they would actually reside -- who would care?

Anonymous said...

As someone outside of TCS, I am curious how the problem mentioned by Mikkel could even happen, as "kill a nice research area by false claim". Doesn't this mean the research problem actually does not have much importance other than as a puzzle? Because otherwise solving the problem will definitely mean opening a door to important problems down the road, and people will have to use the proof/method in them, and they will have to ask/push the authors for the proof or come up with the proof based on whatever information the authors gave.

Also if the proof is indeed wrong, the authors will be discredited in certain way, and will have a hard time in the future publishing anything. If this does not happen, my guess is TCS community can be less lenient.

Anonymous said...

"Because otherwise solving the problem will definitely mean opening a door to important problems down the road, and people will have to use the proof/method in them, and they will have to ask/push the authors for the proof or come up with the proof based on whatever information the authors gave."

It is hard to "push" authors for a proof. In the end, the area won't die, but the people who do eventually find a proof will not get the credit they deserve for it. (This is for many reasons. Most people not in the loop will continue to cite the old paper and not understand or appreciate the need for the correct proof.)