Log in

14 November 2016 @ 10:24 pm

The game of subtract-a-square is played by two players with a pile of coins. They take turns taking a square number of coins until none are left. The last player to move wins. So how can we play this game optimally and efficiently? As it turns out, there's some deep number theory lurking in the answer.

Read more...Collapse ) Update: See a later post for some experiments on the growth rate of this set.
08 November 2016 @ 09:24 pm
Most or all of the following seem destined to be gone, in the US and (for some) the world:

Climate change countermeasures and continued research.
A coordinated response to extreme climate events.
Regulation of carbon dioxide as a pollutant.
National parks and wildlife preserves.
Guaranteed health care.
State-level limits on how predatory the health care industry can be.
A recovering economy and continuing tech boom.
Internet neutrality.
The minimum wage.
Social security and medicare.
The Supreme Court.
Abortion rights and access to contraception.
Anti-discrimination laws and same-sex marriage.
The truth defense from libel.
No wholesale legal persecution of opposition parties.
Restrictions on gun ownership.
Religious freedom for anyone other than Christians.
Limits on how blatantly Christianity can be used as an excuse for bigotry.
Redistricting rules that prevent continued gerrymandering.
Anything resembling adequate polling places in poor and minority districts.
Universal voter registration.
Pressure to reduce sexual harassment and sexual assaults in our universities, or anywhere else.
Reduced or free college tuition for anyone.
Any hope of reining in the out-of-control racists in our police forces.
Farm workers, housecleaners, construction workers, food service workers, and all those other people who do the things nobody else wants to do.
The ability to bring in talented students and workers from other countries.
NATO and the free Baltic states.
Nuclear non-proliferation.
A president who wouldn't start a nuclear war based on a whim or personal slight.

Clinton could still pull this out, mathematically, but barring a miraculous turnaround in Wisconsin or Arizona there doesn't seem to be any remaining path to 270 electoral votes. And with the House and Senate in Republican hands and a free slot on the court there are no checks and balances left; the voters were the last line of defense.

Anyone in a nice safe part of the world looking for academic computer scientists? Canada? Iceland? New Zealand?
23 October 2016 @ 05:51 pm

In Conway's Game of Life, and other cellular automata with the same neighborhood structure, you can determine the values of the cells in any 2x × 2x square of cells from their values x steps earlier in a bigger 4x × 4x square. If we view this as a time-space diagram, with two of the dimensions as the spatial dimensions of the Life grid and the third dimension as time, we can view the bigger starting square and the smaller resulting square as the bottom and top of a sort of stepped pyramid formed by stacking concentric squares. The values of the cells in each layer of the pyramid are determined by the ones in the layer below. The squares shrink inward as they rise upward, because the other cells outside the pyramid need more information (outside the base of the pyramid) to determine their values. The image below shows this construction for x = 1, 2, and 4, with each time-space state of a cell represented as a cube.

Read more...Collapse )

After posting about a recursive generator for the Kolakoski sequence yesterday, I found the following alternative and non-recursive algorithm, which generates the same sequence in a linear number of bit operations with a logarithmic number of bits of storage.

def Kolakoski():
    x = y = -1
    while True:
        yield [2,1][x&1]
        f = y &~ (y+1)
        x ^= f
        y = (y+1) | (f & (x>>1))

Like the previous one, this can be understood as traversing an infinite tree. The tree is defined using essentially the same rules as before: two consecutive nodes on the same level of the tree have the same number of children if and only if they have the same parent. However, it extends infinitely upward rather than infinitely downward, with two children for each node on the leftmost path. Each level of the tree has the same sequence of degrees, which equals the Kolakoski sequence starting from its second position (the missing first position is why this starts at x = y = -1 rather than zero).

The algorithm traverses the bottom level of the tree in left-to-right order. As it does, the variable x maintains, in its binary representation, the numbers of children modulo 2 of the path of nodes extending infinitely upwards from the current leaf. All but finitely many (logarithmically many as a function of the position of the leaf) of these bits are zero, so (after the first step) x is a non-negative finite number with logarithmically many bits. The variable y, similarly, maintains a sequence of bits corresponding to the nodes on the same path that are 0 when the node is a left child of a degree-2 node and 1 otherwise. Again, finitely many of these bits are 1, so y is non-negative with logarithmically many bits. The bit manipulation tricks of the algorithm merely update these two variables to describe the next path in the traversal.

