The various MSR labs are looking for postdocs and full-time researchers in many scientific fields, including all areas of theoretical Computer Science. You can apply via this website. Please don’t forget to specify in the form all the labs you may be interested in.

For Microsoft Research Silicon Valley applications submitted by December first will receive full consideration.

The deadline for the Schramm Postdoctoral Fellowship (joint with MIT math and Microsoft Research New England)  is also on December first.

As Omer says: dont trust the machine. Make sure that somebody relevant knows you are applying.

The 15th ACM conference on Economics and Computation (EC’14, formally known as “ACM conference on Electronic Commerce”) will be held June 8-12, 2014 at Stanford University, Palo Alto, California, United States.

The CFP is now public and can be found here.

EC’14 will be co-located with a meeting of the NBER Market Design working group, and with the NSF/CEME Decentralization Conference.

While this blog is mostly about theory, today I would like to talk about a real auction and how it relates to theory. I’ll focus on a fundraising auction for my child’s elementary school.

As is common around here, the school has an annual community event called a “Walk-a-Thon” in which donations are collected towards the funding of various programs such as music, band, science, arts, field trips and technology. Most of the money comes from parents (and relatives) that commit to payments proportional to the distance (number of laps) walked by their kids. The next picture shows the first lap.

Kids walking the first lap of the Walk-a-Thon

As part of the event, items are collected and are auctioned throughout the afternoon of the Walk-a-Thon day. The items presented in the auction are very diverse, and include both physical objects and services. Typical items could be crafts made by the kids, parties that parents organize, events like a pizza party organized by teachers, items donated by parents as well as items donated by corporations (and even a pumpkin grown in the school’s garden).

A general view of the auction.

A pumpkin from the school’s garden, ready for Halloween.

The first year I joined the school, the auction was running as a “silent auction” (a format used by many schools for their charity auction). The auction was about 4 hours long with a fixed end time. Items were placed on tables, each item had a bid sheet in which bidders bid (simply a piece of paper attached to the item). The highest bidder for an item wins the auction and pays his bid. Each item had a minimal bid and the bid increment was $1. Bidders were encouraged to submit multiple bids, outbidding each other. When multiple identical items were sold (like in the case of tickets to a party), the highest bidders would win the items, paying their bids. Naturally I was very interested to see how the auction performed. Looking at the auction format, one sees that this is essentially an English auction implemented using bid sheets, so at least in theory (for items with private values) one would expect the allocation to be efficient (and the same as of the second price auction). Revenue should also be very high, as long as each item has enough bidders interested in it. But when attending my first Walk-A-Thon event it was quite clear to me that this optimistic outcome was not being realized, and many prices were much lower than I would have expected. Why was this happening? What are the main differences between this auction and the clean theoretical model? The Walk-A-Thon day is a very busy day for most of the potential bidders (=parents), with many of them volunteering in various activities (like handing water bottles to the kids, or serving food) or simply taking care of the children once they become exhausted from walking. So essentially the bidders in our auction have a high cost of submitting bids, as submitting a bid requires them to leave whatever they are doing, go to the auction and find the item they are interested in, and then write their bid. All this hustle only buys you one bid, while an English auction requires you to keep coming back to the auction and submitting bids until the auction ends or someone bids above your true value. Another fundamental difference is that it is not clear that the private value model holds for some of the items (e.g., when the item is a$50 voucher for a restaurant). Moreover, it is not clear that bidders in a charity auction aim at maximizing their utility in the standard way. Perhaps they have a fix amount of money they want to spend and will maximize their utility given that they exhaust their budget? Finally, the value of some items (like party tickets) depend on whether the same group of friends manages to secure enough tickets, so there are plenty of externalities.

Some people have realized that there is no reason to be active until the last minute, and have used the “sniping” strategy: bid at the last minute just as the auction closes (this strategy is well documented in online bidding). With many occupied with other things, only few people were able to execute this strategy and there were no last minute bidding wars, and the lack of competition resulted in low prices.

