?

Log in

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 )
 
 
 
0xDE
When dealing with finite graphs, it's normal to define (rooted) trees in a graph-theoretic way: a tree is a directed graph with a designated root in which each vertex has a unique walk to the root. The ancestor-descendant relation can be derived from this: an ancestor of x is a vertex that can be reached by a walk from x. However, it's also possible to turn this around, and define trees in terms of their ancestor-descendant relations, with the parent-child relation derived from that. In the turned-around definition, a tree is a partial order with a designated root element that is a predecessor of every element, such that the predecessors of each element are totally ordered. The parent of an element would then be the maximum of its predecessors. So graph-theoretic finite trees and order-theoretic finite trees are really the same things as each other, in a different disguise. But that's no longer true when we go from finite to infinite: we can define trees in either of these two ways, but we get different things.

Read more...Collapse )
 
 
0xDE
16 February 2016 @ 10:12 pm
I spent the president's day holiday hiking in Black Star Canyon, a wilderness area nearby enough that it's barely outside Irvine and remote enough that in the upper part of the falls trail (where you're basically scrambling up a creek instead of hiking along a trail) there's no sign of civilization to be seen except for the other hikers, airplanes overhead, and occasional painted rocks.



( More photos of Black Star Canyon )
 
 
 
0xDE
I have a new preprint, "Distance-Sensitive Planar Point Location" (arXiv:1602.00767, with Aronov, de Berg, Roeloffzen, and Speckmann) whose title and abstract may already be a bit intimidating. So I thought I would at least try to explain what it's about in simpler terms.

Read more...Collapse )
 
 
 
0xDE
27 January 2016 @ 09:59 pm
The image below is a drawing of (part of) a pseudoline arrangement, a collection of curves in the plane that behave like lines in the sense that each curve partitions the plane into two unbounded regions and each two curves have exactly one point of intersection, where they cross. It's from my latest arXiv preprint, "Convex-Arc Drawings of Pseudolines" (with Mereke van Garderen, Bettina Speckmann, and Torsten Ueckerdt, arXiv:1601.06865).



Read more...Collapse )
 
 
0xDE
21 January 2016 @ 03:59 pm
In my previous post here I remarked that the hypercubes are the face lattices of simplexes. I also drew the face lattice of a square, which you might have noticed forms a planar graph, the graph of another polyhedron (the tetragonal trapezohedron, an octahedron with eight kite-shaped faces). This turns out not to be a coincidence. For every many (see comments) d-dimensional convex polytopes P, the covering graph of its face lattice is the graph of a (d + 1)-dimensional convex polytope, which for lack of a better name I'll call the face incidence polytope, or incidence polytope for short (although that shorter phrase does already have a different meaning).

Read more...Collapse )
 
 
0xDE

The binary strings of a given length, like the length-8 string "11011110" in the name of my blog, can be thought of as naming the vertices of a hypercube of the same dimension: each bit is one of the Cartesian coordinates of a vertex. In the same way, binary strings with wildcard characters, like "11***1*0", can be thought of as naming the nonempty faces of the hypercube; the number of stars gives the dimension of the face, up to the string "********" which represents the whole cube. But there's one more face, the empty set Ø, which cannot be represented in the same way.

As with the collection of faces of any polyhedron, the faces of a hypercube can be partially ordered by inclusion, and this partial order forms a lattice: every family of faces has a unique meet (its greatest lower bound, the intersection of all the faces), and a unique join (its least upper bound, the unique minimal face that contains all of them). For instance, the meet of two opposite sides of an ordinary 3-dimensional cube (for instance the two sides **0 and **1) is the empty set (that's why Ø needs to be a face) and the join of the same two opposite sides is the whole cube ***. This is the face lattice of the hypercube. (The hypercube itself can also be viewed as a face lattice of another kind of polyhedron, a simplex.)

Here's an example, for the face lattice of a square (a 2-dimensional cube). The inclusion ordering is shown by the edges, and each lattice element is labeled both by the part of the square it represents and by the corresponding wildcard string.

Read more...Collapse )
 
 
 
0xDE
12 January 2016 @ 11:53 pm
The 27th ACM-SIAM Symposium on Discrete Algorithms, in Arlington, Virginia, just finished, along with its satellite workshops ALENEX (experimental algorithmics, one of the most heavily rejected topics from SODA) and ANALCO (analytic combinatorics). With four parallel sessions going at most times, there's no way to take in everything, so here are my impressions of the small fraction I saw.

Read more...Collapse )