January 22, 2015

11:29 PM | The linear algebra of edge sets of graphs
This quarter, in my advanced algorithms class, I've been going through Vazirani's Approximation Algorithms book chapter-by-chapter, and learning lots of interesting material that I didn't already know myself in the process.One of the things I recently learned (in covering chapter 6 on feedback vertex set approximation)* is that, although all the students have taken some form of linear algebra, many of them have never seen a vector space in which the base field is not the real numbers or in […]

January 16, 2015

4:16 AM | Linkage
Real-time 3d special effects in modern dance (G+)How not to react to conference talks that happen to be presented by women (G+, including also an unrelated report from the SODA business meeting)Photos of icy landscapes showing how varied the geometry of ice can be (G+)New ACM fellows (G+)n-body choreagraphies (strange solutions to the n-body problem in which all bodies follow each other along a curve; more and still more; G+)Men (on the Internet) don’t believe sexism is a problem in […]

January 07, 2015

7:56 AM | Report from SODA, ALENEX, and ANALCO
I just returned from San Diego, where ALENEX, ANALCO, and SODA were held this year. I'm only going to write about a fraction of the things that happened at these conferences, in part because (with four different sessions happening in parallel much of the time) it was only possible for one person to see a fraction of those things. Also I already posted bits about the ALENEX/ANALCO business meeting and SODA business meeting so I won't repeat those here.Sunday's scheduled plenary talk by Peter […]

January 05, 2015

6:06 AM | Circular arc contacts, Miura slides, and ALENEX business
While I've been at SODA one of my co-authors has been busy preparing what turns out to be my first preprint of the new year: Contact Representations of Sparse Planar Graphs (arXiv:1501.00318, with Alam, Kaufmann, Kobourov, Pupyrev, Schulz, and Ueckerdt). I think this is one of these cases where a picture can go a lot farther than words in explaining: here's an example of what we're looking at.The 12 circular arcs of this diagram correspond to the 12 vertices of a cuboctahedron, and the 24 […]

January 04, 2015

12:53 AM | Greetings from San Diego
I've just arrived in San Diego for the annual Symposium on Discrete Algorithms and its associated satellite workshops ALENEX and ANALCO. That little strip of blue on the left edge of the photo is the harbor; you can also see a little bit of it directly from the hotel, if your window faces in the right direction. If you're also here, greetings!

January 02, 2015

5:44 AM | 2014 in algorithm preprints
Happy New Year, everyone! It's time once again to give a status report on the cs.DS (data structures and algorithms) section of the arXiv. The arXiv as a whole just hit a big milestone, one million preprints uploaded. cs.DS forms a small fraction of that, but still, last year there were 1182 new preprints, up a little from the previous year.There has been some talk recently about possible changes to the system, including replacing author choices of subarea within cs by the results of an […]
6 Results