0xDE
This one isn't my problem – it came from MathOverflow – but it's frustrating me that I haven't been able to solve it, so I hope by reposting it here I can get some more attention to it and maybe even a solution.

The question is: let Fk be the family of graphs having no minor in the form of a cycle with doubled edges, of length k. Do the graphs in this family have a polynomial number of cycles (with the exponent of the polynomial depending on k, ideally linear in k)?

Read more...Collapse )

ETA 2014-04-10: Solved, negatively, by a planar bipartite permutation graph.
 
 
0xDE
28 March 2014 @ 11:07 pm
I'm back now, but this beach house in Barbados was my home for the last week, as I attended the 29th Bellairs Winter Workshop on Computational Geometry (my first time there).



Read more...Collapse )
 
 
0xDE
19 March 2014 @ 10:10 pm

The cages are a class of graphs that I think deserve to be more widely known, because they have a lot of interesting properties that make them useful as counterexamples in graph algorithms and graph theory. They're hard to construct and we don't have a lot of explicit descriptions of them, but that's not so important when you're using one as a counterexample.

Read more...Collapse )
 
 
0xDE
08 March 2014 @ 07:46 pm

Today I've been playing with the induced subgraphs of the Clebsch graph. Several other interesting and well-known graphs can be obtained from it by deleting a small number of vertices and forming the induced subgraph of the remaining vertices.

Read more...Collapse )
 
 
0xDE
01 March 2014 @ 05:51 pm
Many of the talks at the Conference on Meaningfulness and Learning Spaces that I recently attended concerned (surprise!) meaningfulness. The basic idea is to provide a crude filter for bad science and bad statistics by determining whether applying a formula to data could possibly make any sense. For instance, in many computer science conference program committees, we score papers on a scale from -3 to +3 (say) and then rank the papers by averaging the scores of different reviewers (possibly weighted to counter reviewer bias). Is this aggregation operation a meaningful thing to perform on this kind of data? Is it meaningful to say "it's twice as hot today as it was yesterday"? When we use an algorithm to solve a problem, how can we tell whether the result is meaningful?

Read more...Collapse )
Tags:
 
 
0xDE
28 February 2014 @ 01:11 pm
This week I've been attending the Conference on Meaningfulness and Learning Spaces at UC Irvine, in honor of the 80th birthday of my co-author Jean-Claude Falmagne. I believe videos of the talks will eventually be online and I'll put up a link to mine when that happens.

Jean-Claude himself gave a talk, in which the following cute geometric fact came up as an example: If f(x, y) is the function that computes the length of the hypotenuse of a right triangle with side lengths x and y, then f obeys the associative law. It's not difficult to see this from the algebraic form of the function, but Jean-Claude instead presented a geometric demonstration of this fact, based on the properties of an orthoscheme, a tetrahedron with four right triangles as its sides.

Read more...Collapse )
 
 
 
0xDE
23 February 2014 @ 07:25 pm

One of Oded Schramm's less-well-known but better-named results is his "monster packing theorem", a far-reaching generalization of the famous circle packing theorem of Koebe, Andreev, and Thurston.

Read more...Collapse )
 
 
0xDE
17 February 2014 @ 07:24 pm
While in Tucson, I took a tour of the University of Arizona's Steward Observatory Mirror Laboratory, where they built the mirrors for the big astronomical observatories such as the Giant Magellan Telescope. Two GMT mirrors were in progress and one had been shipped, but the one they were grinding when I visited was for a different instrument, the Large Synoptic Survey Telescope.



Its bizarre shape, with two paraboloids meeting in a central ridge, comes from the fact that it's really two mirrors in one: an annular 8.4m primary surrounding a 5.0m tertiary. The hexagons visible in the glass are a honeycomb pattern of molded holes on its back side, used to keep the mirror lightweight while maintaining rigidity. The honeycomb seems to be aligned with the edge of the mirror all around its circumference, with breaks in the pattern in the interior; it looks like maybe they're using some sort of centroidal Voronoi tessellation?

(A few more photos)
 
 
0xDE
16 February 2014 @ 06:37 pm
Here's a belated valentine-themed cappucino from Caffe Luce in Tucson, where I spent the last week visiting Stephen Kobourov, Alon Efrat, and their students and postdocs. (Also recommended: El Charro for dinner and Prep & Pastry for breakfast. Try the poutine!)

 
 
0xDE
07 February 2014 @ 10:31 pm
Yesterday I went to LACMA, mostly to see the James Turrell exhibit there. If I had been allowed, I would have taken many photos, but probably very few of them would have come out well, because Turrell's work is about light as a physical presence and about the human perception of color, and I don't think either of those things translates very well from camera to screen to eye.

As a case in point, one of his pieces was a large room, shaped roughly like a flattened cylinder, with a square portal entrance at one end (up a flight of steps from its anteroom). From below, waiting our turn to go in, the room seemed to be drenched in saturated color, changing from blue to pink to red, so thick that you expected the people inside to swim in it like honey rather than just walking in air and light. But from the inside, the room seemed mostly white or a bit off-white, with the end opposite the portal open to what seemed a bluish formless and infinite void. The values of light and dark within the room and the space beyond the room changed, but not so much its colors, except that if you paid attention the skin tones of the other participants were a bit off and one young woman's pale pink hoodie glowed with an unearthly radioactive fluorescence. How do you capture that experience in pixels?

