Algorithms for Monotone Fixed-Point Computation Problems

点击翻译按钮获取中文摘要

The project relates to the areas of Theoretical Computer Science,Algorithms and Complexity, and Logic & Combinatorics. The project willstudy monotone functions that map a finite lattice to itself, and thekey goal is to either devise algorithms to compute a fixed point forsuch a function as efficiently as possible, and to prove lower bounds,showing that algorithms that are asymptotically more efficient can notbe achieved.Computation of fixed points has significance in a variety of areas,including optimization, game theory, machine learning, and Markovprocesses. Understanding the complexity of finding a fixed pointbased on Tarski's theorem has implications in the field of economics,as well as computer science. Of particular interest will beapproximation of fixed points arising from discretising the continuousmonotone functions arising in some of these settings. We want tounderstand what improvements in efficiency are possible in thesesituations, beyond existing algorithms.Lattices are a mathematical object with a partial ordering and notionsof "meet" and "join". Lattices generalise set systems that areequipped with inclusion, intersection and union. A monotone functionf, from a lattice to itself, is one that respects the partial order,meaning that for any lattice elements x and y, if x precedes y in thepartial order, then f(x) precedes f(y) in the partial order. In thisproject the finite lattices we focus on are the d-dimensionalEuclidean grid, with sides of finite length N. These arise fromdiscretising continuous monotone function on a euclidean cube, whicharises frequently in applications. Tarski's Theorem, a fundamentalresult in lattice theory, implies that any such monotone function froma finite lattice to itself (in fact any monotone function from a"complete" lattice to itself) has a fixed point, and in fact has asublattice of fixed points, with a least and greatest element. In thefinite lattice case, the proof of Tarski's theorem also yields amethod of computing the least fixed point. It is known thatcomputation of the least fixed point itself is an NP-hard problem,however the complexity of finding some fixed point (not necessarilythe least one) remains an open question, when the function ispresented succinctly (via a boolean circuit).This project aims to consider the problem of finding some fixed pointof a given monotone function on a finite lattice, in particular, thed-dimensional grid with sides of length N. We in particular wish toconsider the computational complexity of this problem in the "oraclemodel", meaning in terms of the number of queries to the function(when it is viewed as a black box) that are required in order to finda fixed point. Recent work by Etessami, Papadimitriou, Yannakakis andRubinstein ("Tarski's Theorem, Supermodular Games, and the Complexityof Equilibria", 2019) has made progress in the 2-dimensional case,establishing tight asymptotic upper and lower bounds of Theta(log^2 N)required queries. This project aims to extend their results andmethodology to the case of 3 or more dimensions, with the goal oftightening bounds in these higher dimensional cases. An existinggeneralization of the binary search algorithm (due to[Dang-Qi-Ye,2012], has been shown to find a fixed point on theselattices using O(log^d (N)) queries. However, it is unknown whetherother methods could find a fixed point in asymptotically fewerqueries.The prior tight results in 2-dimensions exploited properties of aclass of "Herringbone Functions" to show any randomized algorithm cando no better (asymptotically) than the generalized binary searchalgorithm on this class. Studying randomized algorithms on certainsub-classes of 3-dimensional functions could potentially allow us toshow that the existing algorithm is best possible. One sub-class ofinterest is those with a unique fixed point.