Finding Tarski Fixed Points is Hard

5^th February 2020, 13:00
John Fearnley
University of Liverpool

Abstract

Tarski's fixed point theorem states that every order preserving function from a complete lattice to itself has a fixed point. It was recently shown by Etessami, Papadimitriou, Rubinstein, and Yannakakis that finding a Tarski fixed point is in PPAD and PLS, and that in the two-dimensional version of the problem, (log n)^2 queries are required to solve the problem. We show that finding a Tarski fixed point is UEOPL-hard, and that in the k-dimensional version, (log n)^k queries are required to solve the problem.

Joint work with Rahul Savani.