You've probably seen images of the Hopf fibration, a nice decomposition of 3-dimensional space (or more accurately the 3-sphere) into nested tori, and of the tori into circles, so that every point of the space belongs to one of the circles (including the z axis, which can be interpreted as a circle through the single point at infinity) and every two circles are linked.

Here's a very similar construction: a decomposition of 3-dimensional space (or more accurately projective 3-space) into nested hyperboloids, and each hyperboloid into lines, so that every point of the space belongs to one of the lines (including the line at horizontal infinity) and every two lines are skew.



( Read more... )

It's still a week or two until we can expect to see the SoCG acceptances, but in the meantime there's another set of computational geometry titles out: the EuroCG accepted papers. Like the fall workshops in the U.S., EuroCG doesn't have a full proceedings, freeing the participants to announce their best recent work there without preempting the possibility of publishing it elsewhere. This year it's in Dortmund, Germany, from March 22 to 24, and registration is open at the workshop's web site.

My vote for most intriguing title: "How Alexander the Great Brought the Greeks Together while Inflicting Minimal Damage to the Barbarians", by Mark de Berg, Dirk Gerrits, Amirali Khosravi, Ignaz Rutter, Constantinos Tsirogiannis and Alexander Wolff.

The crystallographers must have a name for this pattern but I don't know what it is — maybe someone can fill me in? Start with the 16 points

    (0,0,0), (2,1,0), (1,2,0), (3,3,0),
    (0,1,1), (2,0,1), (1,3,1), (3,2,1),
    (1,1,2), (3,0,2), (0,3,2), (2,2,2),
    (1,0,3), (3,1,3), (0,2,3), (2,3,3)

and then repeat in a cubical grid pattern by adding arbitrary multiples of four to each coordinate. Connect every two points at distance √2 in the resulting infinite point set.

In the resulting pattern, every point has exactly three neighbors and the angles between its three incident edges are exactly 120 degrees. There are also many square helices parallel to each of the three coordinate directions, e.g. (0,0,0), (0,1,1), (1,1,2), (1,0,3), (0,0,4), (0,1,5), ... or (2,1,0), (1,2,0), (1,3,1), (2,4,1), (2,5,0), (1,6,0), ... Here's an image looking directly down one of these helices.



When viewed as an infinite graph, this actually has two connected components, interleaved with each other. Each has chiral symmetry (the square helices in one of the components wind clockwise, the other counterclockwise) and they fit together to form a more symmetric structure with twice the density of each component.

Unfortunately I don't think carbon crystals will take a form like this because the edge planes of two adjacent vertices in this structure are twisted with respect to each other rather than coplanar which seems not to be energetically favorable. But maybe some other crystal unit allows that kind of twisting and still likes having 120 degree angles?

The drawback to being scheduled for the third day of SODA is that everyone is tired and much of the audience has departed, either physically or mentally. Despite that, there were still several talks that were good enough to catch and keep my attention.

( Shellsort )