It seems as though when people did submit bids earlier, many were basically bidding just $1 above the previous highest bid and not more than that, and many never came back to bid again. While this seems not very rational for a bidder that knows that he might never return to submit another bid, large jumps in the bids were very rare. So how could the revenue of the auction be increased? It seemed to me the main goals should be to decrease the cost of bidding and increase the participation rate. A natural solution is to have a sealed bid second price auction on each item, thus eliminating the need to bid multiple times on each item. This idea was not adopted by the organizing committee as it seems like such a big change might be confusing for the bidders, and the auction committee preferred incremental changes (here’s a constraint that is very rarely put into a formal model, yet exists in many real auctions, including large scale internet auctions). The ideas we came up with will not surprise anyone that is familiar with eBay’s auctions. Instead of moving all bidders to the new auction all at once, the changes will allow “traditional” bidders to continue as before and not do anything new, while allowing (but not mandating) more exploratory bidders to try new options. In the following year we implemented two changes. First, for some items we have added a “buy–it-now” (BIN) price. People could still bid for the item on the bid sheet, but could also buy the item at any time during the auction for the BIN price, and take the item off the auction. The BIN option worked very well. It was extensively used by people that wanted to secure the acquisition of the items immediately as the auction opened. That option worked particularly well for parties, as it allowed buyers to coordinate: people would buy tickets together with friends (their valuation had significant positive externalities; and unlike in the auction, with BIN it was easy to guarantee that some set of bidders win together). Of course one has to set a proper BIN price, and that is a non-trivial task. Although the BIN prices we have posted were much higher than the selling prices in the previous year, the first year we have added BIN for parties, tickets were taken off the auction almost immediately. We raised the price in subsequent years and the result is that we almost quadrupled the revenue from one of the parties! In general it is hard to know how to set the BIN price. One would like to update the BIN price of sold out items in future auctions, but by how much? A possible solution is to sell some of the identical items with BIN and others in the auction, but that was determined to be too complicated by the committee. Another benefit of using BIN is that more people are paying for items throughout the auction and not at the end when there are crowds in line for payments. This further reduces the indirect costs of participating in the auction and is significant when running this kind of physical auction. In the last 3 years we added BIN options to more and more items, mainly of high value, and essentially all parties. For most party tickets with BIN option we have observed that usually all tickets were sold at the BIN price, although we have consistently increased the BIN price every year. The second change we introduced was the addition of Proxy bidding for some of the items. Proxy bids are submitted in a sealed box and are secret (see picture for the table with the boxes). People can still bid on the bid sheet, but the highest of all bids (proxy or open) wins. A proxy bidder that wins pays the minimal amount needed to win. This option is an incremental step towards having a sealed bid second price auction. This option was mainly useful for people that were busy with other activities during the day, and was used extensively and resulted with much more aggressive bids than the open bids, and almost always won the auction. Surprisingly, open bids were still used for items with the proxy option. The auction table, with both bid sheets and boxes for Proxy bids. While proxy bidding are trivial to implement in an electronic system, there are surprising complications when they are done in a physical auction. Once the auction ends, people immediately want to know whether they won, and pay for the item, and it requires some time to manually handle proxy bids. Nevertheless, this option was successful and was adopted extensively, mainly for items of unclear (and private) value, like participating in a party with the teachers. Two other changes we made were aimed directly at accelerating the auction and decreasing the overall cost of bidding. First, we increased the reserve prices. Second, we increased the bid increment from$1 to \$5 on items of high value. Both changes seem effective.

So what have we learned? In the physical world, implementation issues can cause big gaps between the basic theoretical model and practice. Understanding the reasons for these gaps enabled us to make a set of changes that were very effective, and increased the revenue considerably. This was achieved although we do not have a complete theoretical understanding of people’s behavior in this auction, and thus are unable to come up with the optimal auction.

In this post I’d like to report a new and simple proof we found for theorem by Berenbrink, Czumaj, Steger, Vöcking on the imbalance of the balls-into-bins process known as the multiple choice scheme. Full details could be found in the paper. Probably many are familiar with this process, Kunal blogged about some variations of it a few months ago, in any case, I’ll start with a quick primer (shamelessly taken from Kunal’s blog post):

Balls-and-Bins processes are a name for randomized allocations processes, typically used to model the performance of hashing or more general load balancing schemes. Suppose there are $m$ balls (think items) to be thrown into $n$ bins (think hash buckets). We want a simple process that will keep the loads balanced, while allowing quick decentralized lookup. We measure the balance in terms of the additive gap: the difference between the maximum load and the average load.

