Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

Research lectures, seminars and events

The events listed in this area are research seminars, workshops and lectures hosted by Durham University departments and research institutes. If you are not a member of the University, but  wish to enquire about attending one of the events please contact the organiser or host department.


 

November 2020
SunMonTueWedThuFriSat
October 2020 December 2020
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30

Events for 24 November 2020

John Fearnley: A faster algorithm for finding Tarski fixed points

1:00pm, Online

Dang 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, and indeed this has been proven for two-dimensional instances. 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. Paper on arxiv: https://arxiv.org/abs/2010.02618

Contact algorithms.complexity@dur.ac.uk for more information about this event.