We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw a simple path in a rectangular grid graph from a start vertex to a destination vertex. The different puzzle types place different constraints on the path: preventing some edges from being visited (broken edges); forcing some edges or vertices to be visited (hexagons); forcing some cells to have certain numbers of incident path edges (triangles); or forcing the regions formed by the path to be partially monochromatic (squares), have exactly two special cells (stars), or be singly covered by given shapes (polyominoes) and/or negatively counting shapes (antipolyominoes). We show that any one of these clue types (except the first) is enough to make path finding NP-complete ("witnesses exist but are hard to find"), even for rectangular boards. Furthermore, we show that a final clue type (antibody), which necessarily "cancels" the effect of another clue in the same region, makes path finding $\Sigma_2$-complete ("witnesses do not exist"), even with a single antibody (combined with many anti/polyominoes), and the problem gets no harder with many antibodies. On the positive side, we give a polynomial-time algorithm for monomino clues, by reducing to hexagon clues on the boundary of the puzzle, even in the presence of broken edges, and solving "subset Hamiltonian path" for terminals on the boundary of an embedded planar graph in polynomial time.

Zachary Abel Jeffrey Bosboom Michael Coulombe Erik D. Demaine Linus Hamilton Adam Hesterberg Justin Kopinsky Jayson Lynch Mikhail Rudoy Clemens Thielen

We develop the basic topological properties of compact polygons, i.e. of compact topological Tits buildings of rank two. It is proved that the Coxeter diagram of such a building is always crystallographic, that is, compact connected n-gons exist only for n=3,4,6. We classify compact polygons which admit a transitive group action, showing that such a polygon is Moufang and thus related to a real Lie group of rank 2.

Linus Kramer

Using a characterization of parabolics in reductive Lie groups due to Furstenberg, elementary properties of buildings, and some algebraic topology, we give a new proof of Tits' classification of 2-transitive Lie groups.

Linus Kramer

We classify all closed 1-connected manifolds $M$ which look like projective planes, i.e. with integral homology $H_*(M)=Z^3$. Furthermore, we give an explicit construction of these manifolds as Thom spaces of open disk bundles.

Linus Kramer

We give a complete diffeomorphism classification of 1-connected manifolds (of dimension different from 4) whose integral homology is H(M)=Z+Z+Z.

Linus Kramer Stephan Stolz

We give a geometric interpretation of the building associated to the real Lie group E_6(-14) in terms of its 54-dimensional module.

Torsten Kurth Ralf Köhl Linus Kramer

This is a survey on nondiscrete euclidean buildings, with a focus on metric properties of these spaces.

Linus Kramer

We classify compact homogeneous geometries of irreducible spherical type and rank at least 2 which admit a transitive action of a compact connected group, up to equivariant 2-coverings. We apply our classification to polar actions on compact symmetric spaces.

Linus Kramer Alexander Lytchak

We prove continuity results for abstract epimorphisms of locally compact groups onto finitely generated groups.

Linus Kramer

We study a bilinear multiplication rule on 2x2 matrices which is intermediate between the ordinary matrix product and the Hadamard matrix product, and we relate this to the hyperbolic motion group of the plane.

Linus Kramer Peter Kramer Vladimir Man'ko