Recently though I've seen a few circumstances where SODA gets mentioned in the same breath as STOC and FOCS as an equal. For example, the SIGACT Home Page lists the upcoming FOCS, STOC and SODA conferences. OK, SIGACT co-sponsors SODA but the bottom of the upcoming FOCS Home Page (side note: Early Registration Deadline Sept. 23) list the previous FOCS, STOC and SODA pages. FOCS is an IEEE conference with no official connection to SODA. Finally Cathy McGeoch is trying to set up a hockey game at an upcoming FOCS, STOC or SODA conference. Can you have a true TCS World Cup with just algorithms people?
Are SODA papers getting the same prestige as STOC and FOCS papers? Not yet but we are heading that way. Is it truly a good thing to move from a STOC/FOCS/specialized conferences system towards a STOC/FOCS/SODA/other specialized conferences system?
Not sure how accurate or up-to-date it is, but this analysis of CiteSeer ranks SODA very nearly as high as FOCS:
ReplyDelete73. STOC: 1.69 (top 5.97%)
108. FOCS: 1.51 (top 8.84%)
110. SODA: 1.51 (top 9.00%)
And Crypto is listed higher than both FOCS and SODA:
ReplyDelete79. CRYPTO: 1.63 (top 6.47%)
Hmm...
Does anyone know exactly when they will announce SODA 2006 results?
ReplyDeleteI hope this will not start a flame fest, but some believe that FOCS is in fact starting to become specialized. If it is not, then at least it is clearly becoming small with the decision not to hold parallel sessions. SODA is a blessing for those who believe that by itself FOCS is no longer enough to fill the role of the "antipodal conference" to STOC.
ReplyDeleteFOCS/STOC have been specialized conference since the late 1980s. They represent a particular fragment of CS theory. There is little correlation between the list if topics in the call-for-papers and the list of topics represented in the conference.
ReplyDeleteFOCS/STOC has been a specialized conference since the late 1980s. It represents a particular fragment of CS theory. There is little correlation between the list of topics in the call-for-papers, which is broad, and the list of topics represented in the conference, which is narrow.
ReplyDeletePardon my ignorance- if FOCS is specialized
ReplyDeletewhat is the specialization?
(I'm asking this non-rhetorically,
I really want an answer and am not
trying to make any point.)
It's a sad world where an algorithms conference ranks alongside STOC and FOCS. Not that it would take FOCS much effort to regain its prominence - let slip on the quality control, give each "specialized" area its quota...
ReplyDeleteIt's a sad world where anonymous theoreticians don't think algorithms is a subject that deserves to rank alongside whatever happens in STOC and FOCS.
ReplyDeleteAs for my own papers, I tend to prefer having them in SODA or SoCG than in FOCS and STOC. Not because of some mystical prestige associated with those conferences, but because my past experience has been that SODA and SoCG are more effective in communicating my work to the other algorithms researchers who I would like to read it.
-- It's a sad world where an algorithms conference ranks alongside STOC and FOCS.
ReplyDeleteAlgorithms are such a broad and general area that one would pretty much expect the top algo conference to be close or above STOC and FOCS.
For an extremely open-minded community, the TCS community often surprises me when it comes to discussions about conferences: too many individuals have too many strong viewpoints.
ReplyDeleteI don't understand why we can't have a variety of conferences (very small number of papers accepted, single-session or parallel-session --- pre-decided, decided by the PC, etc.). In fact, as a community, we are lacking in a good variety of conferences, and all our conferences seem to be converging towards a 20--25 minute talk model. SODA was supposed to be a novel conference, with its 2-page abstract model that was meant to invite and include as many "mathematicians" as possible. CCC was supposed to be a relaxed workshop-style conference with 40-minute talks and what not... I am not sure either has lived up to its goals.
If we want a truly "prestigious" conference, why don't we create one, or morph one of our existing conferences into one? For instance, we could specify a priori that there will be about 20--25 invited talks only, where the invitations will be made from a pool of pre-prints made publicly available at fora like ECCC, arXiv, etc., by a reasonable deadline. This would also encourage authors to write a scholarly article (with full proofs, etc.) under less of a deadline pressure.
We could also create an "open conference" where the only criterion for a paper/talk is scope and sanity of the abstract. This conference could probably function better if it is poster-only.
In the absence of novel models, I think our current models work just fine --- trust the PC to come up with a reasonable CFP (even if they feel that single-column 9pt submission is "reasonable" :-), reasonable review guidelines, reasonable acceptance criteria, etc. If it turns out that some conferences emerge more prestigious than others, then so be it.
Personally, I don't think the quality of papers at SODA (or CCC, being a "dual" to SODA in terms of number of submissions, attendance, etc.) don't match those of STOC and FOCS. Nevertheless, SODA (or any other conf.) has its role to play -- I've heard from a then-graduate-student that she likes SODA better because of the variery of algorithms researchers and applied computer scientists that show up at the conference. I find any conference with 3+ parallel sessions usually boring. Different folks...
D. Sivakumar
"Does anyone know exactly when they will announce SODA 2006 results?"
ReplyDeleteI think not earlier than next week.
Stop procrastinating everyone and go write those STOC/FOCS/SODA/CCC/Crypto/TCC papers! (And especially TCC, because today is the deadline. Oops, I should stop procrastinating...)
ReplyDelete-- Pardon my ignorance- if FOCS is specialized what is the specialization? (I'm asking this non-rhetorically, I really want an answer and am not trying to make any point.)
ReplyDeleteI'm not sure that I agree with the "specialized" label either. Certainly FOCS is becoming less relevant, with a proportionally much smaller set of papers and participants than fifteen years ago, but specialized?
Here's a quick and dirty unscientific sample, using very broad classifications e.g. learning theory+lower bounds+logic+CC = "complexity"...
FOCS 1991 sessions:
Complexity xxxxx xx
Computational Geometry xxxx
Algorithms xxxxx xx
Parallel Algorithms xxxxx
FOCS 1992
Complexity xxxxx xxxxx
Computational Geometry xx
Algorithms xxxxx xxxxx
Parallel Algorithms xxx
FOCS 2003
Complexity xxxxx xx
Computational Geometry x
Algorithms xxxxx x
Parallel Algorithms
Quantum Computing x
FOCS 2004
Complexity xxxxx xx
Computational Geometry
Algorithms xxxxx xx
Parallel Algorithms
Quantum Computing x
Aside from the facts that (i) parallel algorithms are out of fashion (ii) SCGers no longer publish in FOCS and (iii) the number of sessions overall has gone down, can we conclude anything else?
-- STOC/FOCS/SODA
ReplyDeleteEhr, that should be SODA/STOC/FOCS as per the calendar order naming convention ;-)
There is a tradeoff between attending a conference with a broad range of topics like STOC/FOCS and a more narrowly focused one in which more people will be 'like me'. Each has its advantages and its place. STOC & FOCS are still the only top conferences that fill the former role and they do it very well (albeit with some emphasis on Theory A vs Theory B topics).
ReplyDeleteQuality-wise, the top papers at conferences like SODA and CCC are very good and compare well with typical papers at STOC & FOCS in their areas. There is no denying though that there is a lot more variability in quality at SODA and CCC than at STOC & FOCS.
On a separate note, the range of topics covered at FOCS is much greater than the misleading list of the previous post. The list of topics of interest has grown rather than shrunk and is governed by the submissions themselves not by particular biases.
The number of sessions/acceptance rates for FOCS is a separate issue. If you are interested in addressing this, a natural place to do this would be at the business meeting at FOCS in Pittsburgh.
Paul Beame
My understanding is that the purpose of STOC/FOCS is to showcase what's going in theory, and to be a place where one goes to talks outside one's own sub-area:
ReplyDeletehttp://www.math.ias.edu/~avi/TALKS/STOC04.ppt
As such, I like the format of FOCS, with single sessions and tutorials, much better than the format of STOC, when talks that I am interested in are often scheduled against each other.
SODA follows a different model, where there is a narrower focus, more papers, more talks, more parallel sessions, and one ends up attending talks mostly in one's sub-area.
It would be possible to go much further in either direction.
The Information Theory Symposium has more than 500 papers, in up to 9 parallel sessions, and people love it as a place where one can go and meet everybody and see everything that is going on in the area.
The Symposium of Mathematicians is once in four years, all talks are invited, and the committee that decides invitation is kept secret to protect it from outside pressures. I don't know if people love it, but it has been going strong for over a hundred years.
In the huge middle ground, I think that SODA and FOCS have very reasonable, and successful, models (and so would STOC if it were single-session) and I don't see why one needs to criticize one in order to praise the other.
FOCS 2003 seemed to be sparsely attended. This seems counter to Paul and Luca's opinion that they are successful in their role. A possibility is that FOCS 2003 was an outlier in terms of attendance, but I see no reason to believe this. A while back Jeff collected some nice figures on SODA/STOC/FOCS acceptance rates, do we have similar figures for attendance?
ReplyDeletePaul wrote:
ReplyDeleteQuality-wise, the top papers at conferences like SODA and CCC are very good and compare well with typical papers at STOC & FOCS in their areas. There is no denying though that there is a lot more variability in quality at SODA and CCC than at STOC & FOCS.
It has also been expressed often (privately, mostly; I can't find a reference to any blog entry or such) that STOC and FOCS are becoming more complexity-theoretic, and that the acceptance rate for "algorithms papers" is dwindling.
In the context of the two points above (and since both STOC/CCC are late-Spring/early-Summer conferences), here are some questions to think about.
Let k denote the number that, in your opinion, satisfies the predicate "the top k rejected complexity papers from STOC are likely better than the bottom k accepted papers at CCC".
Question 1: what is k?
Question 2: if k is very small, does it mean that STOC is accepting way too many complexity papers?
Question 3: if k is very large, should CCC rethink its timing?
Question 4: True or False: one of the reasons why SODA receives so many submissions is the fact that SODA submission deadline comes after the FOCS acceptance notices (and/or FOCS rejects too many algorithm papers).
Question 5: True or False: one of the reasons for the purportedly high quality of SODA is the same fact mentioned in Question 4.
D.S.
FOCS is certainly not becoming more complexity-theoretic any more than it is becoming more algorithmic. Algorithms papers do just as well as complexity-oriented papers.
ReplyDeleteCheck out the program for the upcoming FOCS, for example. Some years there are more strong papers of one kind or another. FOCS 97, for example, was a conference that had a preponderance of strong algorithmic papers and very few complexity-theoretic papers.
Some of this distinction can be a little silly sometimes: Is a paper that develops a new small space algorithm for connectivity an algorithms paper or a complexity paper? Where does a more efficient algorithm for list-decoding error-correcting codes fit? Algorithms or Complexity?
What about reductions? Much of what gets classified as complexity is actually algorithmic in content.
Beyond that, how would you classify papers that prove some geometric or combinatorial property that yields a better approximation factor or a better running time for an existing algorithm?
One of the great advantages of STOC/FOCS is that for those conferences we don't have to worry about such distinctions of terminology.
Paul Beame
In reference to Siva's suggestions, I have heard rumors that VLDB is going to do precisely that. Rather than having a CFP and papers that are submitted, an "Oscar" model will be used, where papers are submitted (to the arxiv or wherever) throughout the year, and all papers submitted before some cut off data are eligible for invitation to the next conf.
ReplyDelete-- Suresh
One of the great advantages of STOC/FOCS is that for those conferences we don't have to worry about such distinctions of terminology.
ReplyDeleteReally? I had a paper rejected from FOCS a few years back with the comment: "too algorithmic, submit to SODA".
I've been trying to avoid weighing in, but of course I can't help it.
ReplyDeleteI think STOC/FOCS has become progressively less algorithms-oriented over the years. My impression is that STOC/FOCS emphasizes "mathematical depth", "cleverness", and "theory purity" over, say, "usability" and "insight into a practical problem". I know there are a large number of people who think this, and I would therefore encourage people who don't see this or think it is true to simply consider the issue again. I do not wish to make a judgement call as to whether this is good or bad -- this is just what these conferences, I believe, have turned into.
SODA, not coincidentally, has become a refuge for more algorithmically oriented papers. (As have more specialized conferences.) In some ways, this is good -- these papers have a home! In some ways, it is bad, because I think it has exacerbated the division, which in part explains the extreme opinions the post has raised. (I too have had reviews essentially saying, "This is algorithmic, belongs in SODA." Perhaps the reviewer was just being kind and didn't want to negatively comment on the quality of my work. But my impression is that for many FOCS/STOC reviewers "algorithmic" has itself become a quality comment, in the sense that "algorithmic" papers that do not pass the "deep/clever/pure" test are pretty much dismissed out of hand.)
I have been on committees for FOCS/STOC conferences, and I feel that I have seen these biases in action. Strangely, I did not come away with any ideas on how to change things; once a culture develops, it seems very hard to change.
Michael
The reviewer who said "this paper is too algorithmic, not for FOCS" was an idiot. That's like saying "this paper is too cryptographic, not for CRYPTO". Algorithms is the largest area of theory: there would be no STOC/FOCS without algorithms. If there really is a perception that STOC/FOCS committees think this way, it is a very big problem.
ReplyDeleteAs for emphasizing "mathematical depth" and "cleverness", I don't see anything wrong with it, and it sounds insulting to the algorithms community to assume that such an emphasis puts algorithmic work at a disadvantage: it's not like contemporary work on algorithms is trivial and shallow.
There is nothing wrong with "mathematical depth" or "cleverness" per se. The problem is when they are emphasized at the expense of "usability" and "insight into a practical problem".
ReplyDeleteThere is no denying though that there is a lot more variability in quality at SODA and CCC than at STOC & FOCS.
ReplyDeletePerception often trails reality by a few years: SODA 2005 acceptance ratio was lower than STOC 2005. That is, the raw numbers seem to contradict the statement above.
The acceptance rates in some systems conferences, which are not even top in their respective areas, are lower than that of STOC and FOCS(SODA as well).
ReplyDeleteDoesn't it seem to contradict your proof of contradiction!
What you are saying is that when we compare the acceptance ratio of subpar systems conferences with those of STOC and FOCS nothing much can be deduced from such an apples-to-oranges comparison. We agree on this.
ReplyDeleteOn the other hand, SODA is a theory conference, not a systems conference and it is at the top of its field (algorithms). Furthermore its prestige is, as Lance points out, rapidly approaching that of STOC/FOCS. So comparing acceptance ratios here is, to a much larger degree, an apples-to-apples comparison.
Said comparison at the very least contradicts the "undeniably" part of the quoted statement (i.e. the call is closer than what the poster thought) if not the posited conclusion altogether.
Luca --
ReplyDeleteTo clarify just a bit, there are certainly algorithms that are deep and clever, or that require interesting mathematical sophistication to analyze. However, it is often the case that those algorithms are not the ones that are actually useful to people.
And in the other direction, often the challenge in solving an important algorithmic problem is not depth, cleverness, or mathematical sophistication, but rather in understanding the problem you are trying to solve, modelling it appropriately, and applying known techniques, perhaps in a slightly new or non-trivial way.
I would send a paper of the first type to FOCS/STOC, and a paper of the second type either to SODA or to a specialized conference (networks, databases, etc.) that people who might actually want to implement the algorithm would attend. I suppose I am suggesting that I do not think papers of the second type have a very good chance at FOCS/STOC -- they would not pass the deep/clever/pure test.
Whether this is good or bad... is a subject worth debating. I think Piotr is right when he says "Ideally, it would be great to have a venue where both perspectives are valued and represented." Arguably, perhaps, SODA is doing a better job of that these days, and this might be contributing to its rise.
Michael
And papers of the first type would get into SODA, but the authors typically choose not to submit them... For good reason. So let's say, folks, that STOC, FOCS & SODA together serve the needs of the theory community, but let's not pretend that SODA offers the best of both worlds...
ReplyDeleteWeird - papers rejected from FOCS routinely go to SODA, but I've never heard of SODA rejects going to STOC or FOCS. Wonder why...
ReplyDelete-- Weird - papers rejected from FOCS routinely go to SODA, but I've never heard of SODA rejects going to STOC or FOCS. Wonder why...
ReplyDeleteEasy, they don't go to FOCS because the deadlines do not line up.
Second, they are generally not sent to STOC because SODA accepts a superset of STOC/FOCS papers. The question is if this this is so because of SODA's "undeniable" lower quality as some have claimed, or because of SODA's more attuned view of what is an "important algorithmic challenge", as other posters have suggested.
This is in essence the same question that Suresh asks in his blog (paraphrasing): do STOC/FOCS prog. committees aim to select the top-k theory papers or the top-k deep/clever/pure theory papers? are they even aware of the difference?
I know that this kind of sentiment doesn't go over well in these days of dwindling NSF funding, but we are doing _theoretical_ computer science, and thus papers should have a key theoretical insight. Part of the idea of a theoretical field is to be able to think while divorced somewhat from practice. If you actually believe that theory is useful (and having seen the fruitful interaction of theorists and practioners in research labs, I do), then you shouldn't feel so strongly the need to immediately justify your theory.
ReplyDeleteI do a lot of research in algorithms, and the most painful thing I see is when a paper justifies itself on the basis of being "useful" or "practical," when often this is just a scam to sell the result. Algortihms designers _can_ do very useful stuff, with immediate results, and inspired by theory. But I believe this requires a different mindset and a different approach, which isn't as well-suited to achieving recognition in STOC/FOCS.
Regarding rejected papers from SODA not being resubmitted to STOC/FOCS, this happens more often than one thinks. I have seen papers in fact make the rounds of all three and end up in STOC/FOCS. This is merely a function of the particular mix of submissions in a given year, and the tastes of the PC members.
ReplyDeleteIt is still true that authors perceiving their results to be outstanding would submit first to STOC/FOCS. The point I think is that this is less true than it used to be, for a variety of reasons, and also because as the community grows and STOC/FOCS stay relatively fixed in size, SODA naturally receives a lot of excellent papers that can't fit in a restricted program.
FOCS and STOC have stayed nearly the same size while the theoretical computer science has grown immensely in size and splintered into several different subareas. I've been doing quantum computing for quite a while, but what was happening the last time I was paying attention was that there were just too many really good algorithms papers for FOCS and STOC to accept them all. When this happens, some of them start getting sent to SODA, and SODA gets to be a prestigious conference because all these good papers are appearing in it.
ReplyDeleteThe same thing happened with the computational geometry conference earlier, although computational geometry is such a small and specialized area of computer science that most STOC and FOCS attendees didn't care that they were losing many of the best computational geometry papers. Algorithms is a central area of theory, so the best algorithms conference is a natural competitor to FOCS and STOC.
If FOCS and STOC wanted to keep the monopoly on being the best TCS conferences, they should have grown much larger and much earlier.
Weird - papers rejected from FOCS routinely go to SODA, but I've never heard of SODA rejects going to STOC or FOCS. Wonder why...
ReplyDeleteI know of at least two SODA rejects that were accepted in the subsequent STOC conference.
I know of at least two SODA rejects that were accepted in the subsequent STOC conference.
ReplyDeleteAdd at least two accepted FOCS papers that were rejects on the corresponding SODA earlier that year.
What about a STOC/FOCS papers with some errors? Is that also better than a SODA paper?
ReplyDeleteA paper with errors is certainly more interesting than a trivial or incremental paper.
ReplyDeleteThe list of papers accepted to SODA 2006 is available now.
ReplyDeleteNow that the list of accepted papers is out, go ahead and take a look. SODA is a good conference, but I bet that at most the top 10% of papers there would be accepted to FOCS.
ReplyDeleteFor people who say that STOC/FOCS don't accept enough papers, ask yourself whether there are really 150-200 first tier papers per year in TCS. The right number is probably around 50, and the reason we end up publishing 200 is just so we don't accidentally miss the really good ones.
ask yourself whether there are really 150-200 first tier papers per year in TCS. The right number is probably around 50, and the reason we end up publishing 200 is just so we don't accidentally miss the really good ones.
ReplyDeleteEven if we were to agree to this out-of-the-blue number of first tier papers (and I don't) you are assuming that all those papers go to STOC/FOCS and hence SODA simply picks up the leftovers. In practice, the papers are nowadays evenly distributed to the extent that, as indicated before, STOC and FOCS now routinely publish SODA rejects.
What is rather more interesting is that the STOC/FOCS total number of acceptances has declined slightly over the last fifteen years while the number of theoreticians has increased substantially.
Is it far fetched then to argue that with all this growth there is plenty of room for a third conference of equal (or higher) quality? Of course not! This is only jarring to those who believe that STOC/FOCS (former) higher quality is somehow a God given attribute rather than something that is acquired and nurtured through reasonable steering policies.
As Peter Shor pointed out, not growing STOC and FOCS at the proper time in the past opened the door wide open for other conferences to move in an occupy a space side-by-side to STOC and FOCS quality-wise. SODA and the specialized SoCG have now standards of quality comparable to STOC and FOCS, and many people submit interchangeably to those three, or like David, some even favor SODA over the smallish STOC and FOCS with their reduced reach.
-- SODA is a good conference, but I bet that at most the top 10% of papers there would be accepted to FOCS.
ReplyDeleteClearly not, because FOCS/STOC is too elitist. This has advantages and disadvantages. For example, is good for the ego of people directly involved with FOCS/STOC. But it is certainly bad for the long term perspectives of these conferences, since clearly SODA is growing in size and prestige.
I think STOC/FOCS are much better conferences than SODA for another reason. I have reviewed a couple of STOC/FOCS papers and a couple of SODA papers. As a reviewer for a STOC/FOCS paper it always the case that if I said I had high confidence and gave a low score, then the paper was rejected. However, for SODA it happened once that I gave the paper a very low score--well below what should have been the acceptance threshold--along with a thorough list of the paper's weaknesses.
ReplyDeleteBut the paper got in. This made me have much less respect for the SODA conference.
STOC/FOCS might be doing a good job at picking the best papers in complexity theory.
ReplyDeleteIn several other areas, they do (at best) a marginal job: partially because they lack PC expertise in these areas and partially because they get too few good submission in these areas (since people prefer to submit to the specialized conferences).
Are CG papers in STOC/FOCS better than most CG papers in SODA?
(I am from another area.)
In several cases I reviewed for STOC/FOCS, papers in my area were accepted (against my recommendation) that wouldn't have been accepted to the specialized conference.
Outside complexity, it no longer can be said that STOC/FOCS gets the best crop.
It is hard to make anything out of one isolated example. For SODA, usually a single mediocre review from a p.c. member shoots you down, never mind a negative review.
ReplyDelete> Now that the list of accepted papers is
ReplyDelete> out, go ahead and take a look. SODA is a
> good conference, but I bet that at most
> the top 10% of papers there would be
> accepted to FOCS.
I find this remark somewhat amusing. Apparently, its author managed to evaluate the quality of 135 papers from the titles only. Surely, this should simplify the reviewing process in the future.
What about making these conferences blind review?
ReplyDelete(like other conferences for instance?) I know all the "self-thought" "big-shots" think that this is a ridiculous idea...I think the
theory community is so small that
even the program committe should not
have the right to look at the names...anyway, they are not there to find out who is writing the paper, they are there to judge the quality of the paper based on the 10 pages they have...
I think it will at least filter out the 50% or more 'useless' papers that go in just because....?
Just thinking loud ;)
-- Apparently, its author managed to evaluate the quality of 135 papers from the titles only.
ReplyDeleteAll you have to do is scan for the words "complexity class" or "lower bound" or "bounded depth circuit", if absent, then the papers must be "algorithmic" and thus clearly inferior.
This discussion is getting a little ridiculous. Of course there are papers that are accepted by each of these conferences that have been rejected by the others:
ReplyDelete- Papers tend to improve over time, sometimes based on the comments received when rejected.
- Changes in the expertise of between program committees even for the same conference will make somewhat different decisions.
- The competition changes.
- Probably most importantly, the sheer volume of submissions can make the decisions somewhat of a noisy process.
There is an undercurrent in this discussion that is a legitimate debating point: What is the appropriate amount of selectivity for these conferences givenn that they are unlikely to be extended beyond their 3 days of contributed papers?
Recently, SODA has had 3 parallel sessions (necessitated originally by the inclusion of many short papers, although these no longer exist), STOC has had 2 parallel sessions and FOCS has moved between parallel sessions and single sessions. FOCS has also regularly had a day of tutorials prior to the conference.
The decisions have in part been based on the conference venue; some locations simply do not permit such parallel sessions. Accommodating such sessions can restrict a conference to more expensive locations.
There is a legitimate argument that with a broad conference it is actually more important to have single sessions than at a more narrowly focused conference. Our field thrives on the tremendous cross-fertilization between sub-areas. At a more narrowly focused conference it is more likely that if one has to miss a session there will always be another one available on a not-too-distant topic. Parallel sessions at a broader conference mean that one has to choose between learning nothing about topic X or nothing about topic Y. So much of the success of our field is from the tremendous cross-fertilization between areas and this can be lost. The greater sense of community with single sessions is also an advantage.
I am not sure that I see any significant difference between 2 and 3 parallel sessions; once things are parallel a line has been crossed.
The drawback to single session conferences is also clear. It is a balancing act and I am not sure what the best approach is. In some ways it is good that we not be doctrinaire about it.
Paul Beame
Thanks for the analysis Piotr. Is there a bug in it? It seems to me that in scenario 1, one gets to see f*N the papers, while in scenario 2 one gets to see 3/2*f*N -1/2*N*f^2 percent of the papers. If so then the second number is always larger than the first, i.e.
ReplyDelete(3/2*f*N-1/2*N*f^2) - f*N = 1/2*f*N-1/2*N*f^2 =1/2*f*N*(1-f)
which is non-negative for all values of f between 0 and 1.
- It seems to me that in scenario 1, one gets to see f*N the papers, while in scenario 2 one gets to see 3/2*f*N -1/2*N*f^2 percent of the papers.
ReplyDeleteThat is correct. I think it agrees with what I wrote (although it's late, so I might have missed something). Note that I was switching between the *number* of papers/talks, and the *fraction* (of the total 1.5 f N).
My (guarded) conclusions had to do with the fact that, it is after all, just a model (with a ^*). But it is true that scenario 2 has always higher yield than scenario 1 for f in (0,1).
Piotr
Dear Piotr et al. You can wrap this analysis nicely and subbmit it to the comming STOC. I think that your chances are good :)
ReplyDeleteRe Piotr Indyk's analysis:
ReplyDeleteAvrim Blum and Prabhakar Raghavan wrote a paper addressing the similar question of how to "get the advantages of parallel sessions while still allowing attendees to see all the talks they wanted."
Their solution:"Have four sessions, with each talk given twice."
The analysis involves flows and expanders.
On a Theory of computing Symposia (gzipped ps)
I did a search
ReplyDeletehttps://www.google.com/search?q=soda+focs+stoc
and this was the top result.
More than 16 years after this post was written... I would be happy to read a more up to date discussion.
Correcting previous post, "16" should be "11"
ReplyDelete