Dating a result..

The PCP results appeared in conferences in 1992, Sanjeev Arora's thesis appeared sometime after, and the "journal version" appeared in 1998. Similarly, the PRIMES in P result was announced in 2002, but was published in the Annals of Math in 2004.

If I'm trying to write something that talks about the history of a set of results (let's say I'm talking about PCP), it is generally recommended that I cite the definitive version (i.e the journal paper). So I'd talk about a PCP result "published in 1998", which seems silly given that everyone knows it appears much earlier. Given the lag time of CS journals, this is more of a problem than in other areas.

Is there any clean way out of this dilemma ? Should I cite the journal, but attempt to avoid any mention of dates in the text ? Should I use the "first published date" in the text, and cite both the earlier, conference version, AND the journal version ?

Maybe it doesn't matter, because the only results worth announcing well before publication are so famous that such questions are moot, and "everyone knows when it appeared". I don't have answers here: I'm just confused.

Presidential candidate wants to repeal undecidability.

From CNET, via BB, and Ed Felten:

Sen. Sam Brownback (R-Kansas) on Tuesday reintroduced the Truth in Video Game Rating Act, first proposed last September. It calls for requiring video game rating organizations to play all games "in their entirety" before issuing labels and prohibiting game developers from withholding any "hidden" game content from raters. It would also punish ratings groups that "grossly mischaracterize" any game's content.

That's right: he wants to have games played till they terminate, in order to have them certified. I guess it's time to dust off those "Pi = 22/7" legislations.

Fran Allen, Turing Award, 2006

Fran Allen, Fellow Emerita at IBM, has been named this year's Turing Award winner. She is also the first woman to win this award.

WADS deadline fast approaching

For those of you nursing your poor SoCG/STOC/PODS rejects, the WADS deadline is fast approaching. WADS (The Workshop on Algorithms and Data Structures) alternates annually with SWAT, the Scandinavian Workshop on Algorithm Theory, and is being held this year in Halifax, Canada. Lest the title fool you, WADS is actually an honest-to-goodness conference; proceedings are published in an LNCS issue.

The deadline is Feb 23, more than enough time to even invent a problem, solve it, write a snappy intro, and send it off. So get cracking !

Update: The deadline has been moved to Mar 2. Heck, you could write TWO papers in that time.

p.s Not that the WADS folks are asking for my opinion, but I don't like it when conferences shift deadlines.

STOC 2007 Results out

Via Piotr, the STOC 2007 results are out. They are sneakily hidden on Uri Feige's home page, so if you go to the STOC page, you don't see them.

77 papers made it in: I don't know how many were submitted (Update: 312, quite a healthy number). As is often with STOC, the titles are somewhat inscrutable, so it's hard to spot papers that might be interesting.

Some notable entries:

• Computing crossing number in linear time, by Ken-ichi Kawarabayashi and Bruce Reed:

  For a fixed k, they determine whether a graph can be drawn with crossing number at most k, and if so, construct such a drawing, all in time linear in n. This improves an earlier quadratic time algorithm of Grohe.
  

• Combinatorial Complexity in o-Minimal Geometry, by Saugata Basu.

  A continuation of his work on estimating complexity of various topological quantities, for even more generally defined subsets of Rⁿ.

• Fourier meets Möbius: fast subset convolution, by Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto.

  An application of the Möbius transform, in a kind of generalization of the use of Fourier transforms, but for subset convolutions.

• Lower Bounds for Randomized Read/Write Stream Algorithms, by Paul Beame, T. S. Jayram and Atri Rudra.

  This is another in a series of papers that I really must read, given how it reminds me of things I was dabbling in involving graphics cards. The quirk of this model is that the stream algorithm can write onto streams as well as reading from them; memory is limited, but not intermediate storage (for writing such streams)

Parochial concerns section: by my count, 6 geometry papers, which is fairly decent.

Fastlane and Holidays

As many of you are painfully aware, the NSF deadline for theory proposals is this Monday, Feb 19. As you may have also realized, Feb 19 is a federal holiday. According to NSF guidelines, in such an event, the deadline moves to the next working day (i.e the 20th) and I've confirmed that this is a correct interpretation for this deadline.

However, does Fastlane itself know this ? Suppose Fastlane refuses to accept any proposal submitted after Feb 19 (since in principle it has the information on the call and the deadline) ? Can the program manager then override it ?

I wonder if anyone has any experience with this...

Valentines for my current state...

• XEmacs, AUCTeX and RefTex
• The pre-coded BibTeX at the ACM DL and DBLP
• Pandora.com

New Research Center in Massive Data Algorithmics

Lars Arge, crown prince of massive data set algorithms, informs me that MADALGO, a new research center devoted to massive data algorithmics, is now up and running.

Several Postdoctoral positions at the level of Research Assistant Professor of Computer Science are available. Initially, the positions are for one year, but they can be extended by mutual consent. Applications are welcomed from researchers with clearly demonstrated experience and skills in the design and analysis of algorithms and data structures. Applicants with experience with I/O-efficient, cache-oblivious or streaming algorithms, as well as with implementation of such algorithms (algorithm engineering experience), will be preferred. The responsibilities of the candidates include work on algorithms for massive dataset problems in collaboration with center researchers, along with modest teaching responsibilities.

It's a great opportunity if you're looking for somewhere to do a postdoc, and like mucking around with lots of data. Massive data problems have added a profound new dimension to algorithms research, and this center will really help push research in this area forward. There are also Ph.D student positions available.