( Candès' invited talk )

( Forbidden matrices )

( Shortest lattice vectors )

Some other SODA links: my own previous posts from this year's ALENEX and SODA are here, here, and here. Noam Nisan and Suresh Venkatasubramanian also have conference reports. Cora posted on talk formats and future location. And there was a lot of activity on twitter, especially concerning the business meeting and the decision to host SODA 2012 in Kyoto; most of it was under the #soda10 hashtag but I'm probably failing to link to additional tweets that weren't.

Second day of SODA. My attendance at talks is getting more sporadic as are my notes from the ones I did attend.

Unsurprisingly, the conference program features many sets of talks that interest me but that I can't attend without a time machine due to parallel scheduling, but also plenty of blocks of time where the topics of all the parallel talks are too divergent from my own interests to draw my attention to any of them. There must be some interesting optimization problems to be solved in collecting data from prospective attendees about what talks they're likely to want to attend, grouping the talks into tuples to be offered in parallel in order to minimize conflicts, and then grouping the parallel tuples of talks into parallel sessions in order to minimize the number of times everyone has to change sessions. Of course these problems are all likely to be NP-hard but maybe some approximation is possible.

( Minimizing sums of algebraic functions )

( Crossing numbers )

( Planar network simplex )

( Downward translation of the exponential time hypothesis )

( My talk slides )

It's still only the second day of conferencing for me (after yesterday at ALENEX) and I'm not yet exhausted, so I went to talks somewhat more frequently than the 1/3 of the time I suggested yesterday. But I would have been to maybe twice as many talks as I actually did go to if only they weren't all scheduled simultaneously. As Suresh tweeted, many of the talks have been quite good, although there have also been exceptions. I asked Cora Borradaile for her suggestions on how to be one of the good ones; her advice was to prepare what you think is a normal 20-minute talk, but then to keep only the first 10 minutes of material: usually even the bad talks start out ok, but then they get too technical and lose the audience.

( Counting stars )

( Random partitions of bounded degree graphs )

( Time-space tradeoffs for TSP )

( Quote of the day )

And, as with yesterday's post, to end with something not-quite-on-topic for the conference: texting while your professor is lecturing vs twittering while some researcher is giving his or her SODA talk: is one more inappropriate than the other?

If I don't write out my impressions from ALENEX today, it's just going to pile up, so...

( Reverse search for multicore enumeration )

( Double decategorification of Newton )

( The future of ALENEX )

( SoCG author responses )

Just in time for my departure for ALENEX and SODA, a post about algorithm implementation!

This year in my graduate data structures class I've moved my coverage of van Emde Boas trees earlier, to part of a group of lectures on priority queues rather than later when I cover the successor problem (binary search trees). vEB trees are a little simpler when they only have to be used for prioritization, but I also think they're more likely to be useful in that application, simply because priority queues and dictionaries are more important than successors.

Anyway, in order to test my own understanding of the subject, I wrote a Python implementation which I'm including in my PADS Python algorithms library.

In Python, built-in types such as sets and dictionaries can be much faster than user-defined types because they run in native code rather than interpreted (insert rant about Snow Leopard breaking psyco here), so it turns out that for 32-bit keys my implementation needs ~256 items in the heap before it beats a naive priority queue that maintains everything in a set object and uses a linear time min(set) every time it wants to find the minimum key. My vEB tree implementation switches to a bitvector based set data structure at its lower levels, for keys that are very small integers; my testing found that using 256-bit bitvectors for 8-bit keys is a slight win over using 16-bit bitvectors for 4-bit keys.

While I was adding stuff to PADS I also fixed a deficiency in SortedSet that Mark Lawrence pointed out: the Python set object can be initialized with any iterable collection of objects, but SortedSet couldn't. Now it can. This is an incompatible change to the API as it means that the comparison function (if any, and if not passed as a named parameter) has to come after the iterable, but it didn't break any of my other code that uses this module and I'd be somewhat surprised if it broke anyone else's.

The other day on the arXiv I saw an interesting paper on unit distance graphs by Gerbracht (to appear at STACS) that led me to some other recent discoveries on the subject.

( Read more... )

After I noticed that Wikipedia's page on "ECCC" mentioned three other ECCC's but didn't mention the ECCC we all know, I decided it was time to add an article on the one true ECCC, the Electronic Colloquium on Computational Complexity. But since I don't actually use the ECCC (well, technically, I have one paper there but I didn't put it there) I'd appreciate feedback from those who do on whether what I wrote about it is accurate.

Of course, the added difficulty is that what we say about it in Wikipedia needs to be not only accurate, but backed up by published sources. So, for instance, it's not possible to disparage the email interface as "clunky" or to say that the two-month timeout has caused many decent papers to be rejected unless one can find a better source than Lance's blog post from last July.

One thing I wondered about when writing this but didn't see in any of the sources I found: who funds ECCC? Is it run on some researcher's office machine for little or no cost, or does it cost a nontrivial amount of actual money? Does Trier pick up the cost in exchange for the publicity they get for it, does it come from DFG, or somewhere else?

I had a longer and more technical post that I wanted to make but that will have to wait. In the meantime, I've spent much of today reading Doxiadis and Papadimitriou's Logicomix, a graphic novel biography of Bertrand Russell and his search for the foundations of mathematics. It's very engrossing — I had a hard time pulling myself away from it to write this post. Highly recommended.

While looking up something else, I found a paper by Ling-li Sun (2007): “Spanning trees with leaves bounded by independence number”, Applied Mathematics E-Notes 7: 50–52.

Sun proves that any undirected graph G has a spanning tree with at most α(G) leaves (where α(G) is the size of the largest independent set of G) and that such a tree can be found in O(n²) time. Sun's proof is very short, and improves on an earlier paper by Rahman and Kaykobad with a weaker result (a bound on the degree of the tree rather than its number of leaves). Here's an even shorter proof (for a somewhat weaker version of the problem; see comments) and a faster algorithm: use a depth-first search tree. Its leaves form an independent set, therefore, its number of leaves is at most the size of the maximum independent set.

One could also phrase Sun's result as a paired approximation in the style of my upcoming SODA paper. In any graph one can find either an approximate independent set or an approximate minimum-leaf spanning tree with an approximation ratio O(√n): if the DFS tree has fewer than √n leaves, it's a good approximation to the minimum leaf spanning tree, and if it has more leaves then its leaves form a good approximation to the maximum independent set. However, the known inapproximability results for the minimum leaf spanning tree are relatively weak (see Salamon and Wiener, IPL 2007) so it's possible that there exists a better direct approximation for that problem by itself.

How could any photographer resist the falling-down barn below? I certainly couldn't. So I took a bunch of photos of it today; here's the gallery.

We don't have snow or reindeer or (native) pine trees in Orange County, but instead, every year for the past 100 years or so, the boats of Newport Beach have paraded around the harbor at Christmastime decorated in lights. Many of the big expensive houses on shore are also decorated, and throw private parties to rival the public party going on a few feet away on the boardwalks.

My photos from this year's event are now online; they also include a bunch of shots of the kids (and one or two of me!) that I took for our annual Christmas card, with a gorgeous sunset over Catalina as backdrop.

Merry (belated) Christmas, all, and a happy New Year!

Unintentially humorous email subject line of the day: "Impact Your Success With Effective Communication". I don't see why I should trust someone who uses impact as a verb in that context to tell me anything about communication. Physician Dean of Continuing Education, heal thyself.

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.

Make your own paper orthogonal permutohedron! Here's how. Print out the pattern, cut the solid lines, valley fold the dashed lines, and mountain fold the dash-dot lines. (I used a box-cutter both to make the cuts and to prescore the folds.) Here's what it looks like when you're done:



See also this fractal staircase, another orthogonal polyhedron constructed in a similar way.

Three quick puzzles concerning the polycube depicted below: (1) Cut it into two pieces that can be reassembled into a cube. (2) Fill space with translated, rotated, and reflected copies of it. (3) Fill space with translated and rotated (but not reflected) copies of it.



This polyhedron is an axis-parallel permutohedron: its 24 vertices can be labeled with the 24 permutations on four objects, in such a way that each edge connects two permutations that are related by a swap of two adjacent values. My new paper with Elena Mumford, Steinitz Theorems for Orthogonal Polyhedra (arXiv:0912.0537), aims to provide a complete classification of orthogonal polyhedra such as this one in the same way that Steinitz's theorem provides a complete classification of convex polyhedra.

( Read more... )

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.

When I'm in the heat of coming up with new ideas on a research project I have a bad habit of sending an email to my collaborators and then, a minute or an hour or a day later, another and another, correcting or contradicting or elaborating on the previous ones, until it can be difficult to figure out which parts of what I sent were important or bogus or relevant. Wouldn't it be better to have a system that's sort of like email, in that it allows one to send messages that only one's trusted collaborators sees, but sort of like a wiki, in that everything can be edited after the fact by anyone else (with the old versions still viewable)? And while we're at it, why not make this system sort of like a threaded web forum where one can share a whole long thread with additional people long after it starts, and sort of like an outliner that lets you build a hierarchical structure for your ideas, and maybe also sort of like a chat system where one can see what everyone else in the same thread is typing as they type it? And even sort of like LaTeX^* in that it knows how to format equations and not just the usual text and pictures?

That's what Google Wave is.

I've been using Wave for all of a week now for one of my papers and I already regret the times I lapsed back into my old bad habits to work on it by email. I'm not giving up on email any time soon but for some situations there are other tools that are better, and I think this is one of those situations. Wave is in beta (justifiably so: the server is...robust) and still invitation-only. But apparently a week is long enough for me to be an old hand^** and start inviting a few other people to join me, so if you want an invite and somehow haven't managed to score one already elsewhere then feel free to ask here.

^*Ok, the LaTeX part isn't there by default. It's an extra gadget that you have to add on, but it's easy to do so. I haven't used it much, though: most of the time when I need math it's just for simple formulas like O(n²) that are easy enough to type inline.

^**If I'm an old hand, then Suresh and Lance are ancient and decrepit and over-the-hill.

Update: all eight of my initial set of invitations are used now but bhael has more; see the comments.

Update update: I have invites again.