The Query Complexity of Approximating Max-Cut in the Value Oracle Model

Abstract

This thesis considers the problem of global max-cut on a weighted undirected graph in the \emph{value oracle model}. In this model, the algorithm does not have direct access to the graph and instead only has access to an oracle that can answer queries about the value of any cut. The algorithm's cost is simply the number of queries made. This model arises as a natural special case of submodular function maximisation with a value oracle.

We consider both deterministic and randomised algorithms, and investigate the query complexity of achieving a $c$-approximation for any positive $c \leq 1$. We make substantial progress towards identifying the query complexity for all values of $c$ and both the deterministic and randomised settings up to logarithmic factors. We observe a ``phase transition" analogous to general submodular function maximisation at $c = 1/2$, where the complexity of solving the problem for $c > 1/2$ is much harder than solving it for $c < 1/2$. Specifically, we show that achieving a $c$-approximation can be done with $O(\log n)$ queries when $c < 1/2$ but requires at least $O(n/\log n)$ queries when $c > 1/2$. We also observe what could be an additional jump at $c = 1$, showing that deterministic algorithms require at least $\Omega(n^2)$ queries to find the exact value of the max cut.