?

Log in

 
0xDE
Suppose you have an array of n real numbers (or other totally ordered values that you can compare but not treat as small integers). You want to answer queries that specify a contiguous subarray and return the sorted sequence of values within that subarray. Without any preprocessing you could query a subarray of length k in time O(k log k), by pulling out the subarray and then comparison sorting it. With preprocessing, how much better can we do?

Read more...Collapse )
 
 
0xDE
I have another new paper out on arXiv: "Maximizing the Sum of Radii of Disjoint Balls or Disks", arXiv:1607.02184, to appear at CCCG. The problem solved by the paper is, as the title says, to find a set of disks in the plane (or balls in a metric space), with given centers, that do not overlap each other and have as large a sum of radii as possible. There's some weak motivation in terms of map labeling, but really it's an exercise in how LP duality and sparse graph theory can be used to find efficient combinatorial algorithms for problems that can be solved numerically and less efficiently by linear programming. In fact as I was writing it I half-expected the metric space part to show up as an exercise in a book on related topics, such as Vazirani's book on primal-dual approximation algorithms. Maybe it is and I just didn't find the reference; if so please tell me.

Read more...Collapse )
 
 
0xDE
04 July 2016 @ 06:11 pm
Here's an update to the streaming integer point puzzle that I posted yesterday. Recall that the puzzle was to generate all the integer points in the plane, in constant amortized time per point, using as little space as possible. In the post, I gave a solution whose space is proportional to the square root of the number of points generated so far. In the comments to my G+ link to the post, Sariel Har-Peled suggested an improvement, but without much detail. So, here is some detail for Sariel's idea.

Read more...Collapse )
 
 
0xDE
Here's a puzzle in streaming algorithms: suppose you want to generate a stream of all the (infinitely many) integer points (x,y) in the plane, in sorted order by their Euclidean distance from the origin. How little space do you need?

Read more...Collapse )
 
 
0xDE
02 July 2016 @ 10:42 am

Here are some of my photos from the SWAT excursion to the Reykjanes peninsula, and of some of the participants. Iceland (even this small part of it) was easily as scenic as I had been led to believe.





( The rest of the photos )

 
 
0xDE
30 June 2016 @ 10:35 pm
I'm getting the hard-to-quantify but persistent feeling that G+ is getting quieter lately...too much of the actual content has moved elsewhere, maybe, and I'm seeing more of the filler. Wouldn't be surprised if Google pulls the plug soon, like they have on other projects. But for now here's my filler for the last couple of weeks.
 
 
0xDE
28 June 2016 @ 09:22 pm
Here's the first of two batches of photos from my recent visit to Iceland. This set is from before the conference, when I had most of a day free to wander around Reykjavik. It's mostly of street art from the touristy shopping area where my hotel was located, and graffiti from some rougher looking areas nearby. This shot was the first I had a chance to take, of a building across the street from my hotel:



( More photos )
 
 
0xDE
25 June 2016 @ 09:04 am
I'm now making my way back from Iceland, where I attended the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Rather than providing a run-down of the talks and results I found interesting (you can choose your own from the conference proceedngs, this year provided as open-access through LIPIcs), I thought it might be more fun to mention a few open problems that people mentioned along the way and that caught my attention.

Read more...Collapse )
 
 
0xDE
19 June 2016 @ 06:02 pm
I've been slow processing this but the arrival of the official shots reminded me: this is from my daughter's graduation a month ago from Lesley (with a B.F.A. in photography).



Sara tells me she likes the other shot better, though.
 
 
 
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 )