Weird BibTeX problem

This is puzzling me, and I am hoping my readers might help:

I want to add a reference to this entry:

@article{ref,
author = {First Last and First M. Last, III},
title = {Insert Title Here},
journal = {Int. J. Comput. Sci.},
volume = 1,
number = 1,
year = 2010,
pages = {137--154},
}

and it comes out looking like this (in my .bbl file):

\bibitem{ref}
{\sc Last, F., and First M.~Last, I.}
\newblock Insert Title Here
\newblock {\em Int. J. Comput. Sci 1}, 1 (2010), 137--154

As you can see, there are two problems:

1. The second name is not formatted in the style of the first
2. The second author has been replaced by their grandparent (!) (the III has been replaced by I).
   

This is using the acm.bst style file. I tried using plain.bst, and the problem persists: the second author is listed as III First M. Last.

I tried standard tricks like enclosing the III in braces, placing commas in certain places, removing them etc. No luck.

Carnival of Mathematics

First there was the Tangled Bank, and then Philosophia Naturalis. Now we have the prosaically named Carnival of Mathematics, a round up of all the mathy goodness in the blogosphere. Your 'umble blogger has an entry or two, but more importantly, there are lots of interesting posts from blogs I had never heard of before. Time to update those blogrolls !

Have all ideas already been thought of ?

Amidst a superb reflection by Jonathan Lethem on ideas, the marketplace, and copyright, consider this section, on ownership of ideas:

Undiscovered public knowledge emboldens us to question the extreme claims to originality made in press releases and publishers' notices: Is an intellectual or creative offering truly novel, or have we just forgotten a worthy precursor? Does solving certain scientific problems really require massive additional funding, or could a computerized search engine, creatively deployed, do the same job more quickly and cheaply? Lastly, does our appetite for creative vitality require the violence and exasperation of another avant-garde, with its wearisome killing-the-father imperatives, or might we be better off ratifying the ecstasy of influence—and deepening our willingness to understand the commonality and timelessness of the methods and motifs available to artists?

The "ecstasy of influence": what a beautiful way to describe the joy of illumination when we read a beautiful theorem, or a profoundly elegant idea, and use it to build something of our own.

SoCG results out

45/139 acceptances (Congratulations, David) for a 32.3% acceptance rate. Nope, no one's getting tenure with that number :)

The list will be up shortly. Since I was on the committee, I am loathe to make specific comments about papers that I liked. Suffice it to say that I am looking forward to going to Korea.

Update (7/702): And here it is.

The Geometry of Morality

From Indexed, via BB: What do the diagonals of the seven deadly sins represent ?

Some good news on funding the NSF

As has been reported in many places, the House has passed a new spending bill that puts back many of the American Competitiveness Initiative funding that was proposed for FY07. This bill was passed in agreement with the Senate, so Senate passage is hopefully forthcoming next week, when it's taken up there.

There are some differences in the level of the increase. According to Peter Harsha at the CRA blog,

Under the agreement, NSF would receive a 6 percent increase, slightly below the 7.8 percent increase called for in the ACI, but $335 million more than FY 2006.

But according to the AAAS funding update,

The National Science Foundation (NSF) would receive the full requested increase of 7.7 percent or $334 million for its core Research & Related Activities (R&RA) account to $4.7 billion. This funding would allow most research directorates to reverse declining funding of recent years with increases of between 6 and 8 percent. Total NSF R&D would climb 7.0 percent to $4.5 billion within a total budget of $5.9 billion, reversing two years of cuts in 2005 and 2006

Of course, the President still has to sign the bill. But since the ACI was his idea, one can be hopeful.

Visiting Barbados

The SoCG PC meeting was held this year at the Bellairs Research Institute in Barbados, in conjunction with a joint McGill-INRIA workshop on limited visibility, organized by Hazel Everett, Sylvain Lazard, and Sue Whitesides. It was my first time in Barbados; people have been coming to such workshops every year for many years now, and there's a nice core group of people who know how the system works and where all the good eating and drinking joints are.

Bellairs is a fairly minimally equipped research facility, smack bang on the beach on the Caribbean (i.e nicer) side of Barbados - shared dorm rooms, common bath areas, common kitchen, and the like. The facilities are much more basic than say, Dagstuhl, but this is more than made up for by the beauty of the surroundings (Did I mention that it was smack bang on the beach?). In fact, if you walk a few steps from the gate of the Institute, you end up on the beachfront of a swanky nearby hotel, which is rumored to have rooms that cost $700/night, with a 14 night stay guaranteed.

The communal aspect of the facilities (everyone cooks, we all make breakfast together, people share in the costs for food, beer, rum, rum, rum, and more rum) makes the workshop a rather friendly place. I was only there a few days alas, but the mere notion of a schedule where you work in the morning, take the afternoon off, and reconvene after dinner seems so natural, that I was wondering whether we could actually do this at SoCG or other conferences.

The workshop starts off with people proposing all kinds of problems loosely organized around the theme of limited visibility, and then people go off into self-organized groups to work on whatever seems interesting. Every now and then, there's a public review session to discuss progress. This model works surprisingly well, and all kinds of nice puzzles pop out of the discussions.

It's a great environment to do relaxed research in; not having the internet for a few days made looking up results a little tricky, but it was manageable. My main regret in leaving early: I didn't get a chance to go to the (in)famous Rocky's Bar.