The simplest randomized process one can think of is what is called the one choice process: place each ball in an independently and uniformly sampled bin. Many of us studied the $m=n$ case of this process in a randomized algorithms class, and we know that the load is $\Theta(\log n/\log\log n)$ except with negligible probability (for the rest of the post, I will skip this “except with negligible probability” qualifier). What happens when $m$ is much larger than $n$? It can be shown that for large enough $m$, the load is roughly $m/n + \sqrt{ \tfrac{m\log n}{n}}$ (see this paper for more precise behavior of the gap).

Can we do better? Azar, Broder, Karlin and Upfal analyzed the following two choice process: balls come sequentially, and each ball picks two bins independently and uniformly at random (say, with replacement), and goes into the less loaded of the two bins (with ties broken arbitrarily). They showed that when $m=n$ the load of the two choice process when is significantly better: only $\log\log n$.

The proof uses a simple but clever induction. The induction is not on the number of balls nor on the number of bins. Say we know an upper bound $\beta_i$ on the fraction of bins with load at least $i$, the proof shows how do derive a bound $\beta_{i+1}$ on the fraction of bins with load at least $i+1$.

Induction base: Since only $n$ balls are thrown we know that at most $n/3$ bins contain at least $3$ balls, so $\beta_3 \leq 1/3.$

Induction step: As more balls are put in the bins the fraction of bins with load at least $i$ only increases, so if $\beta_i$ is an upper bound on the fraction of bins with load at least $i$ at the end of the process, it is also an upper bound in any other point in time. The key observation is that the number of bins of load at least $i+1$ is bounded by the number of balls which were placed at ‘height’ at least $i+1$. For a ball to land at height at least $i+1$ both its choices need to be at height at least $i$. The inductive hypothesis asserts that the fraction of such bins is at most $\beta_i$, so the probability a ball indeed lands at height at least $i+1$ is at most $\beta_i^2$. There are $n$ such balls so the (expected) total number of balls (and thus bins) of height at least $i+1$ is at most $n\beta_i^2$. In other words, the inductive step implies the following recurrence: $\beta_{i+1} = \beta_i^2.$

Since each inductive step the beta’s are squared, after $\log\log n$ steps the fraction is less than $1/n$ and (modulo some details) we are done!

The proof as sketched above relies on the assumption that the number of balls is $n$. We needed that for the base of the induction and for the inductive step. What happens when $m>>n$? The technique as described above seems unfit to handle the heavily loaded case. Other proof techniques that use differential equations and witness trees also seem unsuited to analyze the heavily loaded case (See this nice survey).

A breakthrough was achieved in a remarkable paper by Berenbrink et al. In that paper they proved that the same bound on the gap holds for any, arbitrarily large number of balls:

Theorem: For every $m$, the maximum load is $m/n + \log \log n + O(1)$ w.h.p.

Note that the additive gap between maximum and average is independent of $m$. Contrast this with the one choice case in which the additive gap diverges with the number of balls.  This is very meaningful, say there are 100 bins and 100,000 balls, the gap between max and average is less than 3 with two choices, while it is roughly 80 when using one choice.

From a (very) high level their approach is the following: first they show that all the action is in the first poly$(n)$ balls, in other words, the gap after $m$ balls are thrown is distributed similarly to the gap after only poly$(n)$ balls are thrown. This is done by bounding the mixing time of the underlying Markov chain. The second step is to extend the induction sketched above to the case of poly$(n)$ balls. This turns out to be a major technical challenge which involves four inductive invariants and plenty of calculations, some of which are computer aided. Moreover, these calculations need to be redone whenever the model is tweaked.

Our hope is that our simpler proof will make this beautiful theorem more accessible.

We take a different approach. The main tool we use is a theorem from our previous paper on the topic which directly implies a weaker bound. This bound is then sharpened to yield the tight $\log \log n$ bound on the gap.  First we need a simple definition:  The gap vector at time $m$, denoted by $X(m)$, is the $n$ dimensional  vector specifying the additive gap(= load – average) of the $n$ bins after $m$ balls were thrown.   The lemma we use states that an exponential potential function has linear expectation:

