A Pseudopolynomial Algorithm for Alexandrov's Theorem (2009)
Kane, Daniel, Price, Gregory Nathan, Demaine, Erik
Alexandrov's Theorem states that every metric with the global topology and local geometry required of a convex polyhedron is in fact the intrinsic metric of some convex polyhedron. Recent work by...
Muñiz Ortiz, Jorge G., Opoka, Robert, Kane, Daniel, Cartwright, Iain L.
Chronic exposure to arsenic-contaminated drinking water can lead to a variety of serious pathological outcomes. However, differential responsiveness within human populations suggests that...
A Pseudopolynomial Algorithm for Alexandrov's Theorem (2008)
Kane, Daniel, Price, Gregory N., Demaine, Erik D.
Alexandrov's Theorem states that every metric with the global topology and local geometry required of a convex polyhedron is in fact the intrinsic metric of some convex polyhedron. Recent work by...
Abstract Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane (2008)
Timothy Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, ...
We provide an efficient data structure for dynamically maintaining a ham-sandwich cut of two nonoverlapping convex polygons in the plane. Given two non-overlapping convex polygons P1 and P2 in the...
New results on the least common multiple of consecutive integers (2008)
When studying the least common multiple of some finite sequences of integers, the first author introduced the interesting arithmetic functions $g_k$ $(k \in \mathbb{N})$, defined by $g_k(n) :=...
6.897: Advanced Data Structures Spring 2005 (2008)
Prof Erik, Demaine Scribe, Daniel Kane
In this lecture, we discuss the implementation of the fusion tree data structure [2], as part of our discussion of the predecessor problem. Given a static set, fusion trees can answer predecessor or...
Abstract Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane (2008)
Timothy Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, ...
We provide an efficient data structure for dynamically maintaining a ham-sandwich cut of two nonoverlapping convex polygons in the plane. Given two non-overlapping convex polygons P1 and P2 in the...
The Chinese language : its history and current usage (2006)
The Chinese Language is a brief introduction to the main characteristics of Chinese, written to be accessible to beginning students as well as anyone with a general interest in Chinese language and...
The Chinese language : its history and current usage (2006)
The Chinese Language is a brief introduction to the main characteristics of Chinese, written to be accessible to beginning students as well as anyone with a general interest in Chinese language and...
Complexity of finding Nash equilibria in 0-1 bimatrix games (2005)
Abbott, Tim, Kane, Daniel, Valiant, Paul
We exhibit a polynomial reduction from the problem of finding a Nashequilibrium of a bimatrix game with rational coefficients to the problemof finding a Nash equilibrium of a bimatrix game with 0-1...
Complexity of finding Nash equilibria in 0-1 bimatrix games (2005)
Abbott, Tim, Kane, Daniel, Valiant, Paul
We exhibit a polynomial reduction from the problem of finding a Nashequilibrium of a bimatrix game with rational coefficients to the problemof finding a Nash equilibrium of a bimatrix game with 0-1...
On the complexity of two-player win-lose games (2005)
Tim Abbott, Daniel Kane, Paul Valiant
The efficient computation of Nash equilibria is one of the most formidable challenges in computational complexity today. The problem remains open for two-player games. We show that the complexity of...
Abstract On the Complexity of Two-Player Win-Lose Games (2005)
Tim Abbott, Daniel Kane, Paul Valiant
The efficient computation of Nash equilibria is one of the most formidable computational-complexity challenges of today. The problem remains open for two-player games. We show that the complexity of...