24 citations · 34 across the 3 of their papers we have counts for
6 papers
No-go Theorem for Acceleration in the Hyperbolic Plane
Linus Hamilton, Ankur Moitra
In recent years there has been significant effort to adapt the key tools and ideas in convex optimization to the Riemannian setting. One key challenge has remained: Is there a Nest…
The Paulsen Problem Made Simple
Linus Hamilton, Ankur Moitra
The Paulsen problem is a basic problem in operator theory that was resolved in a recent tour-de-force work of Kwok, Lau, Lee and Ramachandran. In particular, they showed that every…
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
Zachary Abel, Jeffrey Bosboom, Michael Coulombe +7
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…
Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications
Linus Hamilton, Frederic Koehler, Ankur Moitra
Markov random fields area popular model for high-dimensional probability distributions. Over the years, many mathematical, statistical and algorithmic problems on them have been st…
Braid is undecidable
Linus Hamilton
Braid is a 2008 puzzle game centered around the ability to reverse time. We show that Braid can simulate an arbitrary computation. Our construction makes no use of Braid's unique t…
Anarchy is free in network creation
Ronald Graham, Linus Hamilton, Ariel Levavi +1
The Internet has emerged as perhaps the most important network in modern computing, but rather miraculously, it was created through the individual actions of a multitude of agents…