The FOCS accepted papers (with abstracts) have been posted. Since not every conference is doing this, I think it bears repeating that the addition of abstracts to these lists is a very welcome innovation of recent years.

And while I'm making a short link-only post, an amusing photo gallery that I was pointed to recently: the Russian solution to the art-gallery problem.

I just returned from Montpellier, France, where I was invited to speak at WG 2009, the 35th International Workshop on Graph-Theoretic Concepts in Computer Science.

This was my first trip to France, and Montpellier was a very charming place to visit. It is in the south, and though not quite on the Mediterranean itself it has a very Mediterranean feeling. The conference organizers put together an interesting and educational excursion for us in which we learned some of the local history by visiting three local landmarks (the opera house, an old pharmacy, and the top of the gateway arch) and drinking a different wine in each. We learned that Montpellier is a new city for France, being only a little over 1000 years old, but it is home to one of the oldest medical schools in Europe. It's on the old pilgrim trail from Rome to Compostela, markers for which run through the town, and although the language is no longer spoken in the area there are several inscriptions for tourists written in Occitan. The nearby mountains were a refuge for the Cathars when they were persecuted by the Catholics, and there are many open squares in the city due to the monasteries and other buildings that were torn down in the French revolution. My hotel was on one side of the old quarter, now mostly a shopping district, and the conference was in an old movie theater on the other side of the quarter, so I had a very pleasant walk every day to the conference (only getting lost twice), and my bad high-school French was enough to get by with the people who didn't or wouldn't speak English (rather more of them than I've encountered in other parts of Europe).

The conference itself is about graph algorithms, both for problems on arbitrary graphs and (a larger fraction of the papers) for important special classes of graphs. There were too many interesting talks to describe them all in detail, so let me just mention a few.

( Read more... )

All in all, a good conference, and one I would attend much more regularly if only it weren't so far away.

The 25th ACM Symposium on Computational Geometry just finished yesterday. Suresh has already reported on the pre-conference historical review of computational geometry, but I thought I'd mention a few highlights of the conference itself.

( Read more... )

All in all, a good conference.

A reminder: the Graph Drawing Symposium submission deadline is approaching. Get your graph drawing submissions ready!

We recently changed the submission deadline, from May 31 to June 3, to articulate better with some other conference deadlines. Unlike previous years' extensions we've tried to make this change sufficiently early that it will also be useful for providing extra time to write new submissions.

A warning, passed along from Phil Klein: if you have any old web pages lying around with URLs pointing to focs.org or focs****.org, you should change them to the links listed in Wikipedia's page on FOCS. It seems the .org domains have been taken over by domain-name spammers.

The list of accepted papers at WADS is out: go to the main WADS site and click on the "accepted papers" tab at the top of the page, or follow this direct link.

I'll post about own my papers there later when I have preprint versions available to link to. The rest of the program looks fascinating; I'm looking forward to finding out what all those intriguing titles actually mean.

Longtime algorithms researchers will remember that in the 1980s, parallel algorithms used to be a hot topic, but that it faded as Moore's law caused new single-processor machines to be faster (and much easier to program) than parallel computers made with many older and cheaper processors. Nowadays, Moore's law itself has faded (or, more accurately, stopped leading to single-processor speedups) and parallel computing has been making a comeback, especially as many researchers have realized that we already have powerful and highly parallel processors cheaply available to us in the graphics coprocessors of our home video game systems. Researchers such as (at UCI) graduating student Nodari Sitchinava and his advisor Mike Goodrich have been hard at work on developing analysis models and algorithms for these new systems and figuring out how many of the old PRAM-algorithm techniques can be carried over to them. But there has also been a lot of work in this area in non-theory communities that could benefit from our theoretical expertise. In part, this is one of the themes of the Workshop on Massive Data Algorithmics to be held in conjunction with SoCG in Aarhus this summer, and older parallel algorithms conferences such as SPAA have also adapted to these new directions.

Uzi Vishkin has asked me to publicize another workshop, even more focused on this subject, to be held a little closer to (my) home. The Workshop on Theory and Many-Cores is to be held in College Park, Maryland, on May 29, 2009, the day before STOC and in the same state. There's an abstract submission deadline of April 27 (less than two weeks away). As the conference announcement states,

The sudden shift from single-processor computer systems to many-processor parallel computing systems requires reinventing much of Computer Science (CS): how to actually build and program the new parallel systems. Indeed, the programs of many mainstream computer science conferences, such as ASPLOS, DAC, ISCA, PLDI and POPL are heavily populated with papers on parallel computing and in particular on many-core computing. In contrast, the recent programs of flagship theory conferences, such as FOCS, SODA and STOC, hardly have any such paper. This low level of activity should be a concern to the theory community, for it is not clear, for example, what validity the theory of algorithms will have if the main model of computation supported by the vendors is allowed to evolve away from any studied by the theory. The low level of current activity in the theory community is not compatible with past involvement of theorists in parallel computing, and to their representation in the technical discourse. For example, 19 out of 38 participants in a December 1988 NSF-IBM Workshop on Opportunities and Constraints of Parallel Computing in IBM Almaden had theory roots. The lack of involvement of theorists should also concern vendors that build many-core computers: theorists are often the instructors of courses on algorithms and data-structures, and without their cooperation it will be difficult to introduce parallelism into the curriculum.