Lemma (1): There exist universal $a>0,b>0$ such that $E[ \sum e^{a|X_i(m)|}] \leq bn$

What can we learn from the Lemma? It  immediately implies a bound of $O(\log n)$ on the gap for every given $m$.  In fact the bound is on the gap between the maximum and minimum, and as such it is tight. What we need however is a finer bound of $\log\log n$ on the gap between maximum and average.

So, lets assume $m$ balls were thrown, and the max gap is say smaller than $\log n$. The key idea is to analyze what will happen after we throw $n\log n$ additional balls, i.e. at time $m+n\log n$. First of all, the average would move up from $m/n$ to $m/n+\log n$ which is beyond the current max gap, so all balls contributing to the gap at time $m+n\log n$ were indeed thrown in the last $n\log n$ time steps. This means that we can now prove a bound for time $m+n\log n$ by essentially repeating the inductive step as was described above. In the description above we used the fact that $n$ balls were thrown, but nothing terrible happens if $n\log n$ balls are thrown instead. The more serious obstacle is to find a base case for time $m+n\log n$. Recall that when $m=n$ it must be the case that  $\beta_3 \leq 1/3$, this of course doesn’t hold when the number of balls is arbitrarily large.

The crucial observation is that Lemma (1) gives just that! It shows that the fraction of bins of gap at least $\log \log n$ (at time $m+n\log n$) is at most $O(1/\log n)$ so we can start the argument  with the base case $\beta_{\log\log n} \leq 1/ \log n$ and then continue as usual.

The induction essentially tells us that if we know that at time $m$ the gap was at most $\log n$, then after throwing $n\log n$ additional balls the gap is reduced to $O(\log \log n)$. If we now throw $O(n\log\log n)$ additional balls and repeat the argument, the gap is reduced to $(1+o(1))\log \log n$.

It is important to point out that we haven’t recovered the theorem of Berenbrink et.al. at full strength. We get a weaker tail bound for the probability the gap is larger than the expectation, as well as worse low order terms on the expectation itself.

On the plus side this technique is general enough to capture many variotions on the basic model. Consider for instance a scenario where balls are asigned random weights: when a ball is placed its weight is uniformly sampled from the set $\{1,2\}$. One would naturally expect the maximum gap to be bounded by $2\log\log n$. Indeed the proof above shows just that with minimal changes.

tags:

FOCS 2013 is over, and as predicted here it was very successful. I am happy to have taken part in its success (though all of the credit goes of course to the authors).

I also predicted that “A significant fraction of the community will think the PC messed up badly.” Naturally, most of the people with a paper at FOCS were generally happy with the PC work so I did not get too many complaints :-) (but I did get some). What I did find was that FOCS/STOC attendees passionately care about FOCS/STOC. I therefore got to hear quite a few personal philosophies about what’s good and bad in FOCS/STOC and what should be changed. The interesting aspect is that the opinions were at times the exact opposite:

• Some think (as also reflected in the comments here) that the conference has become too competitive and selective which is why FOCS/STOC is less important now. Others think that FOCS/STOC are accepting too many papers and in this sense the PC is not doing its job of filtering and therefore FOCS/STOC does not serve the purpose of joining TCS and is less useful.
• Some feel that authors and speakers in FOCS/STOC are drowning the audience in technical details rather than sharing ideas and this happens in part because FOCS/STOC papers are judged by experts in their subfield rather than by the community at large. Others expressed rage that the papers aaccepted in their subfield are far from being the best papers submitted. They say that this happens because they are judged by general TCS experts rather than by the subfield experts.
• Some think that FOCS and STOC should be joined into a single bigger event that will draw the attention of the entire community (but with multiple submission deadlines such as is now happening in other fields). Other think it is a horrible idea and two conferences are extremely important.
• The business meeting saw some exciting arguments on various topics.
• Sanjeev and I had a vigorous discussion  (to be continued I am sure) on the no-page-limit policy initiated by the FOCS 2013 PC.

As you might have realized by now, I am passionate about FOCS/STOC as well. The experience of chairing FOCS made me think about it much more and I have various ideas about changes to be made (I did express my ideas even before but I have refined them since). But the abovementioned discussions indicate to me that (1) FOCS/STOC is still extremely important to many of us, (2) changes should be gradual and controlled as we have such a diverse set of expectations.

