Via polylogblog I learn that the list of accepted papers at STACS has become available.

Three graph algorithm titles caught my attention enough to get me to track down their online versions, though I haven't had time to do much more than scan their abstracts:

Finding Induced Subgraphs via Minimal Triangulations (arXiv:0909.5278) by Fomin and Villanger. This turns out to be about finding moderately-exponential algorithms that find subgraphs of bounded treewidth that are as large as possible and to solve subgraph isomorphism problems when the subgraph to be found is large but of bounded treewidth.

Two-phase algorithms for the parametric shortest path problem by Chakraborty, Fischer, Lachish, and Yuster. Parametric optimization problems involve an input graph with weights that vary (linearly or more complicatedly) with some parameter; one must solve an optimization problem like shortest paths for particular parameter values. In the version studied here, one doesn't want all the different shortest paths for all different parameter values (there can be superpolynomially many different paths even when the edge weights vary linearly); rather, we'd like to compute the shortest path for some small set of parameter values, more quickly than the O(mn) per value that it would take to run Bellman-Ford separately for each value. (One can't use Dijkstra because some edges may be negative.) The authors show that, with polynomial preprocessing, shortest paths for each parameter value may be found in O(m + n log n) time, as fast as Dijkstra.

Planar Subgraph Isomorphism Revisited (arXiv:0909.4692) by Dorn. This is a followup to one of my papers, which provides a completely impractical algorithm for finding any k-vertex subgraph (for fixed k) in a larger planar graph in linear time. The algorithm described here has been improved: it's now exponential in k rather than k log k. I'm still not convinced that it's at all close to practical, but it's a step in the right direction.

Old and busted: fake conferences that scam money out of academics using high registration fees, accept everything rather than subjecting submissions to any sort of peer review, but actually exist: you can attend them, meet the other dupes, and get a proceedings.

The new hot trend: fake conferences that don't exist, come with (nonexistent) paid travel expenses to invited speakers and, presumably, scam money out of academics by getting them to send their banking data to the organizers.

Via BoingBoing.

I spent the last week visiting the Institute for Pure and Applied Mathematics at UCLA, for a workshop on combinatorial geometry. Rather than post here about the many exciting new results I heard about (for which see the conference program) I thought I'd describe a few open problems that came up in some of the talks.

( Coloring line segments )

( Blocking visibilities among points )

( Counting spanning trees in bipartite graphs )

( Triple crossings of unit circles )

I just finished uploading five new sets of photos:

• Mathematical sculpture at Trinity College Dublin. Or sort-of mathematical: the artist may have intended one of these sculptures to model DNA, but to a topologist it looks like a torus link. Apparently every year the Hamilton Workshop on Geometry and Topology uses one of these as a logo, but they're running out: soon they'll have to go with the kitschy sculpture of a buxom Molly Malone outside the college gate.


• Dublin. Or the parts of it that I saw outside of Trinity and Guinness. With my usual complement of graffiti.


• The Guinness Storehouse. Supposedly Ireland's biggest tourist attraction. I didn't take many photos inside, although I found the tour quite interesting; most of the photos are of the 360-degree view of the Guinness brewery that one gets from the bar at the top of the tour.


• Chicago. The weather was not really conducive to photography but I took a couple of shots anyway.


• Graph Drawing 2009. If you didn't go, now's your chance to see what you missed. If you did go, you can see how many photos you and your friends are in. I hope none of the ones I kept are too embarrassing or unflattering. ETA: The GD09 web site now also links to another set of photos by Pranava Jha.

After two conferences I'm too tired to successfully post anything serious. So, since Graph Drawing lacks a public business meeting at which to present these, here instead are some statistics on acceptances and rejections at the conference.

( Read more... )

I've been visiting Dublin, Ireland (my first time here) for the Fifth William Rowan Hamilton Geometry and Topology Workshop at the Hamilton Mathematics Institute of Trinity College, where I spoke about hyperconvex metric spaces, finding optimal stars, orthogonal convex hulls, and embedding into the Manhattan plane.

It was a good conference, but a bit like stepping into a parallel world where everyone's evil twin does low-dimensional topology and geometric group theory: the workshop theme had the phrase "Computational Geometry" in it, but it's an Other Computational Geometry that really mostly means low-dimensional topology and geometric group theory; there's an Other David Epstein (spelled wrong) who does etc and was here last year; and there's an Other Kevin Wortman (not spelled wrong) who does etc and wasn't here, but whose name caused some confusion when I referred to the work of my former student Kevin Wortman. Still, my interests and those of the Other Computational Geometers have enough overlap that I think we all got something useful out of the experience.

I'm not going to recount all of the talks (especially because I didn't understand them all) but here are a few that caught my attention.

