Discrete fixed points: models, complexities, and applications

Xiaotie Deng, Qi Qi, Amin Saberi, Jie Zhang

Research output: Contribution to journalArticlepeer-review

8 Citations (SciVal)


We study three discrete fixed point concept (SPERNER, DPZP, BROUWER) under two different models: the polynomial-time function model and the oracle function model. We fully characterize the computational complexities of these three problems. The computational complexity unification of the above problems gives us more choices in the study of different applications. As an example, by a reduction from DPZP, we derive asymptotically equal lower and upper bound for TUCKER in the oracle model. The same reduction also allows us to derive a single proof for the PPAD-completeness of TUCKER in any constant dimension, which is significantly simpler than the recent proofs.
Original languageEnglish
Pages (from-to)636-652
Number of pages17
JournalMathematics of Operations Research
Issue number4
Early online date14 Oct 2011
Publication statusPublished - 30 Nov 2011


Dive into the research topics of 'Discrete fixed points: models, complexities, and applications'. Together they form a unique fingerprint.

Cite this