After things settle in my mind, I may blog some more about what I think should be done, but for now let me just say that I believe the following combination is important and possible: FOCS/STOC should allow wide active participation (in numbers larger than today and by a more diverse community). On the other hand a small enough (and humanly digestible) part of the program should facilitate cross fertilization and information flow between the sub communities. The federated theory conference which so many of us support is a good idea but only part of the solution.

In this guest post, Sanjeev Arora will share some thoughts about the future of scientific publishing in our community. This is not unrelated to our last post, and is also aimed at initiating discussion towards FOCS 2013 that is starting in the coming weekend.

As always, comments are most welcomed with the reminder that WindowsOnTheory maintains a policy of keeping the discussion respectful and on point. And now to Sanjeev:

——————————-

Thoughts on paper publishing in the digital age.

What role should journals and conferences play in the age of arxiv, twitter and other yet-to-be-invented digital wonders? Detecting among many colleagues a general impatience with the status quo, I wrote this blog post to generate more public discussion. I am thinking here purely of theoretical computer science, not other fields.

It is possible now to envision a world where journals and conferences are replaced by arxiv and other depositories, which come with the added benefit of instant “impact metrics” (pageviews, number of tweets, etc.). Machine learning researcher Yann Le Cun has taken this viewpoint to its logical end, arguing for  a “free-market”system with papers subject to a distributed market model for refereeing/commenting. Independent consortia of reviewers (basically a new name for journals and conferences of the future??) would decide to publish reviews of arxiv-ed papers —with or without the permission of the papers’ authors.

At the other end of the spectrum, Lance Fortnow is troubled by the steady decline of journals and proliferation of conferences, and its bad effects on scholarship. He seeks to restore the importance of journals, and lower the prestige of conferences (by greatly raising acceptance rates).

Is Arxiv enough?

Physics is one of several fields that have taken enthusiastically to e-publishing. A physics paper on arxiv may have followup papers within weeks or even days.

While this model has some plus points, one also see dangers:(a) incentive to write shallow and incremental papers; (b) more priority disputes and the temptation to publish sketchy ideas in order to later claim full or at least partial credit; (c) lack of incentive for good reviewers to volunteer time reviewing enough papers (despite the attempted analogy to free market in Le Cun’s proposal).

Let me elaborate on (b). The following already seems to be an axiom among my younger colleagues: “If a result appears on arxiv, you have a few days to put up your independent manuscript. After that you can’t claim independent discovery.” Some other disciplines have already moved on to a more cutthroat model: “Whoever gets to arxiv first wins. “

Surely, this must incentivize hasty writing and incomprehensible papers. Or maybe papers that even have errors —but fixed in the weeks or months in subsequent versions. In the past we relied on conference committees and journals to adjudicate such disputes. How would that happen in a distributed market? One can imagine systems involving feedback buttons, reliability ratings etc. but it seems a dubious method of doing science.

An attraction of the “free market” approach at first sight is that unknown researchers can publish on equal footing with established ones. But in reality things may turn out less fair than the current conference system. Prominent researchers will have bigger megaphones (e.g., more twitter followers or friends willing to review their papers) and tend to benefit.  Power centers will inevitably form in any system.

By contrast, conferences in theoretical CS —perhaps because each PC is a fresh set of 25 individuals—have a good track record of showcasing great work by grad students and postdocs, and giving best paper awards to people I —and probably many others—had never heard of before. And plenty of Turing award winners get their papers rejected.

Conference vs Journals?

Historically, conferences came to dominate computer science because they allowed fast dissemination and a convenient place to catch up on the latest research/gossip. Today, both goals can increasingly be met by other means, so can we still justify conferences? It is interesting that Fortnow and Le Cun, despite being on opposite ends of the spectrum, agree about the irrelevance of conferences.

Let’s now list factors why conferences still make a lot of sense. My focus here is on promoting better science — I worry less about promotion/tenure policies since they will quickly adjust to accommodate any new dissemination method we choose (including arxiv and twitter). Also, I apologize in advance for occasional forays into pop psychology.

(a) Incentive system for good researchers to (sort-of )review lots of papers.

