I have another new preprint on arXiv this evening: Folding a Paper Strip to Minimize Thickness, arXiv:1411.6371, with six other authors (Demaine, Hesterberg, Ito, Lubiw, Uehara, and Uno); it's been accepted at WALCOM.

The basic goal of this is to try to understand how to measure the thickness of a piece of paper that has been folded into a shape that lies flat in the plane. For instance, in designing origami pieces, it's undesirable to have too much thickness, both because it wastes paper causing your piece to be smaller than it needs to and because it may be an obstacle to forming features of your piece that are supposed to be thin.

The obvious thing to do is to just count the number of layers of paper that cover any point of the plane, but can be problematic. For instance, if you have two offset accordion folds (drawn sideways below)

/\/\/\/\/\
          \/\/\/\/\/

then it's not really accurate to say that the thickness is the same as if you just had one of the two sets of folds: one of the two folds is raised up by the thickness of the other one so the whole folded piece of paper is more like the sum of the thicknesses of its two halves.

In the preprint, we model the thickness by assuming that the flat parts of the paper are completely horizontal, at integer heights, that two overlapping parts of paper have to be at different heights, and that a fold can connect parts of paper that are at any two different heights. But then, it turns out that finding an assignment of heights to the parts of paper that minimizes the maximum height is hard, even for one-dimensional problems where we are given a crease pattern of mountain and valley folds as input, without being told exactly how to arrange those folds. The reason is that there can be ambiguities about how the folded shape can fit into pockets formed by other parts of the fold, and choosing the right pockets is difficult.