I did take some shots of other exhibits, though. The one below is from Agnès Varda in Californialand, a show in which French New Wave filmmaker Agnès Varda built a shack from reels of one of her less successful films, Lions Love.



The rest of the photos include more of Varda's piece, and a couple of pieces from another exhibit in the same part of the museum on art inspired by the coming soccer World Cup.
 
 
0xDE
21 January 2014 @ 06:07 pm

A comparison sorting algorithm is called adaptive if its performance can be better than the worst-case O(n log n) time for comparison sorting algorithms, on subsets of inputs that are somehow close to being already sorted. Two examples of this are a Cartesian tree based sorting algorithm described by Levcopoulos and Petersson in WADS 1989, and splaysort, a splay tree based sorting algorithm described by Moffat, Eddy, and Petersson in Software: Practice and Experience 1996. How do these two algorithms compare with each other?

Read more...Collapse )
 
 
0xDE
19 January 2014 @ 02:34 pm
Miscellaneous links, not big enough for their own postings:

OMG is in the OED. But lest you think this is a triumph of netspeak over proper English, the earliest citation for it is dated 1917.

John McPhee on finding structure in the subjects he writes about. Probably helpful for all kinds of technical writing, not just the more popular nonfiction McPhee is known for.

Harry Lewis on the conflicts of interest inherent in the collaborations between academic institutions and repressive anti-free-speech regimes such as the ones in the Middle East, Singapore, or Kansas.

A requiem for the American dream, by Hunter on the Daily Kos.

Complementing my recent posts on SODA 2014, here are some reactions by others: Abstract talk. Notes by Mahnush Movahedi. And Cora on the message we're sending by having an all-male keynote slate.
 
 
0xDE
I guess it's been long enough since the Wave collapse, the Reader closure, and the Google news archive elimination, so it's time once again for Google to pick something else that is useful but only to an insufficiently massive subset of its users, and kill it. The latest dead Google baby is Google Notifier, which I've been using to get desktop notifications of new incoming emails. Google's suggested replacement is to enable desktop notifications directly in gmail, but that only works when I have a browser window or tab open to gmail, and I don't like cluttering up my browser with windows or tabs that I'm not actually using.

Oh well, the likely result is only that I'll be slow answering emails, something that is often true anyway. At least they haven't tried to break Google scholar yet.
Tags:
 
 
0xDE
I don't think of myself as a coffee snob, in that I won't think any less of you if you don't appreciate well-made coffee. But I am somewhat particular about what I drink myself, to the point that I have a real (Gaggia Classic) espresso machine at home instead of one of the pod or steam things. So with a conference located in a city that rivals Seattle for its coffee fanaticism, I felt that I had to at least try some of the local coffee shops.

Read more...Collapse )
Tags:
 
 
0xDE
07 January 2014 @ 09:44 pm
Today was the day I made my pilgrimages to Stumptown Coffee and Powell's Books, so I didn't see as many of the SODA talks as the previous two days. Nevertheless:

Read more...Collapse )
 
 
 
0xDE
05 January 2014 @ 10:57 pm
I'm in Portland, Oregon for SODA, ALENEX, and ANALCO (don't pronounce it the way it looks). There are four parallel sessions – three for SODA, one today for ALENEX, and one tomorrow for ANALCO – so plenty of good talks to choose among, and plenty that for one reason or another I had to miss. Here are some of the highlights of my first day:

Read more...Collapse )
 
 
0xDE
03 January 2014 @ 07:52 pm
Here's one last photo posting before I go back to more technical material. This new year, my in-laws decided that they wanted to see the Rose Parade, and brought us along with them. So here are my photos of the parade. It's a bit of an extravaganza of corporate advertisement and conventional sentimentality, but fun anyway. It's impossible to pick a representative sample from so many images, so here's just one, of one of the less conventional elements of the parade.



My friend Tyler was outraged at the way the Stanford Band strolled through instead of marching in lockstep. He felt it was an insult to all the other bands that had practiced hard to be in the parade, and a serious enough insult that they should be banned from the parade (in fact they have been banned in the past). I could quibble about his reasoning: several of the bands are in it by virtue of geography or a good football team rather than effort, the Stanford Band clearly puts in plenty of practice in their musicianship and scatter-formation, and in any case why interpret their performance by how it reflects on someone else rather than taking it for itself? But my own reaction is instead one of pride in my alma mater's continuing support of nonconformity and boundary-pushing.

(The Hawaii all-state band also did their fair share of boundary pushing by making their whole show into a tribute to the rainbow flag and by making their underdressed eye-candy male instead of female. Props to them for it.)
 
 
0xDE
02 January 2014 @ 09:15 am
This one was taken on Christmas Eve, as the sun finally broke through after a cold foggy walk on the Mendocino headlands. It's out of order because I took it on my cell phone and then forgot to upload it.



Sara also has another cell phone shot from the same time and place. By using Instagram, she usually has hers up within minutes of taking a shot, rather faster than I achieved this time.