There simply isn’t enough refereeing capacity to properly referee all the papers at get written.  When fields rely solely on journals (eg, economics), backlogs can make it difficult for young researchers to get published —many have no publications when they finish their PhD. Also, accept rates of 5% force editors to be risk-averse.

The PC review system in theoretical CS is not perfect, but better than those in many other fields. The social pressure of a face-to-face PC meeting seems to make members take their reviewing quite seriously.

Also, many researchers seem happier to serve on a STOC/FOCS PC once every 3-4 years rather than on a journal board for 3-4 years. Perhaps humans prefer shorter but more intense pain to a longer and less intense one.  Or perhaps journal boards are less interesting because you end up handling papers in your own speciality, including those you already saw 2+ years ago.

(b)Incentive system for researchers to produce a substantial piece of work, and then write it up —sort of comprehensibly—in 10 pages.

The incentives in the arxiv model are quite the opposite —more frequent, insubstantial, and hastily written works.

The 10page limit —archaic relic of the papyrus era— and the PC model has led to our tradition of writing papers that are sort-of comprehensible to nonspecialists.

(c) Clearing point for deciding upon priority, novelty, correctness etc. of claimed results.

Conferences can do it faster and better than journals in most cases, at least under current rules (a jury of 20-25 PC members versus a jury of one editor and 2-3 random reviewers). The informal refereeing system at conferences at first glance seems to invite abuse but I can think of very few accepted papers at STOC/FOCS in the last 30 years that turned out to be very flawed (and often those were recognized as controversial when accepted).

(d)  A stamp of authority, or a recommendation if you will.

We increasingly need this guidance from conference PCs to stay afloat in the sea of new papers, especially outside our sub-specialities.  That is why I go to STOC/FOCS these days, not social networking (which is a nice bonus though). I could stay at home and watch videotaped talks but, really, who does that?

(e)  A synchronization mechanism for our field.

Is it just my imagination, or do conference deadlines actually enhance collaborations and improve productivity/creativity? Half-imagined results get fleshed out as people get together in the months or weeks before the deadline (and I am not referring to caffeine-fueled late-night finishes, which I avoid). We need this synchronization to structure our busy lives, and neither arxiv nor journals provide it. If you don’t care for the human weaknesses this argument stands on, I should mention Boaz Barak’s alternative explanation: sometimes correlated equilibria are superior to Nash equilibria.

Proposals to improve conferences in theoretical CS

The ongoing experimentation—a day of workshops, poster session, recorded talks, no paper proceedings, better feedback from PC—has been good.  Here are my thoughts for further improvement.

• Keep the conference format (say 12 pages, 11pt).  But to reduce work and give an incentive to produce a readable version, make the submission format identical to the published format.(I admit to having done my share of grumbling about the conference format, but on balance it is important for our field that 50-page arxived papers should be accompanied by shorter, more readable, versions. If you think 12 pages is too few, try vying for the privilege of publishing your result in Science and Nature —in 2-4 pages!)

• Increase number of acceptances moderately. (Beware though of Parkinson’s law: submissions increase to fill all available refereeing capacity. So don’t agonize if acceptance rates stay below 30% despite this increase.)But, reduce number of talks. (In other words, not all accepted papers are treated equally by the PC.) Have more plenary talks.

• To combine some of the speed of arxiv with reliable timestamping, have two submission deadlines a year —papers appear on the website as soon as they are accepted in the first cycle, and papers rejected in the first cycle cannot be resubmitted for another year.  Variants of this model have been tested in other fields (databases, ML). This spreads out a PC’s work over a longer period, which has its pluses and minuses.
• It would be nice —perhaps independent of conferences—to have a forum for posting reviews/comments on theory papers. (Hints of Le Cun’s ideas here.) To be useful we must avoid the vicious smallness of blog comments. Requiring posters to use verifiable identities should preclude the worst abuses (the system only needs to scale to a couple thousand users).
• Last but most important: keep the various points made in this article (or any other set of principles discussed and agreed upon collectively) in mind when proposing new changes.

