Algorithms for Monotone Fixed-Point Computation Problems

该项目涉及理论计算机科学、算法与复杂性、逻辑与组合数学等领域。该项目将研究将有限格映射到自身的单调函数，关键目标是设计算法来尽可能有效地计算此类函数的不动点，并证明下界，表明渐近更有效的算法是无法实现的。不动点的计算在许多领域都有重要意义，包括优化、博弈论、机器学习和马尔科夫过程。理解基于塔尔斯基定理寻找不动点的复杂性在经济学领域和计算机科学领域都有意义。特别感兴趣的将是对其中一些设置中出现的连续单调函数进行离散化所产生的不动点的近似。我们想要了解在这些情况下，除了现有的算法之外，在效率方面有哪些可能的改进。格子是一个具有偏序和“相交”和“连接”概念的数学对象。格推广了具有包含、交和并的集合系统。从一个格到它本身的单调函数f是一个尊重偏序的函数，这意味着对于任何格元x和y，如果x在偏序上先于y，则f(X)在偏序上先于f(Y)。在这个项目中，我们关注的有限格子是具有有限长度N的边的d维欧氏网格。这些有限格子是由于离散欧氏立方体上的连续单调函数而产生的，这在应用中是经常出现的。塔斯基定理是格论中的一个基本结果，它意味着从有限格到它自己的任何这样的单调函数(实际上是从一个“完整”格到它自己的任何单调函数)都有一个不动点，并且实际上有一个不动点的子格，有一个最小和最大的元素。在有限格情形下，塔斯基定理的证明也给出了计算最小不动点的方法。众所周知，最小不动点的计算本身是一个NP-Hard问题，然而，当函数被简洁地表示(通过布尔回路)时，寻找某个不动点(不一定是最小一个)的复杂性仍然是一个悬而未决的问题。这个项目旨在考虑在有限格子上寻找给定单调函数的某个不动点的问题，特别是在边长为N的二维网格上。我们特别希望在“预言模型”中考虑这个问题的计算复杂性，即根据寻找不动点所需要的对函数的查询次数(当它被视为黑盒时)。Etessami，Papadimitriou，Yannakakis和Rubinstein最近的工作(“Tarski‘s定理，Supermodular Games，and the Complexityof Equilibria”，2019)在2维情况下取得了进展，建立了Theta(log^2N)所需查询的紧密渐近上下界。这个项目旨在将他们的结果和方法扩展到3个或更多维度的情况，目标是收紧这些更高维度的情况的界限。基于[Dang-qi-Ye，2012]的二分搜索算法的一个已有的推广已经被证明使用O(log^d(N))个查询在格上找到一个不动点。然而，目前尚不清楚是否有其他方法能够在渐近较少的查询中找到不动点。以前在二维的紧致性结果利用了一类“人字形函数”的性质，表明任何随机化算法在这类查询上都不能比广义二进制搜索算法好(渐近地)。在三维函数的某些子类上研究随机化算法可能会潜在地让我们证明现有算法是最好的可能。感兴趣的一个子类别是那些具有唯一固定点的类别。

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.