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 will
study monotone functions that map a finite lattice to itself, and the
key goal is to either devise algorithms to compute a fixed point for
such a function as efficiently as possible, and to prove lower bounds,
showing that algorithms that are asymptotically more efficient can not
be achieved.

Computation of fixed points has significance in a variety of areas,
including optimization, game theory, machine learning, and Markov
processes. Understanding the complexity of finding a fixed point
based on Tarski's theorem has implications in the field of economics,
as well as computer science. Of particular interest will be
approximation of fixed points arising from discretising the continuous
monotone functions arising in some of these settings. We want to
understand what improvements in efficiency are possible in these
situations, beyond existing algorithms.


Lattices are a mathematical object with a partial ordering and notions
of "meet" and "join". Lattices generalise set systems that are
equipped with inclusion, intersection and union. A monotone function
f, 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 the
partial order, then f(x) precedes f(y) in the partial order. In this
project the finite lattices we focus on are the d-dimensional
Euclidean grid, with sides of finite length N. These arise from
discretising continuous monotone function on a euclidean cube, which
arises frequently in applications. Tarski's Theorem, a fundamental
result in lattice theory, implies that any such monotone function from
a finite lattice to itself (in fact any monotone function from a
"complete" lattice to itself) has a fixed point, and in fact has a
sublattice of fixed points, with a least and greatest element. In the
finite lattice case, the proof of Tarski's theorem also yields a
method of computing the least fixed point. It is known that
computation of the least fixed point itself is an NP-hard problem,
however the complexity of finding some fixed point (not necessarily
the least one) remains an open question, when the function is
presented succinctly (via a boolean circuit).

This project aims to consider the problem of finding some fixed point
of a given monotone function on a finite lattice, in particular, the
d-dimensional grid with sides of length N. We in particular wish to
consider the computational complexity of this problem in the "oracle
model", 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 find
a fixed point. Recent work by Etessami, Papadimitriou, Yannakakis and
Rubinstein ("Tarski's Theorem, Supermodular Games, and the Complexity
of 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 and
methodology to the case of 3 or more dimensions, with the goal of
tightening bounds in these higher dimensional cases. An existing
generalization of the binary search algorithm (due to
[Dang-Qi-Ye,2012], has been shown to find a fixed point on these
lattices using O(log^d (N)) queries. However, it is unknown whether
other methods could find a fixed point in asymptotically fewer
queries.

The prior tight results in 2-dimensions exploited properties of a
class of "Herringbone Functions" to show any randomized algorithm can
do no better (asymptotically) than the generalized binary search
algorithm on this class. Studying randomized algorithms on certain
sub-classes of 3-dimensional functions could potentially allow us to
show that the existing algorithm is best possible. One sub-class of
interest is those with a unique fixed point.