Despite its small size, theoretical CS has been remarkably successful. An incredible edifice of ideas was created together with an open culture that values the need to address papers and talks to nonspecialists. This allows ideas and techniques to jump rapidly across subspecialities.  Theory conferences played an important role in creating that culture, and we should think hard about maintaining their good elements in the digital era.
To finish, I must admit that when I started this thought process (and discussions with colleagues) I started out somewhat skeptical  of conferences but ended up strongly in favor. I’m decided to be more willing to combat the cynicism I often see in such discussions; hence this blog post.

People’s views tend to be colored by their last conference rejection. Typically, senior people fume about youngsters who value technical sophistication or over conceptual contributions. Young researchers in turn feel anxious about being judged by a power structure that they don’t fully understand or feel part of. Such anxieties have existed since prehistoric times—there is no way to do research and not have it be misjudged at times. Cynicism is not a good response.

“Time for computer science to grow up” by Lance Fortnow.

New publising model for computer science by Yann Le Cun

A full issue of Nature devoted to this topic:

# Some comic relief (article from 1967): The future of scientific journals. A computer-based system will enable a subscriber to receive a personalized stream of papers.

(Acknowledgements: Useful discussions in recent weeks with all my Princeton colleagues —Moses, Bernard, Avi, Mark, Zeev– and ex-Princetonians Boaz Barak and Ankur Moitra.)

The business meeting of STOC/FOCS is usually rather tedious, but it is also an opportunity to raise and debate issues that the community should be concerned about. One such issue is the inconsistency between our publication norms and the norms of other communities. This is becoming more and more important as TCS megalomaniacally adopt the “lens on the sciences” point of view. Towards the FOCS 2013′s business meeting, Umesh Vazirani agreed to write a guest post on this subject. While Umesh mentions Science and Nature, this is relevant to other communities (Econ journals come to mind).

I would love to encourage the readers to start the debate by commenting here. Please remember though that WindowsOnTheory maintains a policy of keeping the discussion respectful and on point. And now to Umesh:

———-

Here is a recently discovered theorem about STOC/FOCS: the rules spelled out in the STOC/FOCS CFP imply that you cannot have a STOC/FOCS paper whose journal version appears in Science or Nature. Authors are forced to choose: if they choose Science/Nature then our community suffers since we do not get to hear about some strong papers and new directions; if they choose STOC/FOCS, then it diminishes our community’s influence in the sciences.

This is not a purely theoretical concern. There was already a paper that we submitted to ITCS instead of FOCS 2012 for such reasons. It appeared in Nature earlier this year: http://www.nature.com/nature/journal/v496/n7446/full/nature12035.html But the new STOC/FOCS theorem was only fully proved in the context of a paper by Thomas Vidick and myself that resolved a longstanding challenge by Myers and Yao about device independent quantum cryptography. That paper was accepted to STOC, but the subsequent proof of the STOC/FOCS theorem led us to withdraw the paper and we are now in the process of submitting it to Science. Both these papers represent the kind of computational lens on the sciences kind of thinking that our TCS community should be actively engaging in and taking credit for. The phenomenon is not restricted to those two papers – a number of other papers have since chosen to forgo the STOC/FOCS route for the same reasons.

There are two basic issues: the first and larger one is that STOC/FOCS explicitly bans journal publication before the date of the conference. The motivation cannot be suspense, the arxiv has long rendered that moot. It is also clearly not an issue of ”double publication”, in view of the long accepted norm that papers appear in both a conference and a journal. ACM and IEEE copyright policies might have been implicated, but a close reading of those policies reveals that they treat journals and conferences symmetrically, and so have no implications for the order of publication.

The second issue has to do with the recently formalized (or invented) policy of STOC/FOCS to insist on the publication of a full 10 page abstract in the proceedings as an obligation rather than as a privilege. By contrast a 1 page abstract with a pointer to a full paper on the arxiv would not preclude publication in Science/Nature after STOC/FOCS. One could go much farther and note that conference proceedings, which were once the life blood of the theory community, have been increasingly marginalized by the arxiv and the web. A sensible policy would be to take STOC/FOCS proceedings online, with pointers to papers on the arxiv. Without compromising any of the attributes of the current proceedings, this would have the added benefit of reducing the time between abstract submission and conference date, thereby leading to the inclusion of more up to date results in the conference.

Whatever the theory community decides, I hope it will be an active scientific decision rather than the current bureaucratic default.