?

Log in

 
0xDE
I think part of the reason graph isomorphism has been such a tricky problem, theoretically, is that in practice it's too easy. Almost all graphs have some small irregularities that can be used as landmarks for identifying all the features of the graph, even when they've been scrambled arbitrarily. Only a small class of highly symmetric graphs pose any actual difficulties, and that's why a deep knowledge of group theory (the study of symmetries) has been so useful in theoretical work on graph isomorphism. It's also why finding counterexamples to crank graph isomorphism algorithms is hard enough that the cranks don't do it themselves and avoid the embarrassment of someone else doing it for them.

In many cases, even if you add some noise to a graph, its underlying irregularities will show through, allowing you to recognize it and its individual features. That's the main idea behind my most recent arXiv preprint, "Models and Algorithms for Graph Watermarking" (arXiv:1605.09425, with Goodrich, Lam, Mamano, Mitzenmacher, and Torres, to appear at ISC 2016).

The problem we study is one of watermarking copies of a graph (for instance a large social network) so that if you see one of your copies later you can tell which one it was, by using the graph structure rather than extra information such as vertex labels. To do so, we identify a small number of "landmark" high-degree vertices (generally, the ones with the highest degrees), use the pattern of adjacencies to landmarks to give unique identities to a larger set of (medium-degree) vertices, and flip a small set of randomly selected edges among these vertices. With high probability (when the graph to be watermarked is drawn from a suitable random family) even if an adversary tries to mask the watermark by scrambling the vertices or flipping more edges, the vertex identifications and pattern of flipped edges will be recoverable.

Because we're choosing our landmarks in a fairly naive way (by vertex degrees, or as in our implementation with ties broken by neighboring degrees), our algorithms wouldn't work for random regular graphs. But even in such cases, there are other features such as the numbers of triangles they belong to or their distance vectors that often allow some vertices to be distinguished from others. Finding out which features of this type remain robust when noise is added to the graph seems like a promising line of research.
 
 
 
0xDE
30 May 2016 @ 12:09 pm

Ivan Pervushin was a 19th-century Russian amateur mathematician, employed as a cleric, who factored two Fermat numbers and discovered the ninth Mersenne prime 261 − 1 = 2305843009213693951. But despite these obvious reasons for fame, his Wikipedia article was in such bad shape (e.g. completely unsourced) that it was recently put up for a deletion discussion, which it survived.

Read more...Collapse )
 
 
0xDE
SODA PC chair Phil Klein asked me to publicize this quick announcement because of delays in getting this information online in a more official way: for next January's SODA (ACM-SIAM Symposium on Discrete Algorithms) in Barcelona, the submission deadlines will be July 6 (short abstract and paper registration) and July 13 (full submission).

For now, you can visit http://cs.brown.edu/~pnk/#soda17 for the basic information (deadlines, submission site, and program committee).
 
 
0xDE
If you draw a series-parallel multigraph in the plane, with an extra edge (the dashed edge below) connecting its two terminals, then its planar dual is also a drawing of the same type, turned sideways. The terminals of the dual are the vertices linked by the dual of the dashed edge. Each series composition in the primal turns into a parallel composition in the dual, and vice versa. Often one talks only about series-parallel graphs, not multigraphs, but for this duality the "multi" part is not easily avoidable: the primal or dual (or both) will have multiple edges between the same two vertices.



Read more...Collapse )
 
 
0xDE
17 May 2016 @ 04:14 pm

You may have heard of the Poincaré disk model of the hyperbolic plane, in which the whole hyperbolic plane is mapped to the interior of a Euclidean disk, with hyperbolic lines being transformed into circular arcs that make a right angle with the disk boundary. Or of the Beltrami–Klein model, which also maps the hyperbolic plane to the interior of a disk, but with a different map that keeps the lines straight, so that they correspond to the chords of a circle.

One use for these models is in information visualization, to provide a fisheye view of a drawing in the hyperbolic plane that provides "focus+context": focus on some specific feature in the drawing, and context of all the rest of the drawing, compressed into the outer parts of the disk. Another is as an aid to mathematical intuition: hyperbolic lines may be hard to visualize and understand, but chords of a circle are much more familiar, and this model shows that (in terms of the combinatorial patterns they can perform, if not their distances and angles) they are really the same thing.

But did you know that you can get an analogous fisheye view of the Euclidean plane, by another pair of models that map Euclidean lines to natural families of curves in a disk?

Read more...Collapse )
 
 
 
 
0xDE
30 April 2016 @ 07:58 pm
The image below is a study of the geometry of MIT's Kresge Auditorium.



Read more...Collapse )
 
 
0xDE
20 April 2016 @ 08:31 pm
Do you have a software project in which you need a fast and space-efficient approximate set data structure, like a Bloom filter? Then probably what you want is actually a cuckoo filter, a plug-in replacement for Bloom filters that is faster, more space-efficient, and more versatile (because it allows elements to be deleted as well as inserted).

Read more...Collapse )
 
 
0xDE
17 April 2016 @ 11:23 pm
At LATIN, Allan Borodin brought my attention to a recent paper of his with Yuli Ye, "Elimination graphs" (TALG 2012), about an idea that combines local properties of graphs with degeneracy.

Read more...Collapse )
 
 
0xDE
16 April 2016 @ 06:38 pm
I recently traveled to Ensenada (my first visit to Mexico, despite its closeness) for LATIN 2016. This was our view every morning on our arrival to CICESE, the research center hosting the conference, for the conference breakfast.



The rest of my photos include several from the conference excursion and dinner in the Valle de Guadalupe, Mexico's wine region.
 
 
0xDE
15 April 2016 @ 09:43 pm
I continue to find it ironic that the best way I can find to index my posts on Google+, a social network platform launched in 2011 by a major search engine company, and to make it possible for me to search for and find the old posts, is to copy them onto a much older social network platform from 1999 that, except for the Russians, has now mostly fallen into disuse.
 
 
 
0xDE

I recently asked my data structures class the following question: suppose you fill in an n-cell array by a random permutation. What is the probability that the result is a valid binary min-heap?

Read more...Collapse )
 
 
0xDE
18 March 2016 @ 09:07 pm
Some scenes near the entrance to the Bellairs Research Institute, in Holetown, Barbados. (You can see the institute's nameplate in the left background to this one). It's actually quite an upscale touristy town, but that wasn't the feeling I was trying to catch in these photos.



( More photos )
 
 
 
0xDE
14 March 2016 @ 10:35 am
I recently returned from the Fourth Annual Workshop on Geometry and Graphs at the Bellairs Research Institute in Barbados. The youngest participant was Günter Rote's daughter:



( More photos of workshop participants )