Update 10/16: Fast C++ implementation by Jörg Arndt

13 October 2016 @ 04:46 pm

Draw an infinite tree according to the following rules:

  • Each tree node is labeled 1 or 2, and has a number of children equal to its label.
  • If the nodes are placed into their breadth-first search ordering, then two consecutive nodes have the same label if and only if they have the same parent.

There are two choices for the root label, but the trees they produce are almost the same as each other, so let's say the root is labeled 2, giving the tree shown below together with its spiraling breadth first search order. (If the root were labeled 1, the only difference would be to add one more node labeled 1 above the node that is the root in the drawing.)

Then the breadth-first sequence of labels that we obtain is exactly the Kolakoski sequence, starting from its third term. The Kolakoski sequence begins 1,2,2,1,1,2,1,2,2,1,2,2... and has the property that it equals the sequence of run-lengths in itself: the numbers 1, 2, 2, etc. are exactly the numbers of consecutive 1's, 2's, 1's, etc. in the sequence. Our tree is defined in such a way that each run of consecutive equal labels comes from the same parent, so the run-lengths of the sequence equal the numbers of children of the nodes, which equal the labels of the nodes, which define the sequence itself.

Read more...Collapse )

ETA: See next post for an alternative algorithm that avoids the recursion.

While fixing up the Wikipedia article on the constant-space streaming majority algorithm of Boyer and Moore I ran across a stackoverflow question complaining about some sloppy analysis that I had already removed from the Wikipedia article. As a quick reminder, the algorithm stores one element from its input sequence, uses comparisons of that element with input values to decide whether to increment or decrement a counter, and uses comparisons of the counter with zero to decide when to replace the stored element.

Read more...Collapse )
16 September 2016 @ 04:55 pm
I have another new arXiv preprint: "Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection", arXiv:1609.04512, with Juan Besa, Will Devanny, and Mike Goodrich. The same paper also appeared at ATMOS 2016; the two versions differ only in formatting and their theorem numbering scheme.

Read more...Collapse )
07 September 2016 @ 12:17 am
It's pretty well known that a finite lattice has order dimension ≤ 2 if and only if its Hasse diagram is an st-planar graph (below left), and every transitively reduced st-planar graph defines a 2-dimensional lattice in this way. The reference I know of for this is Platt, "Planar lattices and planar graphs", J. Comb. Th. 1976. And I don't know who first observed that the 2-dimensional finite distributive lattices are the ones that can be drawn as grid graphs (below right) but my guess would be Garrett Birkhoff.

My own paper "Upright-quad drawing of st-planar learning spaces" described an analogous geometric representation for antimatroids (which in this context can be seen as another special type of lattice). So a recent CS-theory stack-exchange question about planar modular graphs got me wondering: what do the graphs of 2-dimensional modular lattices (a subclass of the planar modular graphs) look like?

Read more...Collapse )
18 August 2016 @ 06:33 pm
Suppose we play the following game. We place a bunch of hexagonal game board tiles on a table, edge-to-edge, to form our playing field. On the field, we place two game pieces, a cop (blue) and a robber (red). The cop and robber take turns, either moving to an adjacent hex or passing (staying put). The cop wins if he can end a turn on the same hex as the robber. The robber wins by evading the cop forever. Who has the advantage?

Read more...Collapse )
07 August 2016 @ 04:37 pm
One of the talks at CCCG was by Ahmad Biniaz, on red-blue-purple spanning graphs: given a partition of a point set into red, blue, and purple points, find a minimum-weight graph such that the red-purple and blue-purple subsets induce connected subgraphs. It can be solved by matroid intersection, but this is slow and Biniaz talked about a faster special case. Anyway, in his talk, Ahmad mentioned a different colored spanning problem: find a minimum spanning tree of the complete bipartite geometric graph determined by a set of red and blue points in the Euclidean plane (with no purple this time). He noted that bichromatic closest pairs can be used to solve it in time O(n log8 n), and asked whether a faster algorithm is possible. The illustration below gives an example of this problem and its solution.

Read more...Collapse )
05 August 2016 @ 05:14 pm
This week I've been in Vancouver for the Canadian Conference on Computational Geometry, where I spoke about radius-sum optimization. This seemed like a good occasion to post a pointer to the slides from my recent conference talks (and to go back through the talks to make sure their slides were all online), so here they are:
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 )