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.
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.
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.
( Read more... )
All in all, a good conference.
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.
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,
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.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.
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
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)2n-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 2n-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 )
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.
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.
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.
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.
• 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.
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.
( Tanglegram drawings and planar graph Steiner trees )
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...
( Read more... )
