0xDE
15 February 2015 @ 05:32 pm
I don't know what Google+ is doing under the hood (and don't really want to know) but whatever it is seems kind of bloated to me, enough to kill my browser and the responsiveness on my whole machine when I try to open 14 G+ tabs at once. But anyway, here they are:
 
 
0xDE
05 February 2015 @ 10:35 pm
Formatting a couple hundred references for a proposal led me to wonder: If you find yourself wanting to look up the BibTeX data for a paper, where do you go? And how much do you have to edit it yourself afterwards?

The three most obvious choices for me are DBLP, ACM Digital Library, or MathSciNet.

Read more...Collapse )
 
 
 
0xDE
22 January 2015 @ 03:29 pm
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 which the elements of the vector space are not tuples of real coordinates. So instead of discussing the details of that algorithm I ended up spending much of the lecture reviewing the theory of binary vector spaces. These are very important in algebraic graph theory, so I thought it might be helpful to write a very gentle introduction to this material here.

Read more...Collapse )
 
 
 
0xDE
06 January 2015 @ 11:56 pm
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.

Read more...Collapse )
 
 
0xDE
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 contact points between arcs (the points where one arc ends as it runs into another arc) correspond to the 24 edges of the cuboctahedron. What we want to know is which other graphs can be represented like the cuboctahedron in this way? They have to be planar, and every subgraph has to have at most twice as many edges as vertices (because every set of arcs has twice as many endpoints as arcs) and beyond that it's a little mysterious. But we have some natural subclasses of the planar graphs for which we can prove that such a representation always exists (for instance the 4-regular planar graphs) and some NP-hardness results.

Two other uploads of possible interest: my report as co-PC-chair at the ALENEX business meeting, and my talk on Miura folding (both with small corrections to the slides I actually used). I've posted here before about the Miura folding results. For the ALENEX report, besides the usual breakdown of acceptance rates and subtopics, there were two more substantial issues for future planning: should ALENEX move its submission deadline earlier than the SODA notification date (so that the PC has adequate time to review the submissions), and should it accept more papers? The sentiment at the meeting seemed to be in favor of both ideas.
 
 
0xDE
03 January 2015 @ 04:53 pm
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!

 
 
0xDE
01 January 2015 @ 09:44 pm
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.

Read more...Collapse )
 
 
0xDE
31 December 2014 @ 03:18 pm
After I returned to Google+ in mid-year (once Google rescinded their real-name policy) I've been sharing approximately a link a day there, and collecting the links for twice-monthly roundups here (in part to allow me to find my posts again since G+ provides very little organization for old posts). This is the latest batch:
 
 
0xDE
30 December 2014 @ 09:43 pm
My parents' house in Mendocino is full of books and sculptures of creatures (mostly cats). Here are some of them:



The rest of the gallery.
 
 
0xDE
29 December 2014 @ 09:37 pm
In the unlikely event that anyone wondered why I didn't post anything either here or over on my Google+ account for the last few days, it's because I unexpectedly found myself incommunicado, visiting relatives for Christmas. Here are two of them, my cousin's daughters.



It's normal for there to be no cell phone service at my parents' house in Mendocino. Cell phones finally reached downtown Mendocino a couple of years ago over the objections of some protesters who were terrified of being exposed to any form of electromagnetic radiation, but there's a hill between downtown and the house that blocks the signal. There would normally be landline phone service there, but the lines got flooded in the big storm a couple of weeks ago and AT&T hasn't succeeded in drying them out yet. And my parents also have cable internet, but for some other reason that went down too. So we had to resort to old-fashioned behavior like reading books or actually interacting with each other instead of all being absorbed in our own separate electronic devices the way we otherwise would likely have been.
 
 
0xDE
17 December 2014 @ 12:17 am
In my recent posting on four-dimensional polytopes containing linked or knotted cycles of edges, I showed pictures of linked cycles in three examples, the (3,3)-duopyramid, hypercube, and (in the comments) truncated 5-cell. All three of these have some much more special properties: the two linked cycles are induced cycles (there are no edges between two non-consecutive vertices in the same cycle), they include all the vertices in the graph, and their intersection with any two- or three-dimensional face of the polytope forms a connected path.

When this happens, we can use it to construct a nice two-dimensional grid representation of the polytope. Read more...Collapse )
Tags:
 
 
0xDE
16 December 2014 @ 08:46 pm
When I was asked earlier this year to write a short survey on k-best enumeration algorithms for the Springer Encyclopedia of Algorithms, I wrote a first draft before checking the formatting requirements. It ended up being approximately five pages of text and seven more pages of references, and I knew I would have to cut some of that. But then I did check the format, and saw that it needed to be much shorter, approximately two pages of text and a dozen references. I don't regret doing it this way; I think having a longer version to cut down helped me to organize the results and figure out which parts were important. But then I thought: why not make the long(er) version available too? I added a few more references, so now it's about six pages of text and ten of references, still closer to an annotated bibliography than an in-depth survey. Here it is: arXiv:1412.5075.
 
 
 
0xDE

The surface of a three-dimensional polyhedron is a two-dimensional space that's topologically equivalent to the sphere. By the Jordan curve theorem, every cycle of edges and vertices in this space cuts the surface into two topological disks. But the surface of a four-dimensional polytope is a three-dimensional space that's topologically equivalent to the hypersphere, or to three-dimensional Euclidean space completed by adding one point at infinity. So, just as in conventional Euclidean space, polygonal chains (such as the cycles of edges and vertices of the polytope) can be nontrivially knotted or linked. If so, this can also be seen in three-dimensions, as a knot or link in the Schlegel diagram of the polytope (a subdivision of a convex polyhedron into smaller convex polyhedra). Does this happen for actual 4-polytopes? Yes! Actually, it's pretty ubiquitous among them.

Read more...Collapse )
 
 
0xDE
04 December 2014 @ 11:27 pm
The exponential random graph model is a system for describing probability distributions on graphs, used to model social networks. Read more...Collapse )
 
 
0xDE
30 November 2014 @ 06:20 pm
 
 
0xDE
26 November 2014 @ 11:25 pm
In my algorithms class today, I covered minimum spanning trees, one property of which is that they (or rather maximum spanning trees) can be used to find the bottleneck in communications bandwidth between any two vertices in a network. Read more...Collapse )
 
 
0xDE
25 November 2014 @ 12:12 am
If, like me, you're working on a SoCG submission, and this is the first time you've tried using the LIPIcs format that SoCG is now using, you may run into some minor formatting issues (no worse than the issues with the LNCS or ACM formats, but new and different). Here are the ones I've encountered, with workarounds where I have them:Read more...Collapse )
Tags: