BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260909T011235Z
UID:Seminar-EcCo-975@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20201216T130000
DTEND:20201216T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:John Fearnley: A faster algorithm for finding Tarski fixed points\n\nDang et al. have given an algorithm that can find a Tarski fixed point in a k-dimensional lattice of width n using O(log^k n) queries. Multiple authors have conjectured that this algorithm is optimal [Dang et al., Etessami et al.], and indeed this has been proven for two-dimensional instances [Etessami et al.]. We show that these conjectures are false in dimension three or higher by giving an O(log^2 n) query algorithm for the three-dimensional Tarski problem, which generalises to give an O(log^{k−1} n) query algorithm for the k-dimensional problem when k≥3. \n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=975
LOCATION:
END:VEVENT
END:VCALENDAR