Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SPERNER'S LEMMA:
Reports tagged with Sperner's lemma:
TR06-037 | 10th February 2006
Xi Chen, Xiaotie Deng

#### On the Complexity of 2D Discrete Fixed Point Problem

While the 3-dimensional analogue of the Sperner problem in the plane was known to be PPAD-complete, the complexity of the 2D-SPERNER itself is not known to be PPAD-complete or not. In this paper, we settle this open problem proposed by Papadimitriou~\cite{PAP90} fifteen years ago. This also allows us to derive ... more >>>

TR22-160 | 31st October 2022
Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, N. V. Vinodchandran

#### The Geometry of Rounding

Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of $\mathbb{R}^d$ are equivalent, we introduce the following natural partition problem which we call the secluded hypercube partition problem: Given $k\in\mathbb{N}$ (ideally small) and $\epsilon>0$ (ideally large), is there a partition of ... more >>>

ISSN 1433-8092 | Imprint