The main objective of the workshop will be to explore opportunities for theoretical computer science research and education in the emerging era of many-core computing, and develop understanding of the role that theory should play in it.

There's still time to get something together for this, so get working! And I'm sure Uzi would appreciate workshop participants who want to learn more about this subject but are not ready to speak on it themselves, as well.

As we've already discussed on Mihai's blog a month ago, this year FOCS has a strange new procedure: a week after the real submission deadline, one has to submit a two-page brief description. Now, via Muthu, we get a little more information about what this is supposed to mean: Umesh Vazirani's proposal for including them in the submission process and several examples of brief descriptions for past FOCS/STOC papers.

While it's helpful to have greater clarity, I have to admit that I still don't see why one would want to make such a thing significantly different than the first two pages of one's paper. All of the purposes it supposedly serves, of attracting readers to the paper and providing a brief hint at the more technical material to follow, are purposes that it would be good to fulfil in one's real introduction. And from my reading the proposal, specifically the part about “reluctance of senior researchers in the field to serve on STOC/FOCS committees,” implies that these senior researchers are lazy and would only judge papers by the first two pages anyway, and explicitly encourages them to do just that. Having just been one of the more senior members of a STOC committee, I find that a little insulting.

Regardless, it's the procedure so we follow it, I suppose. Even if “follow it” means “cut off the first two pages and submit it again”. If doing it that way leads people to put more care into the first two pages of their submissions, I suppose that would be a good thing.

ETA: Suresh, Sariel, and Jeff

Looks like there's potential for internet disruption on April 1. It's probably not going to amount to much, but since the FOCS deadline is April 2, you may want to have a version of the paper into the system ahead of time just in case. Actually, ignore the malware; you shouldn't need a reason like that to aim ahead of the deadline, it's just a good idea regardless.

On a not-very-closely-related subject, this weekend I was thinking about intersection graphs of k-dimensional faces of hypercubes. In an n-dimensional hypercube there are (n choose k)2^n-k k-faces; they can be represented as strings of n characters k of which are stars and the rest of which are 0's and 1's. The faces of a hypercube (interpreted as sets of vertices) have the Helly property — if a collection of strings of 0's, 1's, and *'s match each other pairwise, there is a string of 0's and 1's that they all match — so the cliques just consist of sets of k-faces sharing a common hypercube vertex; therefore, the clique number of these graphs is (n choose k). An independent set in the graph is just a set of disjoint k-faces; by double counting the vertices per face and faces per vertex it's easy to see that the independence number is 2^n-k. The chromatic number is (n choose k): it is at least the clique number, and partitioning faces into groups of parallel faces produces a coloring with this many colors. When one sees chromatic number equal to clique number, one should think perfect graphs, and these graphs are perfect when k=1 (the line graphs of hypercubes, like other line graphs of bipartite graphs, are perfect) but not in general.

( A drawing of one of these graphs, and a connection to probabilistically checkable proof theory )

No doubt everyone else is also posting this, but, thanks to Sariel, here is the list of accepted papers to the 25th ACM Symposium on Computational Geometry, to be held next June in Denmark.

I was quite pleased to see one of my papers, the one with Mumford, Speckmann, and Verbeek on area-universal cartograms, on the list, and it looks like there are many other interesting titles as well.

The list of acceptances to STOC is out. See Michael's post, or go directly to the version with the abstracts.

The list of acceptances to EuroCG is out.

EuroCG isn't really a peer-reviewed conference, as I've been told (never having attended one myself): much like the U.S. fall workshop series in computational geometry, they accept almost anything that's on-topic, and don't have a published proceedings, although there is an online collection of short abstracts. So if you want to find out about something on the list you should go to Brussels in March for the conference or wait for a real version to appear elsewhere.

The call for papers for Graph Drawing 2009 is now up. The important details are that the submission deadline is May 31, the conference is September 22–25, and the location is Chicago.

As the call for papers describes, we're interested not only in papers about software and algorithms for visualizing “web maps, software engineering diagrams, database schemas, chemical structures and molecules” (arguably the main topic of the conference) but also about closely related topics including algorithms for geometric computing involving graphs, the mathematics of graph embeddings, user interfaces and usability studies for graph drawing systems, and applications of graph drawing in other areas.

So, if you haven't done so already, start thinking about what you'd like to submit!

I've now put my photos from Volker Strassen's Knuth Prize lecture at SODA online. I've also uploaded two of them to Wikimedia and used them to illustrate the Wikipedia articles for Strassen and the Knuth Prize; if anyone has a need for a freely-licensed version of any of the other photos, I'd be happy to upload them there as well.

I already have something of a tradition of recording limericks that people have included in their technical talks, so, for the record, Strassen's was:

An E.T. residing on Vega
determined the size of ω.
  In Praha, at night,
  he told me that quite
