BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260920T145859Z
UID:Seminar-EcCo-615@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20200205T130000
DTEND:20200205T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:John Fearnley: Finding Tarski Fixed Points is Hard\n\nTarski'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.\n\nJoint work with Rahul Savani.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=615
LOCATION:
END:VEVENT
END:VCALENDAR