( Read more... )

The list of SODA acceptances is out. Sadly, again, it doesn't include abstracts, but they're promised to come later. Now with abstracts! I have one paper there; I'll post more about it when I've had a chance to respond to the feedback from the reviews and prepare a preprint version.

It's hard to tell just from the titles, but I have the vague impression that there's rather less computational geometry than I'm used to seeing at past SODAs.

One very important change (perhaps a consequence of going to electronic proceedings?): “your conference paper can be up to twenty (20) pages”!!

ETA: See also 3d pancakes, algorithmic games, kd-PhD, 3d pancakes again, biased coin, polylogblog, geomblog, motocicleta

The list of papers accepted to ISAAC 2009, the 20th International Symposium on Algorithms and Computation is now online. (I'd be happier if abstracts were also included, but they're not.)

I never had any thoughts of going to this one, but my colleague and frequent co-author Mike Goodrich has been excited about the possibility of a trip to Hawaii for months, and now he has a good excuse to go. He and his student Darren Strash have a paper there on succinct greedy embedding of planar graphs into the Euclidean plane (related to our previous work on greedy hyperbolic embedding). The idea is to use a version of the Leighton-Moitra embedding from FOCS 2008 (for 3-connected planar graphs, or more generally graphs containing an appropriate cactus subgraph) and show how to compute O(log n)-bit labels for the vertices in such a way that the embedded location of each vertex is a function (independent of the graph) of its label. In this way they get around the “cheating” aspect of much of the greedy embedding literature, that a single vertex location already encodes enough information by itself to represent an entire routing table.

Another result that I've heard of before, mentioned briefly in Erik Demaine's invited talk at WADS, is his paper (listing his last name as author twice in his usual egocentric style, also with Konjevodz and famed origamist Robert Lang) “Folding a Better Checkerboard”. If I remember correctly, they save a factor of two in the area of the starting sheet of origami paper (with different colors on its two sides) needed to fold a checkerboard of a given size (in which the two colors alternate to form an 8×8 grid of squares).

There are many more titles that look interesting to me but that I don't know a lot more about than the title itself. I'm sure it will be an interesting conference, and if you haven't already done your planning for Hawaii in December, now would be a good time.

Here are the slides from my talks at WADS and those of my co-authors:

• On the approximability of geometric and geographic generalization and the min-max bin covering problem (slides and talk by Mike Goodrich; also with Kevin Du and George Lueker)
• Orientation-constrained rectangular layouts (slides and talk by Elena Mumford with her usual artistic flair)
• The h-index of a graph and its application to dynamic subgraph statistics (with Emma Spiro)
• Optimal embedding into star metrics (with Kevin Wortman)

I just returned from WADS, formerly the Workshop on Algorithms and Data Structures but newly renamed to be the Algorithms and Data Structures Symposium, in Banff, Canada. At the conference dinner, we learned that the organizers originally intended this to be a true workshop, with 30 or so participants, but it was never that small, and the new name recognizes that. Banff National Park is beautiful; I arrived two days early with my wife Diana so that we could do some sight-seeing, and I'll be posting some photos of that part later when I catch up on my postprocessing.

( Read more... )

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.