positively ω was nega....

In the following slide, he encoded a conjecture that ω (the exponent in the time bound for matrix multiplication) is strictly greater than two into another poem. Fortunately, the quality of the poetry provided a lower bound, rather than an upper bound, on the quality of the rest of his talk.

The slides from Elena Mumford's talk at SODA on our paper, “Self-overlapping curves revisited” (arXiv:0806.1724) are now online, including a few she skipped in the presentation.

Several people asked us the same two questions afterwards. First: how did you make such beautiful drawings? I can phrase it like that without fear of immodesty because Elena made the drawings, by hand with colored pencils, and then scanned them. Her colleagues at Eindhoven told me she also had some nice large 3d models made out of semitransparent plastic that would have made an interesting addition to the talk, but unfortunately she didn't bring them.

The second question we were asked is what applications we had in mind. The short answer is that this is a theory paper that isn't trying to be applied, but after the talk Yusu Wang discussed with Elena an application involving finding similarities between pairs of curves (one of Yusu's two SODA papers involved using Fréchet distance for this sort of comparison). Unfortunately I'm not sure of the details of the application. More generally, beyond the specific results in the paper itself, we think that one of its important contributions is the definition of a generalized terrain as a surface such that every point has a neighborhood within which the surface is a terrain. There should be many more problems in which these surfaces can be applied, and we tried to convey that in the talk slides by the images of real-world spiral ramps forming surfaces of this type that we found on Flickr. Sadly, we didn't end up using another photo we found, of the generalized terrain formed by a giant helicoid potato chip (or as Elena would call it a crisp), perhaps because it didn't have the proper salt-and-vinegar flavoring.

• Bernard Chazelle's talk “Natural Algorithms” (describing a convergence time for a simple model of bird flocking that is both upper and lower bounded by a logarithmically tall tower of powers of two, if I remember correctly) was quite entertaining and played to a standing-room-only crowd, and I heard that some latecomers weren't able to get in at all. The system we've had at some SODAs of having meeting rooms of varying sizes and guessing which talks would be better attended had some drawbacks, but the present Harrison Bergeron system of making everybody equal does too.

• I'm sorry to have missed the first data structures talk, on pairing heaps, due to said Chazelle talk. But the rest of the data structures session (including the one with Chazelle's name in the title, in a different session from Chazelle's own talk) was good. The triple threat of John Iacono, Erik Demaine, and Mihai Pătraşcu presenting their equivalence between a geometric problem (augmenting a point set so there is no rectangle with only two opposite corners present) and dynamic optimality for online binary search tree data structures was again particularly entertaining and standing-room-only.

• Gary Miller roped me into taking photos for Volker Strassen's Knuth Prize lecture, in which he described some of his major past results. (Someone who understands it better than I should add his law of the iterated logarithm to his Wikipedia article, which is in other respects as well quite bare-bones.) So photos will be appearing here shortly, and I'll likely add them to the Wikipedia articles as well. But they won't be appearing until I get access to a compact-flash card reader (as I left mine at home) and in any case will probably have to wait until after the conference when I have time to sort through them and postprocess them. I ended up using both my own Canon 40D and 50mm prime lens (I didn't bother to bring a zoom this time) and Erik Demaine's brand-new 5D mk II and 24-105 zoom; the 5D is a sweet camera. Thanks, Erik!

• Jeff has posted the annual drinking game rules. Sadly I did not partake so I have no details to report.

Rather than spending much time blogging about SODA today, I spent the time instead updating the Wikipedia article on Davenport–Schinzel sequences with Gabriel Nivasch's new and very nice results tightening the bounds for the order-3 and even-order cases of these sequences.

Gabriel deservedly won the best student paper award at SODA for these results, a preprint of which can be found at arXiv:0807.0484.

Given how efficiently I was corrected about the mistake I made in yesterday's post (I had given a too-large time bound for the planar Steiner tree PTAS, now fixed I hope), I hope any necessary corrections to these edits will be equally efficient.

I'm now in New York for ALENEX (today) and SODA (the following three days). The most interesting juxtaposition at ALENEX, for me, was the pair of back-to-back talks by Martin Nöllenburg and Siamak Tazari.

( Tanglegram drawings and planar graph Steiner trees )

Just like last year, the SODA hotel (in downtown NYC) claimed when I called on their 800 number to be sold out of the SIAM reserved block and wanted to charge $300/night for the privilege of staying there anyway. But just like last year, the non-800 number for reservations still had conference-rate rooms (at least, except for the last day of the conference when most people are leaving anyway). So if you're going to SODA, and were planning on staying at that hotel, you might want to try calling more than once.

The conference rate is still pretty expensive, of course. If you want a cheaper alternative, Google maps worked well for finding a place for me the last time this happened...

So last week I attended the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008), which was held here in Irvine. It's a little problematic attending a conference in one's own town — too easy to schedule other conflicting activities — but I still went to much of it, as well as getting some research done with attendee and renaissance man extraordinaire Matt Dickerson (about which more some other time).

( Read more... )