# On the cut-query complexity of approximating max-cut

Orestis Plevrakis111Princeton University<EMAIL_ADDRESS>Seyoon
Ragavan222Princeton University<EMAIL_ADDRESS>S. Matthew
Weinberg333Princeton University<EMAIL_ADDRESS>
###### Abstract

We consider the problem of query-efficient global max-cut on a weighted
undirected graph in the value oracle model examined by [RSW18]. This model
arises as a natural special case of submodular function maximization: on query
$S\subseteq V$, the oracle returns the total weight of the cut between $S$ and
$V\backslash S$.

For most constants $c\in(0,1]$, we nail down the query complexity of achieving
a $c$-approximation, for both deterministic and randomized algorithms (up to
logarithmic factors). Analogously to general submodular function maximization
in the same model, we observe a phase transition at $c=1/2$: we design a
deterministic algorithm for global $c$-approximate max-cut in $O(\log n)$
queries for any $c<1/2$, and show that any randomized algorithm requires
$\tilde{\Omega}(n)$ queries to find a $c$-approximate max-cut for any $c>1/2$.
Additionally, we show that any deterministic algorithm requires
$\Omega(n^{2})$ queries to find an exact max-cut (enough to learn the entire
graph), and develop a $\tilde{O}(n)$-query randomized $c$-approximation for
any $c<1$.

Our approach provides two technical contributions that may be of independent
interest. One is a query-efficient sparsifier for undirected weighted graphs
(prior work of [RSW18] holds only for unweighted graphs). Another is an
extension of the cut dimension to rule out approximation (prior work of
[GPRW20] introducing the cut dimension only rules out exact solutions).

##  1 Introduction

Submodular function optimization is a canonical algorithmic problem, studied
in various computational models. One popular model is the value query model:
given as input black-box access to a submodular function $f(\cdot)$, find
$\arg\max_{S\subseteq[n]}\\{f(S)\\}$ (or $\arg\min_{S\subseteq[n]}\\{f(S)\\}$)
using as few queries as possible.

For submodular function minimization, state-of-the-art algorithms use
$\tilde{O}(n^{2})$ queries [Jia21, LSW15]. Yet, the best lower bounds are
still $\widetilde{\Omega}(n)$ [Har08, GPRW20, LLSZ21, CGJS22]. This prompted
recent work of [RSW18] to consider the special case where $f(\cdot)$ is the
cut function of a graph. That is, an algorithm has “cut query” access to an
underlying graph (it can query a set $S$, and learn the total weight of edges
between $S$ and $V\setminus S$). Surprisingly, in unweighted, undirected
graphs, they find a randomized algorithm for (exact) global min-cut in
$\tilde{O}(n)$ queries, and for (exact) $s$-$t$ min-cut in
$\tilde{O}(n^{5/3})$ queries. While recent, the study of min-cut in the cut
query model now boasts a substantial body of work. Moreover, the tools
developed in these works have found application to seemingly distant areas
such as streaming algorithms [ACK19, MN20] and quantum query complexity [AL21,
LSZ21].

Our work initiates the study of max-cut in the cut-query model. We aim to
understand how many queries are necessary and sufficient for an algorithm to
find a $c$-approximate global max-cut in an undirected, weighted graph.

###  1.1 Our results

We first state our main results below, and also tabulate them in Figure 1.
Soon after, we provide context for these results.

######  Theorem 1.1.

(See Theorems 3.1 and 3.14 for precise statements) For $c=1$, the query
complexity for a deterministic algorithm to achieve a $c$-approximation is
$\Theta(n^{2})$ and the query complexity for a randomized algorithm to do the
same is between $\tilde{\Omega}(n)$ and $O(n^{2})$.

######  Theorem 1.2.

(See Corollary 4.11, Corollary 3.6, and Theorem 3.14 for precise statements)
For $c\in(1/2,1)$, the query complexity for a deterministic algorithm to
achieve a $c$-approximation is between $\Omega(n)$ and $O(n^{2})$ and the
query complexity for a randomized algorithm to do the same is
$\tilde{\Theta}(n)$.

######  Theorem 1.3.

(See Corollary 5.2, Theorem 5.4, and Corollary 3.19 for precise statements)
For $c\in(0,1/2)$, the query complexity for a deterministic algorithm to
achieve a $c$-approximation is $\Theta(\log n)$ and the query complexity for a
randomized algorithm to do the same is $\Theta(1)$.

$c$ | Deterministic | Randomized
---|---|---
$1$ | $\Theta(n^{2})$ | $(\tilde{\Omega}(n),O(n^{2}))$
$(1/2,1)$ | $(\Omega(n),O(n^{2}))$ | $\tilde{\Theta}(n)$
$(0,1/2)$ | $\Theta(\log n)$ | $\Theta(1)$
Figure 1: Summary of our results. For each range of $c$, we state the query
complexity (up to constant and logarithmic factors) that we show for achieving
a $c$-approximation in both the deterministic and randomized settings.
$(n,n^{2})$ indicates settings where we have a lower bound of
$\tilde{\Omega}(n)$ and an upper bound of $O(n^{2})$.

We now provide context for each of our results, beginning with Theorem 1.1.
Observe that there is a straightforward non-adaptive $O(n^{2})$-query
deterministic algorithm to find the max-cut exactly (observed in [RSW18], as
it applies to the min-cut as well). The algorithm can query all singletons and
sets of size 2 and from this learn
$w_{i,j}=\frac{1}{2}(F(\left\\{i\right\\})+F(\left\\{j\right\\})-F(\left\\{i,j\right\\}))$
for all $i,j$ and thus the entire graph. The algorithm can then find the max
cut exactly using brute force, since no more queries need to be made. This
addresses all of the $O(n^{2})$ upper bounds stated in the theorems. Theorem
1.1 shows that this trivial algorithm is optimal among deterministic
algorithms: up to constant factors, any deterministic algorithm must learn the
entire graph in order to find the global max-cut with cut queries.

Next, observe that there is a phase transition at $c=1/2$. Theorem 1.3
establishes that a $(1/2-\varepsilon)$-approximation can be achieved
deterministically with $O(\log n)$ queries (which happen to also be
necessary). On the other hand, even a randomized algorithm needs
$\tilde{\Omega}(n)$ queries to guarantee a $(1/2+\varepsilon)$-approximation.

Finally, observe that we resolve the query complexity for most cases. For
randomized algorithms, the only unresolved cases are $c=1/2$ and $c=1$.444For
the $c=1/2$ case, simply outputting a random cut will achieve a
$(1/2)$-approximation in expectation in $O(1)$ queries. But we are concerned
with the algorithm’s ability to achieve a $c$-approximation with some
probability $p>0$. In this setting, there exists a deterministic $O(n)$-query
algorithm (see Section 5.3) but we do not have a matching lower bound. For
deterministic algorithms, the range $[1/2,1)$ remains unresolved. We elaborate
on these cases more in Section 6.

Before continuing, we note several facts about our results. In the positive
direction, we note that all of our algorithms find a set $S$ that is a
$c$-approximation to the global max-cut (for undirected, weighted graphs with
arbitrarily large weights), rather than simply estimating the value of the
max-cut within a factor of $c$. We refer to these two settings as the _cut
finding_ and _value estimation_ settings respectively. On the other hand, most
of our lower bounds hold even against algorithms in the value estimation
setting. The only exception is our $\tilde{\Omega}(n)$ lower bound on
randomized algorithms for $c>1/2$, which we only prove in the cut finding
setting. Similarly, all algorithms we discuss, except for our
$\tilde{O}(n)$-query randomized algorithm for $c\in(1/2,1)$ and the well-known
$O(n)$-query deterministic greedy algorithm for $c=1/2$, are non-adaptive. On
the other hand, all of our lower bounds hold even against adaptive algorithms.

In the negative direction, we note here that most of our algorithms have
exponential time complexity even though they are query-efficient. For example,
the $O(n^{2})$-query algorithm we just described learns the graph in
polynomial time, but then uses exponential brute force search to actually find
its max-cut. This illustrates that, by focusing on query complexity, we are
primarily concerned with the information theoretic question of how much the
algorithm must learn about the graph to be able to estimate its max-cut, even
with unlimited computation. Note that the most query-efficient algorithms for
submodular function minimization are exponential time as well [Jia21], so this
is not uncommon when prioritizing query complexity.

###  1.2 Technical Highlights

Our results follow from a wide array of techniques. Some results (e.g. our
$\tilde{\Omega}(n)$ lower bound on randomized algorithms for $c$-approximate
max-cut and $c>1/2$) follow from direct constructions of hard distributions —
we defer further discussion of these constructions to the corresponding
technical sections. Some of our results follow from novel techniques that are
likely of independent interest for subsequent work — we quickly highlight
these below.555Additionally, some of our algorithms are reasonably
straightforward (e.g. our $O(\log n)$ deterministic algorithm for
$c$-approximate max-cut when $c<1/2$) — we include discussion of these results
in the relevant technical sections for completeness.

The key ingredient in our $\Omega(n^{2})$-lower bound for exact max-cut is the
_cut dimension_ introduced by [GPRW20] for min-cuts (which has also been
studied in follow-up work [LLSZ21]). The lower bound follows immediately after
establishing that the complete graph on $n$ vertices has max-cut dimension
$\Omega(n^{2})$. More interestingly, we extend the concept of the cut-
dimension to what is roughly a notion of “$c$-approximate cut-dimension” using
strong LP duality. We show that this technique provides a lower bound on the
number of queries needed by a deterministic algorithm to find a
$c$-approximate max-cut for $c>1/2$, and that for the complete graph on $n$
vertices this gives a bound of $\Omega(n)$. This approach should also be of
independent interest, given recent interest in the exact cut dimension.
Completing this analysis also requires a technical lemma stating a simple
geometric property of the Boolean hypercube, which may additionally be of
independent interest.

Our $\tilde{O}(n)$-query randomized $c$-approximation for $c\in(1/2,1)$
follows from a query-efficient sparsifier for global cuts in undirected,
weighted graphs (once we have learned a sparsifier for the graph, we can just
exhaust to find its max-cut, which is a $(1-\varepsilon)$-approximation). A
query-efficient sparsifier for unweighted graphs appears in [RSW18]. We first
give a natural extension of their sparsifier that accommodates graphs with
weights in $[1,\operatorname{poly}(n)]$, and show that a slight modification
of this suffices for approximate max-cut for _all weighted graphs_ (however,
it may not produce a sparsifier; see Theorems 4.9 and 4.10 for further
details). We also go a step further and provide a novel query-efficient
sparsifier for all weighted graphs. This stronger sparsifier is not
“necessary” to resolve approximate max-cut, but is of independent interest as
not all weighted graph problems can be reduced to one with weights in
$[1,\operatorname{poly}(n)]$ (e.g. exact min-cut). In fact, our stronger
sparsifier is already used in recent work [MN20].666[MN20, Theorem 5.2] seems
to credit [RSW18] for handling weighted graphs (whereas their query-efficient
sparsifier only accommodates unweighted graphs).

###  1.3 Related work

Submodular function maximization. Our problem is a special case of symmetric
submodular function maximization, but the additional structure imposed by the
cut function of a graph opens up possibilities for new algorithms and requires
new lower bound arguments. For example, when $c>1/2$, [FMV11] show that
achieving a $c$-approximation to symmetric submodular function maximization
requires $\exp(\Omega(n))$ queries to the oracle. For global max-cut, the
situation is significantly different: $O(n^{2})$ queries suffice to trivially
learn the entire function (and therefore, there seems to be little hope of
embedding hard SFM instances as graphs). Still, we show that this trivial
algorithm is optimal among deterministic algorithms when $c=1$, and show that
$\tilde{\Omega}(n)$ queries are necessary for even a randomized algorithm to
achieve a $c$-approximation for $c>1/2$.

For $c\leq 1/2$, randomized [BFNS12] and deterministic [BF18] algorithms are
known that achieve a $1/2$-approximation with $O(n)$ and $O(n^{2})$ queries
respectively, even when the submodular function is not symmetric. [FMV11] show
in the symmetric case that picking a random set ($O(1)$ queries) achieves a
$1/2$-approximation in expectation. They also provide a deterministic
algorithm based on local search that achieves a $c$-approximation for any
$c<1/2$ in $\tilde{O}(n^{3})$ queries. When restricting to max-cut, [FMV11]
immediately implies a randomized algorithm for all $c\leq 1/2$ with $O(1)$
queries (which is optimal). For deterministic algorithms, however, our bound
of $\Theta(\log n)$ is again an exponential improvement over the general case
of submodular function maximization.

In summary, global max-cut demonstrates a similar phase transition at $c=1/2$
as general submodular function maximization: the query complexity for $c<1/2$
is exponentially smaller than the query complexity for $c>1/2$. However, the
distinction for max-cut is between logarithmic and polynomial queries, whereas
the distinction for general submodular functions is between polynomial and
exponential.

Max-cut in the classical computational model. Max-cut is extremely well-
studied in the computational model, but algorithms in the cut-query model
differ significantly. For example, [GW95] present a randomized polynomial-time
algorithm using semidefinite programming that achieves a $\approx 0.878$
approximation in expectation. However, this algorithm does not imply anything
in our model; even formulating the necessary SDP requires access to the entire
graph.

It has since been shown by [Hås01] that it is NP-hard to beat a $16/17\approx
0.941$ approximation. Moreover, [KKMO07] show that it is NP-hard to beat the
constant achieved by Goemans and Williamson assuming the unique games
conjecture [Kho02]. These lower bounds do not imply anything in our model
either. In fact, many of our algorithms (and those in prior work) involve
exponential computation even if they use an efficient number of queries. Once
we have either learned the entire graph ($c=1$) or constructed a sparsifier of
the graph ($c\in(1/2,1)$), we use brute force search to find the exact max cut
on the graph we have learned.

Graph sparsification. [RSW18] also provide an algorithm for graph
sparsification in $\tilde{O}(n)$ queries for unweighted graphs, based on the
idea of _edge strength-based sampling_ used by [BK15] to construct sparsifiers
in the classical computational model. There are also other lines of work that
adapt the ideas from [BK15] to construct sparsifiers in other limited-access
computational models, particularly (semi-)streaming [AGM12a, AGM12b, AGM13,
KLM+14, SWYZ19]. Some of these algorithms are adaptable to the cut-query
model. However, these algorithms either only support unweighted graphs or
incur a performance cost for weighted graphs. For example, the natural
extension of the algorithm in [RSW18] to weighted graphs requires
$\tilde{O}(n\log W)$ queries, where $W$ is the ratio between the largest and
smallest nonzero edge weight in the graph. Our novel sparsifier avoids this
pitfall by using results from [BK15] connecting edge strengths to maximum
spanning trees to remove the $\log W$ factor.

While these results and ours all use randomization to construct a sparsifier,
there are also classical algorithms for constructing sparsifiers
deterministically [BSS14]. Implementing such an algorithm directly would
require being able to learn the spectrum of the graph’s Laplacian. It may
indeed be possible to do this (exactly or approximately) in a query-efficient
way, but doing so would require significantly new ideas. A deterministic
query-efficient implementation of these algorithms would also yield a
deterministic query-efficient algorithm for a $(1-\epsilon)$-approximation to
max cut.

Graph algorithms in the cut query model. The first study of graph algorithms
in the cut query model known to the authors is that of [GK00], who study the
query complexity of learning the entire graph for various classes of graphs.
In particular, they show that the query complexity of deterministically
learning an unweighted graph is $\Theta(n^{2}/\log n)$, and that this can be
attained non-adaptively. Graph algorithms in the cut-query model has generally
attracted interest over the past few years (e.g. [RSW18, GPRW20, LSZ21,
LLSZ21, AEG+22]).

For the problem of global min-cut instead of max-cut, [RSW18] show that
$\tilde{O}(n)$ queries suffice, and [GPRW20] show using a linear algebraic
argument that $\Omega(n)$ queries are necessary (the constant-factors have
since been improved by [LLSZ21]), thus resolving the query complexity of exact
min-cut up to logarithmic factors. As mentioned earlier, our deterministic
lower bounds arise from adapting and extending the concept of the cut
dimension to approximation.

The cut dimension was introduced by [GPRW20], and further studied in [LLSZ21].
[LLSZ21] further nail down that undirected graphs have a min-cut dimension of
no more than $2n-3$ (and there exist graphs realizing this bound). They also
introduce the $\ell_{1}$-approximate cut dimension. The $\ell_{1}$-approximate
cut dimension is motivated by a similar thought experiment as our
“$c$-approximate cut dimension” technique — both consider an adversary
changing the original graph in a way that respects all queries made, and both
consider the magnitude of the changes made to the max/min-cut (rather than
just whether or not the cut is changed). However, their $\ell_{1}$-approximate
cut dimension does not imply lower bounds on the query complexity of finding
approximately-optimal cuts. Finally, they further consider “the dimension of
approximate min-cuts”, and prove a linear upper bound on this. This concept
does not have any relation to our approximate cut dimension technique (and in
particular, only our technique implies lower bounds on the deterministic query
complexity). In summary, the cut dimension is an active concept of study in
related work, but our work is the first to use this concept to lower bound the
query complexity of approximately-optimal cuts.

##  2 Preliminaries

$G$ is an undirected, weighted graph with weights $w_{i,j}$ on the edge
$(i,j)$. $G$ induces a cut function $F$. We denote the cut function by
$F(\cdot)$, so $F(S):=\sum_{i\in S,j\notin S}w_{i,j}$.

We consider algorithms that have black-box access to $F(\cdot)$, and aim to
find $\arg\max_{S\subseteq[n]}\\{F(S)\\}$ (exact maximization) or a set $T$
such that $F(T)\geq c\cdot\max_{S\subseteq[n]}\\{F(S)\\}$ ($c$-approximation).
We refer to the query complexity as the number of queries to $F(\cdot)$ that
the algorithm makes (the algorithm has no other access to $G$ or $F$, and may
perform unlimited computation).

##  3 Lower Bound Results

In Section 3.1, we adapt the linear algebraic cut dimension argument by
[GPRW20] to show the deterministic lower bound in Theorem 1.1. We then extend
this argument in Section 3.2 using linear programming and the strong duality
theorem to show the deterministic lower bound in Theorem 1.2. In Section 3.3,
we use an information theoretic argument to show the randomized lower bound in
Theorem 1.2. Finally, in Section 3.4, we construct a simple hard distribution
over graphs to show the deterministic and randomized lower bounds in Theorem
1.3.

###  3.1 Lower Bound for Exact Deterministic Algorithms

Here we address the deterministic hardness part of Theorem 1.1. The following
theorem shows that $\Omega(n^{2})$ queries are needed to deterministically
find the value of the max cut. Note that this lower bound relies on the fact
that the graph is weighted; [GK00] show that $O(n^{2}/\log n)$ queries are
necessary and sufficient to deterministically and non-adaptively learn an
unweighted graph.

######  Theorem 3.1.

Suppose $n\geq 3$. Then a deterministic algorithm that finds the value of the
max cut exactly requires at least $\binom{n}{2}$ queries when $n$ is odd, and
at least $\binom{n-1}{2}$ queries when $n$ is even.

This implies that the query complexity for a deterministic algorithm to
exactly solve global max-cut on a weighted undirected graph in the value
estimation setting is $\Omega(n^{2})$.

Our proof of this directly applies the linear algebraic _cut dimension_
technique developed by [GPRW20]. [GPRW20] use this technique to obtain query
lower bounds for exact min-cut in the cut query model, but we will see that it
works just as well for exact max-cut. We set up some notation. Let $E(G)$ be
the set of edges in $G$ with positive weight, then we can stack the nonzero
edge weights of $G$ into a vector $w\in\mathbb{R}^{|E(G)|}$. We still index
the coordinates in $\mathbb{R}^{|E(G)|}$ by pairs of vertices $i,j$. Now any
cut $S\subseteq[n]$, we have that:

$\displaystyle F(S)$ $\displaystyle=\sum_{i\in S}\sum_{j\in[n]\backslash
S}w_{i,j}$ $\displaystyle=\sum_{i,j}(v_{S})_{i,j}w_{i,j}$
$\displaystyle=w^{T}v_{S},$

where we define the indicator vector $v_{S}\in\mathbb{R}^{|E(G)|}$ by:

$\displaystyle(v_{S})_{i,j}$ $\displaystyle=\begin{cases}1,&(i,j)\text{
crosses the cut defined by }S,\\\ 0,&\text{ otherwise}.\end{cases}$

We call $v_{S}$ the _query vector_ corresponding to $S$. Note that we only
include entries for vertex pairs in $G$ that share an edge of positive weight.
With this language, we can intuitively summarize the cut dimension technique –
we refer the reader to Section 3 of [GPRW20] for a more comprehensive
explanation. Before any queries have been made, the graph’s weights can be
described by a vector $w\in\mathbb{R}^{|E(G)|}$ and thus exist in a subspace
of dimension $|E(G)|$. Each query made imposes one linear constraint on $w$,
so that if there are $q$ queries made, the algorithm only has the information
that $w$ exists in a subspace of dimension at least $|E(G)|-q$. The idea is to
show that this is still too many degrees of freedom for the algorithm to be
able to identify the max cut value exactly. We now make this precise by
defining the _max cut dimension_ :

######  Definition 3.2.

The _max cut dimension_ of a graph $G$ is equal to the dimension of the span
of:

$\left\\{v_{U}:U\in\operatorname{argmax}_{S\text{ a cut of }G}F(S)\right\\}.$

Call this span the _max cut space_ of the graph.

In other words, the max cut space is the span of the indicator vectors of all
max cuts, and the max cut dimension is the dimension of this span. We now show
that the max cut dimension of a graph provides a lower bound on the number of
queries needed:

######  Lemma 3.3.

[GPRW20] Suppose there exists a graph $G$ on $n$ vertices with max cut
dimension $d$. Then any deterministic algorithm that finds the value of the
max cut exactly must use at least $d$ queries.

(Note importantly that even if all edges in $G$ have weight 0 or 1, this lemma
still only yields a lower bound on deterministic max-cut for weighted graphs.
This is because the proof involves making small non-integer perturbations to
the edge weights of $G$.)

###### Proof.

See Appendix A.1. This exact result is not proven by [GPRW20] but they show
the analogous result for min cuts and the proof is exactly the same. ∎

We complete the proof of Theorem 3.1 by using Lemma 3.3 with the particular
case of $G=K_{n}$. The following lemma shows that $K_{n}$ has max cut
dimension corresponding to the lower bounds stated in the theorem:

######  Lemma 3.4.

Suppose $n\geq 3$, and let $G=K_{n}$ be the graph on $n$ vertices where all
pairs of distinct vertices share an edge of weight 1. (Thus
$|E(G)|=\binom{n}{2}$.) Then the max cut dimension of $G$ is $\binom{n}{2}$ if
$n$ is odd, and $\binom{n-1}{2}$ if $n$ is even.

###### Proof.

The idea is just that $K_{n}$ has exponentially many max cuts since any cut of
size $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$ is a max cut, so we can take
appropriate linear combinations of their indicator vectors to obtain a large
span. When $n$ is odd, we can obtain the indicator vector for any vertex pair
and thus the entire space, giving $\binom{n}{2}$. When $n$ is even, we don’t
quite get the entire space since all vertices have the same degree of $n/2$ in
a max cut and this imposes some linear constraints. Details are provided in
Appendix A.2. ∎

###  3.2 Lower Bound for Deterministic $(1/2+\epsilon)$-approximation

We now extend the cut dimension technique to show the deterministic hardness
part of Theorem 1.2. Our exact result is as follows:

######  Theorem 3.5.

Suppose we have $c\in(1/2,1),\epsilon\in(0,1),\alpha>0$ such that
$c>\frac{1}{1+\epsilon^{2}}$ and
$\alpha<\frac{(1-\epsilon)^{3}}{108(1+\epsilon)}$. Then for $n$ sufficiently
large, $\alpha n$ queries do not suffice for a deterministic algorithm to
estimate the max cut value within a factor of $c$.

Before proving this theorem, we state a cleaner lower bound as a corollary:

######  Corollary 3.6.

For $c\in(1/2,1)$, a deterministic algorithm that estimates the max cut value
within a factor of $c$ requires at least
$n(\frac{(\sqrt{c}-\sqrt{1-c})^{4}}{108c(2c-1)}-o(1))$ queries.

This implies that the query complexity for a deterministic algorithm to
achieve a $c$-approximation for global max-cut on a weighted undirected graph
in the value estimation setting is $\Omega(n)$.

###### Proof.

See Appendix B.1. ∎

The first step is conceptually similar to that of Theorem 3.1. We consider an
adversary that answers all queries as if the graph were $K_{n}$ (there is an
edge of weight 1 between all pairs of vertices). Then we would like to find a
perturbation $z$ to the weight vector of $K_{n}$ such that $w,w+z$ agree on
all queries but have differing max cut values. The difference here is that we
would like to show that the algorithm cannot even achieve a $c$-approximation,
so we require the perturbation to be so large that the max cut value of $w+z$
is a multiplicative factor greater than the max cut of $w$. To do this, we
will have to go beyond linear algebraic tools and consider linear programming
instead. Our argument comprises the following steps:

  1. 1.

Write the conditions we require of the perturbation $z$ as linear constraints
and thus formulate a linear program LP1, which we would like to show has high
value.

  2. 2.

LP1 works with vectors in $\mathbb{R}^{\binom{n}{2}}$ that represent cuts,
which are unwieldy and unnatural. Rewrite this in terms of indicator vectors
in $\mathbb{R}^{n}$.

  3. 3.

Define another linear program LP2 and show that a high value for LP2 implies
that LP1 must also have high value.

  4. 4.

Show that LP2 has high value by taking its dual, and showing that the dual has
high value. This comes down to showing a key technical lemma, which
essentially states that the $n$-dimensional hypercube cannot be covered by an
$\ell_{1}$ neighborhood of an $\alpha n$-dimensional subspace of
$\mathbb{R}^{n}$. We show this using an $\ell_{1}$ $\epsilon$-net argument.

We now work through each step in detail. We retain all notation used in
Section 3.1 and Appendix A for the cut dimension argument, and introduce
additional notation as necessary.

####  3.2.1 Step 1: Formulating LP1

Throughout these proofs, we use $\mathbf{1}$ to denote a vector with all
entries equal to 1 in either $\mathbb{R}^{n}$ or $\mathbb{R}^{\binom{n}{2}}$.
It will be clear from context which of these we are referring to at any given
time, but for now we are taking $\mathbf{1}\in\mathbb{R}^{\binom{n}{2}}$ to
denote the weight vector of $K_{n}$. Let $q=\alpha n$ and
$Q_{1},Q_{2},\ldots,Q_{q}\subseteq[n]$ be the $q$ queried cuts. As in Section
3.1, they have the corresponding 0/1 indicator vectors
$v_{Q_{1}},v_{Q_{2}},\ldots,v_{Q_{q}}\in\mathbb{R}^{\binom{n}{2}}$. We are
interested in finding a perturbation $z$ such that $\mathbf{1},\mathbf{1}+z$
are both weighted, undirected graphs (with non-negative edge weights) and
agree on all queries but have max cut values differing by a multiplicative
factor.

First, we require $\mathbf{1}+z$ to define a valid graph i.e. its entries
should all be non-negative since these correspond to edge weights:

$\displaystyle\mathbf{1}+z\geq 0$ $\displaystyle\Leftrightarrow
z\geq-\mathbf{1}.$ (1)

Next, we need $\mathbf{1},\mathbf{1}+z$ to agree on all queries. This
guarantees that the algorithm cannot tell the difference between $\mathbf{1}$
and $\mathbf{1}+z$ based only on the queries made so far.

$\displaystyle\mathbf{1}^{T}v_{Q_{i}}=(\mathbf{1}+z)^{T}v_{Q_{i}},\ \forall i$
$\displaystyle\Leftrightarrow z^{T}v_{Q_{i}}=0,\ \forall i.$ (2)

Finally, we would like the graph corresponding to $\mathbf{1}+z$ to have a
much larger max cut value than the graph corresponding to $\mathbf{1}$. We
capture this in the following definition and lemma:

######  Definition 3.7.

Define a _near-max cut_ to be any cut $C\subseteq[n]$ such that
$n/2-\sqrt{n\log n}\leq|C|\leq n/2+\sqrt{n\log n}$.

Note that a near-max cut is nearly a max-cut in $K_{n}$. As hinted at earlier,
we will show that we can find a near-max cut $C$ and a perturbation $z$ to the
graph that will preserve the value of all queries while blowing up the value
of $C$ by a factor of $c$. In this case, the algorithm cannot distinguish
between $K_{n}$ and the perturbed graph and thus cannot achieve a
$c$-approximation.

######  Lemma 3.8.

To prove Theorem 3.5, it suffices to show that there exists a near-max cut $C$
such that following linear program has value at least $\epsilon^{2}n^{2}/4$.
We call this linear program LP1.

Maximize $\displaystyle z^{T}v_{C}$ subject to $\displaystyle
z^{T}v_{Q_{j}}=0\quad\text{ for all }j\in[q],\text{ and }$ $\displaystyle
z\geq-\mathbf{1}.$

###### Proof.

We have already explained how the constraints arise. To justify that the
objective corresponds to a bound on the approximation ratio, see Appendix B.2.
∎

####  3.2.2 Step 2: Rewriting LP1

As already mentioned, the vectors $v_{S}\in\mathbb{R}^{\binom{n}{2}}$ are
unnatural and difficult to work with. Intuitively, the reason for this is that
a cut only has $n$ degrees of freedom (each vertex can be included or not
included in $S$), but we are representing it with a vector with $\binom{n}{2}$
entries, thereby creating unwanted dependencies between entries of these
vectors.

We would thus like to find a more natural parametrization of these cuts that
can still be connected naturally to the vectors $v_{S}$. To construct such a
parametrization, we assign to each cut $S$ a $\pm 1$ indicator vector
$u_{S}\in\mathbb{R}^{n}$. Entries are indexed by vertices in $[n]$, and for
each $i\in[n]$ we have:

$\displaystyle(u_{S})_{i}$ $\displaystyle=\begin{cases}1,&i\in S,\\\
-1,&\text{ otherwise}.\end{cases}$

Now we connect these new indicator vectors to $v_{S}$ as follows. Define the
matrix $M_{S}\in\mathbb{R}^{n\times n}$ by
$M_{S}=\frac{\mathbf{1}\mathbf{1}^{T}-u_{S}u_{S}^{T}}{2}$. (Note that from
here onwards, $\mathbf{1}$ now refers to the vector in $\mathbb{R}^{n}$ with
all entries equal to 1.) $M_{S}$’s entries are indexed by ordered pairs of
vertices. Now observe that:

$\displaystyle(M_{S})_{i,j}$
$\displaystyle=\frac{\mathbf{1}_{i}\mathbf{1}_{j}-(u_{S})_{i}(u_{S})_{j}}{2}$
$\displaystyle=\frac{1-(u_{S})_{i}(u_{S})_{j}}{2}$
$\displaystyle=\begin{cases}0,&i,j\in S\text{ or }i,j\notin S,\\\ 1,&\text{
otherwise}\end{cases}$ $\displaystyle=\begin{cases}(v_{S})_{i,j},&i\neq j,\\\
0,&i=j.\end{cases}$

Thus if we flatten $M_{S}$ into a vector, it consists of two copies of $v_{S}$
(each unordered vertex pair $(i,j)$ in $v_{S}$ appears twice in $M_{S}$ since
the vertex pairs indexing $M_{S}$ are ordered) and $n$ 0’s (corresponding to
vertex pairs $(i,i)$ for $i\in[n]$). This allows us to rewrite LP1 in terms of
the $u_{S}$’s as stated in the following lemma. For matrices $A,B$ of the same
shape, we use $\langle A,B\rangle$ to denote the matrix inner product
$\operatorname{tr}(A^{T}B)=\sum_{i,j}A_{i,j}B_{i,j}$.

######  Lemma 3.9.

For any $C$, LP1 has value $\geq\epsilon^{2}n^{2}/4$ if and only if the
following LP has value at $\geq\epsilon^{2}n^{2}/2$. We call this the “matrix
LP”. Here, $Z\in\mathbb{R}^{n\times n}$.

Maximize $\displaystyle\langle Z,M_{C}\rangle$ subject to
$\displaystyle\langle Z,M_{Q_{j}}\rangle=0\quad\text{ for all }j\in[q],\text{
and }$ $\displaystyle Z\geq-\mathbf{1}.$

###### Proof.

See Appendix B.3. ∎

####  3.2.3 Step 3: Defining LP2 and Connecting LP2 to LP1

For a near-max cut $C$, define a new linear program which we call LP2 as
follows. Here $y\in\mathbb{R}^{n}$.

Maximize $\displaystyle y^{T}u_{C}$ subject to $\displaystyle
y^{T}u_{Q_{j}}=0\quad\text{ for all }j\in[q],$ $\displaystyle
y^{T}\mathbf{1}=0,\text{ and }$ $\displaystyle-\mathbf{1}\leq
y\leq\mathbf{1}.$

We claim that it suffices to show that LP2 has value at least $\epsilon n$:

######  Lemma 3.10.

If there exists a near-max cut $C$ such that LP2 has value at least $\epsilon
n$ then the matrix LP for $C$ has value at least $\epsilon^{2}n^{2}/2$, which
would imply Theorem 3.5.

###### Proof Sketch.

Take such a near-max cut $C$ and $y\in\mathbb{R}^{n}$ such that $y$ is in the
feasible region of LP2 and $y^{T}u_{C}\geq\epsilon n$. Then we claim that
$Z=-yy^{T}$ is feasible for the matrix LP and attains a value
$\geq\epsilon^{2}n^{2}/2$. Intuitively, $y$ can be thought of as a vector
representing a “pseudo-cut” in the same way that $u_{S}$ represents $S$. LP2
having high value means that $y$ aligns non-trivially with $C$, and what we
are claiming is that perturbing towards the “pseudo-cut” corresponding to $y$
will align the graph’s weights with the cut corresponding to $C$. We provide
details in Appendix B.4. ∎

####  3.2.4 Step 4: Showing that LP2 has High Value

Finally, we show that we can find a near-max cut $C$ such that LP2 has value
at least $\epsilon n$, which by Lemma 3.10 will complete the proof of Theorem
3.5. We do this by taking the dual of LP2, which has a simple characterization
captured by the following lemma:

######  Lemma 3.11.

Consider vectors $w,w_{1},w_{2},\ldots,w_{k}\in\mathbb{R}^{d}$, and the
following LP:

Maximize $\displaystyle z^{T}w$ subject to $\displaystyle
z^{T}w_{i}=0\quad\text{ for all }i\in[k],\text{ and }$
$\displaystyle-\mathbf{1}\leq z\leq\mathbf{1}.$

Let $W=\operatorname{span}(w_{1},w_{2},\ldots,w_{k})$. Then the value of this
LP is $\min_{v\in W}||v-w||_{1}$. (If there is no such $v$ then by this
minimum we mean $\infty$.)

###### Proof.

See Appendix B.5. ∎

To use this lemma, let
$V=\operatorname{span}(u_{Q_{1}},\ldots,u_{Q_{q}},\mathbf{1})$. Then Lemma
3.11 tells us that LP2 has value equal to $\min_{u\in V}||u-u_{C}||_{1}$.

Now note that $V$ depends only on the set of queries and not at all on $C$.
Thus we would like to show that there exists a near-max cut $C$ such that
$\min_{u\in V}||u-u_{C}||_{1}\geq\epsilon n$. We will show the strict version
of this inequality i.e. that $\min_{u\in V}||u-u_{C}||_{1}>\epsilon n$. Denote
by $B_{r}$ the $\ell_{1}$ ball of radius $r$ in $\mathbb{R}^{n}$. Then what we
want to show is that there exists a near-max cut $C$ such that $u_{C}\notin
V+B_{\epsilon n}$. This brings us to our key technical lemma, which has little
to do with graphs and may be of independent interest:

######  Lemma 3.12.

Let $\epsilon\in(0,1)$ and $d\leq\alpha^{\prime}n$ for
$\alpha^{\prime}<\frac{(1-\epsilon)^{3}}{108(1+\epsilon)}$. Suppose $D$ is a
$d$-dimensional subspace of $\mathbb{R}^{n}$. Denote by $B_{r}$ the $\ell_{1}$
ball of radius $r$ in $\mathbb{R}^{n}$. Then there exists
$p\in\left\\{-1,1\right\\}^{n}$ such that $p\notin D+B_{\epsilon n}$ and
$|\mathbf{1}^{T}p|\leq 2\sqrt{n\log n}$.

###### Proof.

We show this by a volume argument. Specifically, we estimate the size of
$(D+B_{\epsilon n})\cap\left\\{-1,1\right\\}^{n}$ using an $\ell_{1}$
$\epsilon$-net argument and show that this must be much less than $2^{n}$. We
provide details in Appendix B.6. ∎

With this lemma, we can complete this step and thus the proof of Theorem 3.5:

######  Corollary 3.13.

For $n$ sufficiently large, there exists a near-max cut $C$ such that
$u_{C}\notin V+B_{\epsilon n}$.

###### Proof.

See Appendix B.7. ∎

###  3.3 Lower Bound for randomized $(1/2+\epsilon)$-approximation

We now prove a lower bound for randomized algorithms that achieve a
$c$-approximation for $c>1/2$. This differs from the deterministic lower bound
just presented in two ways: first, the query complexity shown is
$\Omega(n/\log n)$ rather than $\Omega(n)$, and secondly, this lower bound
argument only works for the cut finding setting.

######  Theorem 3.14.

For $c>1/2$, a randomized algorithm that finds a $c$-approximate max cut with
constant probability $p>0$ requires at least $\frac{n}{\log
n}(\frac{p(2c-1)}{16c+72}-o(1))$ queries.

This implies that the query complexity for a randomized algorithm to achieve a
$c$-approximation with $\Omega(1)$ probability for global max-cut on an
unweighted (or weighted) undirected graph in the cut finding setting is
$\Omega(n/\log n)$.

###### Proof.

It suffices to show for any $\epsilon>0$ satisfying
$\epsilon^{2}<\frac{2c-1}{8c+36}$ that at least $\frac{n}{\log
n}(\frac{p\epsilon^{2}}{2}-o(1))$ queries are necessary.

The following is our hard distribution: let $A$ be a uniformly random subset
of $[n]$ then take the complete bipartite graph on $(A,[n]\backslash A)$ with
all edge weights 1. The intuition is that in order to find a $c$-approximate
max cut, the algorithm must learn $\Omega(n)$ bits of information about $A$.
Since it only receives $O(\log n)$ bits of information per query, this will
yield the desired lower bound. We make this rigorous with an information
theoretic argument.

Denote by $E(A)$ the set of edges included in this graph, for any set $A$. By
Yao’s minimax principle, it suffices to show the lower bound for a
deterministic algorithm against this distribution. Moreover, this lower bound
will hold even if we restrict attention to unweighted graphs, since all graphs
in our hard distribution are unweighted (all their edge weights are 0 or 1).
Suppose the algorithm uses $q$ queries. The key lemma is as follows:

######  Lemma 3.15.

Let $B$ be any subset of $[n]$ and $A$ a uniformly random subset of $[n]$.
Then we have:

$\Pr[\frac{|E(A)\cap E(B)|}{|E(A)|}\geq c]\leq 4\exp(-\epsilon^{2}n)$

.

where the randomness is over $A$.

###### Proof.

This essentially follows from the fact that $|A|$ concentrates around $n/2$
and $|A\cap B|$ concentrates around $|B|/2$ provided $B$ is reasonably large
(we can assume $|B|\geq n/2$ w.l.o.g since $E(B)=E(\overline{B})$). We provide
details in Appendix C.1. ∎

######  Corollary 3.16.

The number of subsets $A$ of $[n]$ satisfying $|E(A)\cap E(B)|\geq c|E(A)|$ is
at most $2^{n}\cdot 4\exp(-\epsilon^{2}n)$.

So suppose that the lemma holds true. We prove the theorem with an information
theoretic argument. Specifically, it is clear that the random variable $A$ has
entropy $H(A)=n$. Informally, we will show that:

  1. 1.

each query only gives the algorithm a small amount of information, and

  2. 2.

achieving a $c$-approximation with probability $p$ requires the algorithm to
learn a linear amount of information,

which will give us a query lower bound. We provide remaining details in
Appendix C.2. ∎

###  3.4 Lower Bounds for $\epsilon$-approximation

Here we show the deterministic lower bound part of Theorem 1.3, and also show
that at least $\lg(1/p)$ queries are necessary for randomized
$\epsilon$-approximation with probability $\geq 1-p$. Both these results are
captured by the following theorem:

######  Theorem 3.17.

For any $c\in(0,1/2)$, any randomized algorithm using at most $q$ queries will
achieve a $c$-approximation (even in the value estimation setting) with
probability at most $1-\frac{n-2^{q}}{2^{q+1}(n-1)}$.

###### Proof.

We construct a hard distribution of instances. It comprises the following:

  * •

With probability $1/2$: the empty graph (i.e. all edges have weight 0).

  * •

For each edge $(i,j)$ in the graph, with probability $\frac{1}{n(n-1)}$: the
graph $G_{i,j}$ where all edges have weight 0 except for $(i,j)$ which has
weight 1.

Note that we can alternately characterize this distribution as follows: we
choose an edge $(i,j)$ uniformly at random. Then all edges other than $(i,j)$
are set to 0, and $(i,j)$ is set to 1 with probability $1/2$. By Yao’s minimax
principle, it suffices to show that a deterministic algorithm succeeds on a
graph from this distribution with probability at most
$1-\frac{n-2^{q}}{2^{q+1}(n-1)}$. The following is the key lemma:

######  Lemma 3.18.

Let $Q_{1},Q_{2},\ldots,Q_{q}$ be any $q$ cuts. Then with probability at least
$\frac{n-2^{q}}{2^{q}(n-1)}$, none of these cuts will be crossed by the chosen
edge $(i,j)$.

###### Proof.

See Appendix D.1. ∎

Given this lemma, our argument is simple: let $Q_{1},\ldots,Q_{q}$ be the cuts
the algorithm will query if it always receives 0 as an answer from the oracle
(this sequence is fixed and independent of the chosen edge $(i,j)$ since we
are now considering a deterministic algorithm). By the lemma, we have that
with probability at least $\frac{n-2^{q}}{2^{q}(n-1)}$, none of these cuts
will be crossed by the chosen edge $(i,j)$. If this is the case, the algorithm
will always receive 0 as an answer and thus follow this exact sequence of
queries. Moreover, at the end, the algorithm has absolutely no information on
the weight of that edge so it cannot distinguish between the two different
scenarios. In one case the max cut value is 0 and in the other case the max
cut value is 1 so no answer can cover both cases, so the algorithm fails with
probability at least $1/2$. Hence the algorithm’s overall probability of
failure is at least $\frac{n-2^{q}}{2^{q+1}(n-1)}$ which proves the theorem. ∎

Our lower bounds arise as natural corollaries of this theorem:

######  Corollary 3.19.

A deterministic algorithm that achieves a $c$-approximation for any $c>0$
requires at least $\lg n$ queries.

This implies that the query complexity for a deterministic algorithm to
achieve a $c$-approximation for global max-cut on an unweighted (or weighted)
undirected graph in the value estimation setting is $\Omega(\log n)$.

###### Proof.

See Appendix D.2. ∎

######  Corollary 3.20.

For $p>0$, a randomized algorithm that achieves a $c$-approximation in the
value-estimation setting with probability at least $1-p$ for any $c>0$
requires at least $\lg(1/p)-1-o(1)$ queries.

###### Proof.

See Appendix D.3. ∎

Note that this implies that the upper bound given for randomized algorithms in
Corollary 5.2 is tight in terms of its dependence on the failure probability
$p$, although there is a gap in terms of the dependence on $c$.

##  4 Sparsifier-based Randomized Algorithms for $(1-\epsilon)$-approximation

Here we address the randomized upper bound part of Theorem 1.2, namely that a
$(1-\epsilon)$-approximation can be achieved in the cut finding setting with
$\tilde{O}(n)$ queries. Our algorithms are adaptive. The key notion is that of
a _sparsifier_ :

######  Definition 4.1.

Given weighted graphs $G,H$ on the same set of $n$ vertices with non-negative
weights, we say $H$ is an $\epsilon$-sparsifier of $G$ if all of the following
conditions hold:

  1. 1.

$H$ has $\tilde{O}_{\epsilon}(n)$ edges with nonzero weight.

  2. 2.

For any cut $S\subseteq[n]$, we have $(1-\epsilon)F(S;G)\leq
F(S;H)\leq(1+\epsilon)F(S;G)$.

Here $F(S;G)$ denotes the value of the cut defined by $S$ on the graph $G$,
and similarly for $F(S;H)$.

######  Lemma 4.2.

If an algorithm can compute an $\epsilon$-sparsifier of $G$ in
$\tilde{O}(n/\epsilon^{2})$ queries with high probability, then it can also
find a $(1-2\epsilon)$-approximate max cut with no additional queries.

###### Proof.

Once the algorithm has a sparsifier $H$, it can just try all possible cuts and
output the cut $U$ maximizing $F(U;H)$. Indeed, for any other cut $S$, we
would have
$F(U;G)\geq\frac{F(U;H)}{1+\epsilon}\geq\frac{F(S;H)}{1+\epsilon}\geq\frac{(1-\epsilon)F(S;G)}{1+\epsilon}\geq(1-2\epsilon)F(S;G)$,
so $U$ is indeed a $(1-\epsilon)$-approximate max cut. ∎

Throughout this section, let $d>5$ be constant, and let $\delta\in(1/2,1)$ be
a constant sufficiently close to 1. Then let $c_{0}$ and $c_{1}$ be
sufficiently large positive constants. Also, let $W_{\text{tot}}$ be the total
weight of all edges in the graph, and $W$ the ratio between the largest and
smallest nonzero edge weights. Finally, for a vertex set $S\subseteq V(G)$,
let $G[S]$ denote the vertex-induced subgraph of $G$ on $S$. Note that we do
not require that $G$ be connected. We organize the remainder of this section
as follows:

  1. 1.

In Section 4.1, we set up and analyze the algorithmic tools necessary to adapt
[RSW18]’s algorithm to weighted graphs.

  2. 2.

In Section 4.2, we present the direct adaptation of [RSW18]’s algorithm to
weighted graphs and show that it constructs a sparsifier in
$\widetilde{O}(n\log W)$ queries.

  3. 3.

In Section 4.3, we show that we can achieve a $(1-\epsilon)$-approximation for
max-cut in $\widetilde{O}(n)$ queries by essentially stopping our adaptation
of [RSW18]’s algorithm early. This will not construct a sparsifier, but it
will construct something “close enough” to suffice for max-cut. Intuitively,
we do this by discarding edges of weight $<W_{\text{tot}}/\text{poly}(n)$
since these will not have much effect on the max cut, thereby reducing the
problem to one where $W=\text{poly}(n)$.

  4. 4.

Finally, in Section 4.4, we use ideas introduced by [BK15] relating edge
strengths to maximum spanning trees in order to construct a sparsifier for
weighted graphs in $\widetilde{O}(n)$ queries. Given the results from Section
4.3, this is not necessary for max-cut specifically, but it will make for a
conceptually cleaner algorithm for max-cut and may be applicable to other
problems.

###  4.1 Setup and Algorithmic Tools

The key idea is the notion of edge strength introduced by [BK15].

######  Definition 4.3.

([BK15], as stated in [RSW18]) The _strong connectivity_ of $G$, denoted
$K(G)$, is the value of $G$’s min cut.

######  Definition 4.4.

([BK15], as stated in [RSW18]) Given an edge $e$ in $G$, the strong
connectivity or _edge strength_ $k_{e}$ of $e$ is the maximum min cut over all
vertex-induced subgraphs of $G$ containing $e$:

$k_{e}=\max_{S\subseteq V:u,v\in S}K(G[S]).$

The idea introduced by [BK15] and used by [RSW18] is that subsampling edges of
$G$ with probabilities inversely proportional to their strength will give a
sparsifier. We cannot do exactly this in the cut query model, but we can
subsample in a way that is “close enough” to independent. We need some basic
primitives to support our algorithm, and we capture all of them in the
following lemma:

######  Lemma 4.5.

There exists a data structure supporting the following operations.

  1. 1.

$\text{InitializeDS}(H)$: Initialize the structure’s state and carry out any
preprocessing needed with the starting graph $H$.

  2. 2.

$\text{Contract}(S)$: Contract a given supernode set $S$.

  3. 3.

$\text{GetEdge}()$: Find and return an edge from $H$ (that has not been
contracted) with weight at least $\frac{2W(H)}{n^{2}}$. Here $W(H)$ is the
total weight of not-yet-contracted edges.

  4. 4.

$\text{GetTotalWeight}(S)$: Return the total weight of all edges with both
endpoints in $S$ (that have not yet been contracted). $S$ must once again be a
set of supernodes.

  5. 5.

$\text{Sample}(S)$: Sample a random edge with both endpoints in $S$ (that has
not yet been contracted), with probability proportional to its weight. $S$
must be a set of supernodes here as well.

It takes $O(n)$ queries for each call to InitializeDS, $O(1)$ queries for each
call to Contract, $O(\log n)$ queries for each call to GetEdge, $O(1)$ queries
for each call to GetTotalWeight, and $O(\log n)$ queries for each call to
Sample.

###### Proof.

The pre-processing and queries when contracting are due to having to keep
track of (super)node degrees. GetEdge and Sample can be handled using
recursive bisection procedures similar to that used to prove Corollary 2.2 in
[RSW18]. We provide details in Appendix E.1. ∎

Before we go any further, we make an important comment about how we regard
contraction in our algorithms (including Lemma 4.5). When we contract a set of
vertices, we regard that set of vertices as one supernode as usual, but we do
not merge any edges that have now become parallel. So the set of edges will
always be a subset of the edges from the original graph.

It will be convenient to regard our algorithms as having two separate stages,
although the two stages share some ingredients. In the first stage, the
algorithm iteratively subsamples and contracts the graph to estimate the
strengths of ell edges within a constant factor. In the second stage, the
algorithm uses these edge strength estimates to construct the sparsifier,
following the ideas of [BK15]. We address these two stages in the next two
subsections respectively.

We note that these algorithms are very similar to those presented by [RSW18];
the key difference is that whenever the sparsification algorithm in [RSW18]
subsamples the graph, it does so independently for each edge. This works
because [RSW18] focuses on unweighted graphs. With weighted graphs, we would
like to sample edges proportionately to their weight, and this cannot be done
independently without knowledge of the graph. We modify their subsampling
procedures to obtain algorithms that do not sample completely independently,
but still have the concentration properties that we need.

####  4.1.1 Constant-Factor Edge Strength Estimates

We next describe the main tool of our edge strength estimation, which we call
EstimateAndContract. It takes in the input graph $G$ where some vertex sets
$S_{i}$ have already been contracted and a strength parameter $\kappa$, and
further contracts $G$ while also estimating the strength of any edges that get
contracted. For any graph $H$, let $W(H)$ denote the total edge weight of $H$.

Data: Initial graph $G$ with vertex set $V(G)\subseteq[n]$, disjoint
collection $\mathcal{C}$ of contracted sets, strength parameter $\kappa$,
partial list $X$ of strength estimates

Result: Updated collection of contracted sets $\mathcal{C}$, updated list $X$
of strength estimates

Let $G^{\prime}$ be $G$ with all sets from $\mathcal{C}$ contracted and
$\lambda=\frac{c_{0}\log^{2}n}{\kappa}W(G^{\prime})$. (We can find
$W(G^{\prime})$ using GetTotalWeight from Lemma 4.5.)

  1. 1.

Sample $\lambda$ edges from $G^{\prime}$, proportionally to their weights,
with replacement. If an edge $e$ is sampled at least once, assign weight
$\frac{w(e)}{p(e)}$ to it, where
$p(e)=1-(1-\frac{w_{e}}{W(G^{\prime})})^{\lambda}$. These newly weighted edges
form a new graph $G^{\prime\prime}$.

  2. 2.

While there exists a connected component of $G^{\prime\prime}$ with a cut of
size $\leq(1-\delta)\kappa$, delete all edges of that cut from
$G^{\prime\prime}$. Let the resulting connected components of
$G^{\prime\prime}$ be $C_{1},C_{2},\ldots,C_{r}$.

  3. 3.

For each $i\in[r]$, append the tuple $(C_{i},\kappa/2)$ to $X$. (Here, what we
are saying is “assign a strength estimate of $\kappa/2$ to any edge with both
endpoints in $C_{i}$ that has not already been contracted”, but we phrase it
differently to account for the fact that the algorithm may not actually know
these edges.)

  4. 4.

Add $C_{i}$ to $\mathcal{C}$ (and remove any subsets of $C_{i}$ to maintain
disjointness) for all $i\in[r]$.

Algorithm 4.1 $\text{EstimateAndContract}(G,\mathcal{C},\kappa,X)$

We state some key properties of Algorithm 4.1 and defer their proofs to
Appendix E.4:

######  Lemma 4.6.

(Analogous to claim 3.6 from [RSW18]) With probability $1-O(n^{1-d})$, for all
$e$ such that $k_{e}\geq\kappa$ and $e$ is not contracted by any of the sets
in $\mathcal{C}$, it will be assigned $k^{\prime}_{e}=\kappa/2$ and
contracted.

######  Lemma 4.7.

(Analogous to claim 3.7 from [RSW18]) Assume that any edge contracted by
$\mathcal{C}$ has strength $\geq\kappa/2$. Then with probability
$1-O(n^{1-d})$, no edge $e$ such that $k_{e}<\kappa/2$ is assigned a strength
estimate or contracted.

####  4.1.2 Sparsifier Construction

Next, we describe our algorithm that will construct a sparsifier if provided
constant-factor strength estimates for all edges in the graph, which we call
ConstructSparsifier.

Data: Graph $G$ with vertex set $[n]$, list
$X=[(C_{1},\beta_{1}),(C_{2},\beta_{2}),\ldots,(C_{r},\beta_{r})]$ of strength
estimates. We assume that $\left\\{C_{1},\ldots,C_{r}\right\\}$ is a laminar
family of vertex sets and that if $C_{i}\subset C_{j}$ then $i<j$. (This is
because we will be contracting $C_{1},\ldots,C_{r}$ in that order.) Note that
we do not assume here that $X$ includes a strength estimate for every edge.

Result: Potential sparsifier $H$

Initialize $G^{\prime}=G$ and $H$ to be empty.

$\text{InitializeDS}(G^{\prime})$. (This is just to reset and ignore any
previous contractions we may have done in EstimateAndContract.)

for  _$i\leftarrow 1$ to $r$_ do

  1. 1.

Let $\mu_{i}=\frac{c_{1}\log^{2}n}{\epsilon^{2}\beta_{i}}W(C_{i})$. (Here
$W()$ is with respect to $G^{\prime}$, and once again can be found using
GetTotalWeight from Lemma 4.5.)

  2. 2.

Sample $\mu_{i}$ edges from $C_{i}$ proportionally to their weights, with
replacement. If an edge $e$ is sampled at least once, add it to $H$ with
weight $\frac{w_{e}}{p_{e}}$, where
$p_{e}=1-(1-\frac{w_{e}}{W(C_{i})})^{\mu_{i}}$ is the probability that $e$ is
sampled at least once. (Note that this sampling would be done by calling
$\text{Sample}(C_{i})$ from Lemma 4.5.)

  3. 3.

Contract $C_{i}$ in $G^{\prime}$.

end for

Algorithm 4.2 $\text{ConstructSparsifier}(G,X)$

We capture the desired sparsification properties in the following lemma:

######  Lemma 4.8.

Fix $X=[(C_{1},\beta_{1}),(C_{2},\beta_{2}),\ldots,(C_{r},\beta_{r})]$ as in
ConstructSparsifier ($X$ might be random, but we condition on a particular
list of values for now). Then for each $i$, define:

$\displaystyle E(C_{i})$ $\displaystyle=\left\\{e\in G:\text{ both endpoints
of $e$ are in $C_{i}$}\right\\}$ $\displaystyle\widetilde{E}(C_{i})$
$\displaystyle=E(C_{i})\backslash\bigcup_{j:C_{j}\subset C_{i}}E(C_{j})$

(Thus $\widetilde{E}(C_{i})$ is the set of edges that will be contracted at
the time that $C_{i}$ is contracted.)

Assume each of the following conditions:

  1. 1.

Each connected component of $G$ is contained in at least one $C_{i}$ (every
edge in $G$ gets contracted), and

  2. 2.

For all $i$ and edges $e\in\widetilde{E}(C_{i})$, we have
$\beta_{i}\in[k_{e}/4,k_{e}]$ (edge strength estimates are correct within a
constant factor).

Then with probability $1-O(n^{-d})$, ConstructSparsifier will output a
sparsifier $H$ that approximates the cuts of $G$ within a factor of $1\pm
2\epsilon$. (Thus this probability is only considering the randomness of
ConstructSparsifier.)

###### Proof.

This follows using similar ideas to [BK15], but we need to take some extra
care because the subsampling we use to construct the sparsifier is not
independent. We provide details in Appendix E.2.2. ∎

###  4.2 Sparsification with $\widetilde{O}(n\log W)$ Queries

Here we analyze the naive generalization of [RSW18]’s sparsifier to weighted
graphs. The procedure is described in Algorithm 4.3.

Data: Graph $G$ on $n$ vertices, positive real parameter $T$

Result: A potential $(2\epsilon)$-sparsifier $H$ of $G$.

Initialize $\mathcal{C}=\emptyset$ and $X$ as an empty list.

$\text{InitializeDS}(G)$.

Find $W_{\text{tot}}$ by running $\text{GetTotalWeight}(G)$.

Initialize $\kappa$ to be the smallest power of 2 that is at least
$W_{\text{tot}}$.

while  _$\text{GetTotalWeight}(G) >0$ and $\kappa>W_{\text{tot}}/T$_ do

$\text{EstimateAndContract}(G,\mathcal{C},\kappa,X)$

$\kappa\leftarrow\kappa/2$

end while

$H\leftarrow\text{ConstructSparsifier}(G,X).$

Algorithm 4.3 $\text{NaiveWeightedSubsample}(G,T)$

######  Theorem 4.9.

$\text{NaiveWeightedSubsample}(G,\infty)$ runs in $O(n\log^{3}n(\log n+\log
W+\frac{1}{\epsilon^{2}}))$ queries and outputs a $(2\epsilon)$-sparsifier $H$
with probability $1-O(n^{1-d}(\log n+\log W))$.

###### Proof.

We outline the proof here and provide details in Appendices E.5 (correctness)
and E.8 (efficiency). The proof proceeds in two parts.

First, we address the calls to EstimateAndContract. Given Lemmas 4.6 and 4.7,
EstimateAndContract can be thought of as estimating the strengths of and then
contracting edges whose strengths are within a window that is a factor of 4
wide. The lemmas tell us that these strength estimates are accurate within a
factor of 4. Then NaiveWeightedSubsample essentially “slides” this window
across all possible edge strengths so that all edges of $G$ are assigned a
strength estimate. This part has query complexity $O(n\log^{3}n(\log n+\log
W))$; the $\log W$ term is because the outer loop could run for $O(\log n+\log
W)$ iterations. This is also why the success probability depends on $W$, as
this is obtained by taking a union bound over all iterations.

Secondly, because all edges are assigned an accurate strength estimate (within
a constant factor), Lemma 4.8 tells us that ConstructSparsifier will output a
$(2\epsilon)$-sparsifier with high probability. This part has query complexity
$O(n\log^{3}n/\epsilon^{2})$. ∎

###  4.3 Randomized Algorithm for $(1-\epsilon)$-approximation with
$\widetilde{O}(n)$ Queries

To remove the dependence of the query complexity on the weights of the graph,
we show that we can stop NaiveWeightedSubsample before all edges have been
assigned strengths. This may no longer give us a sparsifier, but it will still
suffice for max-cut.

######  Theorem 4.10.

Let $H=\text{NaiveWeightedSubsample}(G,n^{3})$. Then $H$ can be calculated in
$O(n\log^{3}n(\log n+\frac{1}{\epsilon^{2}}))$ queries, and outputing the cut
$U$ maximizing $F(U;H)$ will achieve a $(1-5\epsilon)$-approximation for max-
cut with probability $1-O(n^{1-d}\log n)$.

###### Proof.

Once again, we provide an outline and defer details to Appendices E.5.3
(correctness) and E.8 (efficiency). To see why this eliminates the query
complexity’s dependence on $W$, note that $\kappa$ is now only allowed to vary
between $W_{\text{tot}}$ and $W_{\text{tot}}/n^{3}$, so the outer loop can now
only proceed for $O(\log n)$ iterations, as opposed to $O(\log n+\log W)$.
This is also essentially why the success probability no longer depends on $W$.

For correctness, the intuition is that the output of
$\text{NaiveWeightedSubsample}(G,n^{3})$ is essentially the same as taking the
sparsifier output by $\text{NaiveWeightedSubsample}(G,\infty)$ and discarding
sufficiently weak edges. It can be shown that in the sparsifier, these weak
edges have total weight $O(W_{\text{tot}}/n)$, which is much less than
$W_{\text{tot}}/2$ and hence the value of the max cut. Hence discarding these
weak edges will only shift the max cut by a factor of $1-o(1)$, so it suffices
to use $\text{NaiveWeightedSubsample}(G,n^{3})$.

∎

######  Corollary 4.11.

For any $c<1$, the query complexity for a randomized algorithm to achieve a
$c$-approximation with $1-o(1)$ probability for global max-cut on a weighted
undirected graph in the cut finding setting is $\tilde{O}(n)$. This algorithm
is adaptive.

###  4.4 Sparsification with $\widetilde{O}(n)$ Queries

We have already provided a $(1-\epsilon)$-approximation for max-cut that runs
in $\widetilde{O}(n)$ queries. However, it turns out that with some additional
work, we can use these ideas to even construct sparsifiers in
$\widetilde{O}(n)$ queries. We begin by setting up the necessary ideas.

####  4.4.1 Crude Edge Strength Estimates

Recall that the key problem with Algorithm 4.3 was that our “sliding window”
for edge strength estimation could potentially repeat $O(\log n+\log W)$
times. The key idea is to mitigate this by finding very crude (within a factor
of $n^{4}$) estimates for the edge strengths for all edges in $G$, before
refining these estimates using EstimateAndContract. We do this using the idea
of [BK15] to estimate edge strengths from the maximum spanning forest (MSF) of
$G$. Fix an MSF $\mathcal{T}$ of $G$. Then for any edge $e$ with endpoints
$i,j$, define $d_{e}=d_{i,j}$ to be the minimum weight of an edge on the MSF
path between the endpoints of $e$. We first state a lemma shown in [BK15]:

######  Lemma 4.12.

([BK15]) For all edges $e$, we have $d_{e}\leq k_{e}\leq n^{2}d_{e}$.

This would immediately give us sufficient edge strength estimates but we do
not know of a way to find the MSF efficiently in the cut query model. In fact,
we can adapt the max cut dimension argument from Lemma 3.3 to a “max tree
dimension” argument to show that deterministically finding the MSF requires
$\Omega(n^{2})$ queries; see Appendix A.3 for details. So instead, we run what
we call “approximate Kruskal” using the primitives we have available from
Lemma 4.5.

Data: Graph $G$ on $n$ vertices

Result: A forest $\mathcal{\widetilde{T}}$ using the edges of $G$.

Initialize $\mathcal{\widetilde{T}}$ to be the empty graph on $n$ vertices.

$\text{InitializeDS}(G)$.

while  _$\text{GetTotalWeight}(G) >0$_ do

$e=\text{GetEdge}()$

$\text{Contract}(e)$

Add $e$ to $\mathcal{\widetilde{T}}$.

end while

Algorithm 4.4 $\text{ApproximateKruskal}(G)$

It follows from Lemma 4.5 that ApproximateKruskal can be run in $O(n\log n)$
queries. Once we run ApproximateKruskal, we will have a spanning forest of $G$
so we will also know its connected components. Moreover, the following lemma
tells us that even this crude approximation to the MSF suffices to give us
edge strength estimates. We defer the proofs of this lemma and its
straightforward corollary to Appendix E.6.1.

######  Lemma 4.13.

For any distinct $i,j$, define $\tilde{d}_{i,j}$ as follows:

  * •

If $i,j$ are connected in $G$, then let $\tilde{d}_{i,j}$ be the minimum
weight of an edge on the path in $\mathcal{\widetilde{T}}$ connecting $i$ and
$j$.

  * •

Otherwise, let $\tilde{d}_{i,j}=0$.

Then for any $i,j$ that are connected in $G$, we have
$\frac{2}{n^{2}}d_{i,j}\leq\tilde{d}_{i,j}\leq d_{i,j}$ for all $i,j$.

Note that we only assume here that $\mathcal{T}$ is maximal; any assumptions
we make about $\widetilde{\mathcal{T}}$ are baked into GetEdge.

######  Corollary 4.14.

For all distinct $i,j$, we have
$k_{i,j}\in[\tilde{d}_{i,j},\frac{n^{4}}{2}\tilde{d}_{i,j}]$.

####  4.4.2 Fast Weighted Subsampling

We now describe how to use our crude edge strength estimates to construct a
sparsifier in $\tilde{O}(n)$ queries. The idea is that by Lemma 4.7, any edges
with strength $<\kappa/2$ will be deleted in Step 2 of Algorithm 4.1. But we
can use our crude edge strength estimates to preemptively identify some edges
that will definitely be deleted, and then delete these edges to disconnect the
graph a bit _before_ running EstimateAndContract. We describe this procedure
in Algorithm 4.5.

Data: Graph $G$ on $n$ vertices

Result: A potential $(2\epsilon)$-sparsifier $H$ of $G$.

Run ApproximateKruskal on a copy of $G$ and calculate $\tilde{d}_{i,j}$ for
all $i,j$.

Initialize $L$ to a list of all nonzero values of $\tilde{d}_{i,j}$.

Initialize $\mathcal{C}=\emptyset$, $\kappa=\infty$, and $X$ as an empty list.

$\text{InitializeDS}(G)$.

while  _$L\neq\emptyset$_ do

Let $\tilde{D}=\max L$ and
$C=\left\\{(i,j):\tilde{d}_{i,j}<\tilde{D}/(2n^{5})\right\\}$.

Let $S_{1},\ldots,S_{r}$ be the connected components of $K_{n}$ after we
remove all edges from $C$.

Let $\kappa^{\prime}$ be the smallest power of 2 that is at least
$n^{4}\tilde{D}/2$.

$\kappa\leftarrow\min(\kappa,\kappa^{\prime})$

while  _$\kappa\geq\tilde{D}/(2n)$_ do

for  _$i\leftarrow 1$ to $r$_ do

$\text{EstimateAndContract}(G[S_{i}],\mathcal{C},\kappa,X)$

Remove all contracted edges from $L$.

end for

$\kappa\leftarrow\kappa/2$

end while

end while

$H\leftarrow\text{ConstructSparsifier}(G,X).$

Algorithm 4.5 $\text{FastWeightedSubsample}(G)$

We make one comment here about FastWeightedSubsample: for the algorithm as
presented to even be well-defined, we need to check that each $S_{i}$ at any
stage of the algorithm is the union of some collection of supernodes. If not,
it does not make sense to run EstimateAndContract on each $G[S_{i}]$. This
condition is also necessary to ensure the applicability of Lemma 4.5 to each
call to EstimateAndContract; Contract, GetTotalWeight, and Sample all require
that their input $S$ be a union of supernodes. We defer the verification of
this and the proof of our final theorem to Appendices E.7 (correctness) and
E.8 (efficiency):

######  Theorem 4.15.

FastWeightedSubsample runs in $O(n\log^{3}n(\log n+\frac{1}{\epsilon^{2}}))$
queries and outputs a $(2\epsilon)$-sparsifier $H$ with probability
$1-O(n^{5-d})$.

######  Corollary 4.16.

For any $\epsilon>0$, the query complexity for a randomized algorithm to
construct an $\epsilon$-sparsifier with $1-o(1)$ probability for a weighted
undirected graph is $\widetilde{O}(n)$. This algorithm is adaptive.

Note that by Lemma 4.2, this also implies Corollary 4.11.

We remind the reader that Theorem 4.15 extends the query-efficient sparsifier
of [RSW18] to weighted graphs (as we saw in Section 4.2, a naive
generalization of [RSW18] requires $\widetilde{O}(n\log W)$ queries).

##  5 Other Algorithmic Results

We noted in Section 1.1 that there exists a straightforward $O(n^{2})$
deterministic algorithm to learn the graph and hence find the max cut, even in
the cut finding setting. This immediately addresses quite a few of the
algorithmic results stated there. We have addressed the randomized upper bound
in Theorem 1.2 in Section 4. We now finally address the randomized upper bound
in Theorem 1.3 in Section 5.1, and the deterministic upper bound in Theorem
1.3 in Section 5.2.

###  5.1 Warm-Up: Randomized Algorithm for $(1/2-\epsilon)$-approximation

Here we address the randomized upper bound part of Theorem 1.3. This is
subsumed by the results in [FMV11] as they show these results for arbitrary
symmetric submodular functions, but we restate the main ideas here to help
motivate our deterministic algorithms in Sections 5.2 and 5.3. The primary
observation enabling this algorithm is simple and well-known:

######  Lemma 5.1.

Suppose we sample a cut $U$ uniformly at random from subsets of $[n]$. Then we
have
$\mathbb{E}[F(U)]=\frac{1}{2}\sum_{i<j}w_{i,j}\geq\frac{1}{2}\max_{S}F(S)$.

###### Proof.

Observe that this sampling is equivalent to independently assigning each
vertex to either be in $U$ or not be in $U$ with probability $1/2$. Thus for
any pair of distinct vertices $i,j$, they will be on opposite sides of the cut
with probability exactly $1/2$. The lemma follows. ∎

This lemma implies that randomly sampling a cut achieves a
$(1/2)$-approximation in expectation, and this takes just 1 query. We can
strengthen this to a non-adaptive algorithm that succeeds with arbitrarily
high probability by repeating this procedure $O(1)$ times:

######  Corollary 5.2.

For $c<1/2$ and a probability $p>0$, there exists a non-adaptive randomized
algorithm using $\log(1/p)/\log(2-2c)$ queries that finds a $c$-approximate
max cut with probability at least $1-p$.

This implies that the query complexity for a randomized algorithm to achieve a
$c$-approximation with $\Omega(1)$ probability for global max-cut on a
weighted undirected graph in the cut finding setting is $O(1)$.

###### Proof.

See Appendix F.1. ∎

Thus a randomized algorithm can achieve a $c$-approximation in $O(1)$ queries
by simply querying $O(1)$ random cuts and outputting the largest one. We will
now see that a similar idea can be made to work for deterministic algorithms
as well.

###  5.2 Deterministic Algorithm for $(1/2-\epsilon)$-approximation

Here we show the deterministic upper bound part of Theorem 1.3. As just
mentioned, we would like to draw on the intuition from Section 5.1 that
sampling random cuts suffices since these achieve a $(1/2)$-approximation in
expectation. Of course, doing this directly faces the obstacle that we cannot
randomly sample cuts. However, it turns out that it suffices to find a
deterministic set of cuts that is “sufficiently random”. This is made precise
by the following lemma:

######  Lemma 5.3.

Let $q=\frac{4}{(1-2c)^{2}}\log n$. Then there exist cuts
$Q_{1},Q_{2},\ldots,Q_{q}\subseteq[n]$ such that the following condition
holds: every edge $(i,j)$ for distinct $i,j\in[n]$ appears in at least a $c$
fraction of these cuts.

###### Proof.

See Appendix G.1. ∎

Now we will show that it essentially just suffices to query the $q$ cuts
provided by Lemma 5.3 and output the largest one, mimicking the repetition
procedure used in the proof of Corollary 5.2.

######  Theorem 5.4.

For any $c<1/2$, a deterministic algorithm can non-adaptively find a
$c$-approximate max cut in $\frac{4}{(1-2c)^{2}}\log n$ queries.

This implies that the query complexity for a non-adaptive deterministic
algorithm to achieve a $c$-approximation for global max-cut on a weighted
undirected graph in the cut finding setting is $O(\log n)$.

###### Proof Sketch.

Since Lemma 5.3 is completely independent of the particular graph the
algorithm is dealing with, the algorithm can as a first step find $q$ such
cuts $Q_{1},\ldots,Q_{q}$ without making any queries at all. (Even though we
showed the existence of these cuts using the probabilistic method, such a set
of cuts can be found deterministically e.g. with brute force search.) Once the
algorithm has done this, it can query each of $Q_{1},\ldots,Q_{q}$ and output
whichever cut has the largest value. We verify that this algorithm works in
Appendix G.2. ∎

###  5.3 Deterministic Algorithm for $(1/2)$-approximation

Here we show that $O(n)$ queries suffice to achieve a $(1/2)$-approximation.
There is a well-known greedy algorithm for this in the classical model, but we
reproduce it here for completeness and to highlight that it can be readily
adapted to the cut query model.

######  Lemma 5.5.

A deterministic algorithm can adaptively find a $(1/2)$-approximate max cut
with $5n$ queries.

This implies that the query complexity for an adaptive deterministic algorithm
to achieve a $(1/2)$-approximation for global max-cut on a weighted undirected
graph in the cut finding setting is $O(n)$.

###### Proof.

See Appendix H.1. We use a greedy algorithm that in some sense derandomizes
the naive random sampling we saw in Lemma 5.1. ∎

##  6 Conclusion and Future Directions

We initiate the study of the cut-query complexity of global max-cut. We nail
down the query complexity for a large range of constant approximation
guarantees. In particular, we show that $\Omega(n^{2})$ queries are necessary
for a deterministic algorithm to learn the max-cut exactly, enough to learn
the entire graph. Additionally, we observe a phase transition at $c=1/2$:
achieving a $c$-approximation can be done by a deterministic algorithm with
$O(\log n)$ queries when $c<1/2$, exponentially fewer than the $\Omega(n/\log
n)$ queries needed by even a randomized algorithm when $c>1/2$. This matches a
similar phase transition at $c=1/2$ for general submodular function
maximization (but the query complexity of max-cut in both ranges is
exponentially smaller than in submodular function maximization).

One range of $c$ remains unresolved for randomized and deterministic
algorithms. For randomized algorithms, the only remaining cases are $c=1$
(exact max-cut) and $c=1/2$. Our randomized $\tilde{O}(n)$-query algorithm
relies on sparsifiers and therefore does not extend to exact max-cut, and we
do not have a matching lower bound for $c=1/2$. Similarly, our
$\Omega(n^{2})$-hardness for deterministic algorithms relies on the cut
dimension, and therefore does not extend to randomized algorithms. For
deterministic algorithms, the remaining range is $[1/2,1)$. One possible
approach is to design a query-efficient deterministic sparsifier. Such
sparsifiers are known in the computational model (e.g. [BSS14]), but would
require significantly new ideas to implement using $\tilde{O}(n)$ cut queries,
as they typically require global information about the graph (e.g. the
spectrum of the Laplacian).

We are optimistic that the techniques used in proving these results,
especially our query-efficient sparsifier for weighted graphs, and our
extension of the cut dimension to rule out approximation algorithms, will be
applicable to other graph problems in the cut query model. Lemma 3.12, our
technical lemma used in Section 3.2 to prove a deterministic lower bound when
$c>1/2$, shows a simple geometric property of the Boolean hypercube and may be
applicable to problems in other domains as well.

## References

  * [ACK19] Sepehr Assadi, Yu Chen, and Sanjeev Khanna.  Polynomial pass lower bounds for graph streaming algorithms.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 265–276. ACM, 2019.
  * [AEG+22] Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, and Danupon Nanongkai.  Cut query algorithms with star contraction.  CoRR, abs/2201.05674, 2022.
  * [AGM12a] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 459–467. SIAM, 2012.
  * [AGM12b] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Graph sketches: sparsification, spanners, and subgraphs.  In Michael Benedikt, Markus Krötzsch, and Maurizio Lenzerini, editors, Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 5–14. ACM, 2012.
  * [AGM13] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Spectral sparsification in dynamic graph streams.  In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, volume 8096 of Lecture Notes in Computer Science, pages 1–10. Springer, 2013.
  * [AL21] Simon Apers and Troy Lee.  Quantum complexity of minimum cut.  In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 28:1–28:33. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2021.
  * [BF18] Niv Buchbinder and Moran Feldman.  Deterministic algorithms for submodular maximization problems.  ACM Trans. Algorithms, 14(3):32:1–32:20, 2018.
  * [BFNS12] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz.  A tight linear time (1/2)-approximation for unconstrained submodular maximization.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 649–658. IEEE Computer Society, 2012.
  * [BK15] András A. Benczúr and David R. Karger.  Randomized approximation schemes for cuts and flows in capacitated graphs.  SIAM J. Comput., 44(2):290–319, 2015.
  * [BSS14] Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava.  Twice-ramanujan sparsifiers.  SIAM Rev., 56(2):315–334, 2014.
  * [CGJS22] Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, and Aaron Sidford.  Improved lower bounds for submodular function minimization.  CoRR, abs/2207.04342, 2022.
  * [CT06] Thomas M. Cover and Joy A. Thomas.  Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing).  Wiley-Interscience, USA, 2006.
  * [DR98] Devdatt P. Dubhashi and Desh Ranjan.  Balls and bins: A study in negative dependence.  Random Struct. Algorithms, 13(2):99–124, 1998.
  * [FMV11] Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák.  Maximizing non-monotone submodular functions.  SIAM J. Comput., 40(4):1133–1153, 2011.
  * [GK00] Vladimir Grebinski and Gregory Kucherov.  Optimal reconstruction of graphs under the additive model.  Algorithmica, 28(1):104–124, 2000.
  * [GPRW20] Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, and S. Matthew Weinberg.  New query lower bounds for submodular function minimization.  In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 64:1–64:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [GW95] Michel X. Goemans and David P. Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  J. ACM, 42(6):1115–1145, 1995.
  * [GW11] Anupam Gupta and Timothy Wilson.  Lecture notes: LP duality.  https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture05.pdf, 2011\.
  * [Har08] Nicholas J. A. Harvey.  Matchings, matroids and submodular functions.  PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 2008.
  * [Hås01] Johan Håstad.  Some optimal inapproximability results.  J. ACM, 48(4):798–859, 2001.
  * [Jia21] Haotian Jiang.  Minimizing convex functions with integral minimizers.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 976–985. SIAM, 2021.
  * [Kar99] David R. Karger.  Random sampling in cut, flow, and network design problems.  Math. Oper. Res., 24(2):383–413, 1999.
  * [Kho02] Subhash Khot.  On the power of unique 2-prover 1-round games.  In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 767–775. ACM, 2002.
  * [KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell.  Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?  SIAM J. Comput., 37(1):319–357, 2007.
  * [KLM+14] Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford.  Single pass spectral sparsification in dynamic streams.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 561–570. IEEE Computer Society, 2014.
  * [LLSZ21] Troy Lee, Tongyang Li, Miklos Santha, and Shengyu Zhang.  On the cut dimension of a graph.  In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 15:1–15:35. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2021.
  * [LSW15] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong.  A faster cutting plane method and its implications for combinatorial and convex optimization.  In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1049–1065. IEEE Computer Society, 2015.
  * [LSZ21] Troy Lee, Miklos Santha, and Shengyu Zhang.  Quantum algorithms for graph problems with cut queries.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 939–958. SIAM, 2021.
  * [MN20] Sagnik Mukhopadhyay and Danupon Nanongkai.  Weighted min-cut: sequential, cut-query, and streaming algorithms.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 496–509. ACM, 2020.
  * [RSW18] Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg.  Computing exact minimum cuts without knowing the graph.  In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 39:1–39:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [SWYZ19] Xiaoming Sun, David P. Woodruff, Guang Yang, and Jialin Zhang.  Querying a matrix through matrix-vector products.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 94:1–94:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.

##  Appendix A Lemmas from Section 3.1

###  A.1 Proof of Lemma 3.3

Suppose for the sake of contradiction that there is a deterministic algorithm
that uses $q\leq d-1$ queries. Then let the algorithm run against an adversary
that answers all queries as if the graph were the $G$ given in the statement
of the lemma. Let $w\in\mathbb{R}^{|E(G)|}$ be the weight vector corresponding
to $G$, and $Q_{1},Q_{2},\ldots,Q_{q}$ be the queries made by the algorithm.

The idea is to find a nonzero “perturbation direction”
$z\in\mathbb{R}^{|E(G)|}$ and small $\epsilon\neq 0$ such that $w,w+\epsilon
z$ agree on all queries but have different max cut values, so that the
algorithm cannot succeed. It suffices to show that such a perturbation exists.

To do this, let $X$ be the max cut space of $G$, so that we have $\dim X=d$.
Also, let $Y$ be the span of $v_{Q_{1}},\ldots,v_{Q_{q}}$ so that $\dim Y\leq
q<d=\dim X$. It follows that $Y^{\perp}$ (the orthogonal complement of $Y$)
and $X$ must have nontrivial intersection777To see this, note that $\dim
Y^{\perp}=|E(G)|-\dim Y$ and we have $|E(G)|\geq\dim(X+Y^{\perp})=\dim X+\dim
Y^{\perp}-\dim(X\cap Y^{\perp})=\dim X+|E(G)|-\dim Y-\dim(X\cap
Y^{\perp})\Leftrightarrow\dim(X\cap Y^{\perp})\geq\dim X-\dim Y>0$.. Let us
take $z$ to be any nonzero vector in $X\cap Y^{\perp}$, and $\epsilon$
positive but small enough that both $w-\epsilon z$ and $w+\epsilon z$ have
only positive entries (we can do this since $w$ has only positive entries).
Thus $w-\epsilon z$ and $w+\epsilon z$ will both correspond to valid graphs
with non-negative weights.

Since $z\in X$ (which is the max cut space) and $z$ is nonzero, we have
$z\notin X^{\perp}$ so that there exists some max cut $C$ such that
$z^{T}v_{C}\neq 0$. Assume WLOG that $z^{T}v_{C}>0$; if it is negative then we
can just replace $z$ with $-z$. Then we claim that $w,w+\epsilon z$ agree on
all queries but have differing max cut values. To see that they agree on all
queries, note that $z\in Y^{\perp}\Rightarrow z^{T}v_{Q_{i}}=0$ for all $i$.
Then we also have for all $i$ that $(w+\epsilon
z)^{T}v_{Q_{i}}=w^{T}v_{Q_{i}}+\epsilon z^{T}v_{Q_{i}}=w^{T}v_{Q_{i}}$, thus
they indeed agree on the queries.

Finally, to see that the max cut values differ, note that:

$\displaystyle(w+\epsilon z)^{T}v_{C}$ $\displaystyle=w^{T}v_{C}+\epsilon
z^{T}v_{C}$ $\displaystyle>w^{T}v_{C}.$

Now, the max cut value of the graph corresponding to $w+\epsilon z$ is at
least the value of the cut defined by $C$, which is $(w+\epsilon z)^{T}v_{C}$.
This is strictly greater than $w^{T}v_{C}$ which by definition of $C$ is
exactly the max cut value of the graph corresponding to $w$. This establishes
that the graphs have distinct max cut values and completes the proof of the
lemma.

###  A.2 Proof of Lemma 3.4

Observe that any set $S\subseteq[n]$ has cut value $F(S)=|S|(n-|S|)$, so $S$
is a max cut if and only if $|S|\in\left\\{\lfloor n/2\rfloor,\lceil
n/2\rceil\right\\}$. We need to show three things:

  1. 1.

When $n\geq 3$ is odd, the max cut space of $K_{n}$ is all of
$\mathbb{R}^{\binom{n}{2}}$ (and thus has dimension $\binom{n}{2}$).

  2. 2.

When $n\geq 4$ is even, the max cut space of $K_{n}$ has dimension at least
$\binom{n-1}{2}$.

  3. 3.

When $n\geq 4$ is even, the max cut space of $K_{n}$ has dimension at most
$\binom{n-1}{2}$.

Note that the third claim is not necessary since we just need a lower bound on
the max cut dimension, but we prove it for completeness. As we remark at the
end, the proof of the third claim in Lemma A.3 also tells us exactly which
$\binom{n-1}{2}$-dimensional subspace gives the max cut space of $K_{n}$ when
$n$ is even.

To set up our proofs, we introduce some helpful notation. For any disjoint
sets $S,T\subseteq[n]$, let $E(S,T)$ be the set of vertex pairs/edges with one
endpoint in $S$ and the other in $T$. Similarly, let
$v_{S,T}\in\mathbb{R}^{\binom{n}{2}}$ be the indicator vector defined as
follows:

$\displaystyle(v_{S,T})_{i,j}$ $\displaystyle=\begin{cases}1,&i\in S\text{ and
}j\in T\text{ or vice versa},\\\ 0,&\text{ otherwise}.\end{cases}$

So for example we have $v_{S,[n]\backslash S}=v_{S}$. When
$S=\left\\{a\right\\}$ or $T=\left\\{b\right\\}$ are singletons, we also
denote $v_{S,T}$ by $v_{a,b}$, $v_{S,U}$ by $v_{a,U}$ etc. Thus the
$\binom{n}{2}$ vectors $v_{i,j}$ for all $i\neq j$ form the standard
orthonormal basis for $\mathbb{R}^{\binom{n}{2}}$.

Now we turn to proving these lemmas:

######  Lemma A.1.

For $n\geq 3$ odd, the max cut space of $K_{n}$ is all of
$\mathbb{R}^{\binom{n}{2}}$.

###### Proof.

Let $X$ be the max cut space of the graph. We proceed in steps to show that
$X$ contains $v_{a,b}$ for all pairs of distinct vertices $(a,b)$, which we do
by just taking appropriate linear combinations of the indicator vectors of max
cuts. This would imply the desired result since the $v_{a,b}$’s form a
complete orthonormal basis.

Step 1. $v_{a,b}-v_{a,c}\in X$ whenever $a\neq b$ and $a\neq c$.

If $b=c$ then we have $v_{a,b}-v_{a,c}=0\in X$ since $X$ is a subspace. Thus
from now assume that $b\neq c$ also. Let $A,B$ be any partition of the
vertices excluding $a,b,c$ into two sets of size $\frac{n-3}{2}$. (We can do
this since $n\geq 3$; if $n=3$ just let $A,B$ both be the empty set.) Let
$S_{1}$ be the cut with $a,b,A$ on one side and $c,B$ on the other, and
$S_{2}$ the cut with $b,A$ on one side and $a,c,B$ on the other. These are
both max cuts, so $v_{S_{1}}-v_{S_{2}}=v_{a,c}+v_{a,B}-v_{a,b}-v_{a,A}\in X$.

But we can repeat this with $A$ and $B$ swapped to find that
$v_{a,c}+v_{a,A}-v_{a,b}-v_{a,B}\in X$. Adding this with the vector from the
above paragraph and dividing by 2 gives $v_{a,c}-v_{a,b}\in X\Rightarrow
v_{a,b}-v_{a,c}\in X$ as desired.

Step 2. $v_{a,b}-v_{c,d}\in X$ whenever $a\neq b$ and $c\neq d$.

If $\left\\{a,b\right\\}$ and $\left\\{c,d\right\\}$ intersect then this is a
special case of Step 1, so assume they are disjoint. In this case, this
follows since $v_{a,b}-v_{c,d}=[v_{a,b}-v_{a,c}]+[v_{a,c}-v_{c,d}]\in X$ (the
term in each bracket is in $X$ by Step 1).

Step 3. $v_{a,b}\in X$ whenever $a\neq b$.

Take an arbitrary max cut $S$. Then we have

$\displaystyle v_{S}=\sum_{(c,d)\in E(S,[n]\backslash S)}v_{c,d}\in X.$

We also have

$\displaystyle\sum_{(c,d)\in E(S,[n]\backslash S)}[v_{a,b}-v_{c,d}]\in X$

by Step 2. Adding these gives

$\displaystyle\sum_{(c,d)\in E(S,[n]\backslash S)}v_{a,b}=|S|(n-|S|)v_{a,b}\in
X.$

Since $S$ is a max cut, we have $|S|(n-|S|)\neq 0$ so dividing by this scalar
yields that $v_{a,b}\in X$ as desired. ∎

######  Lemma A.2.

For $n\geq 4$ even, the max cut space of $K_{n}$ has dimension at least
$\binom{n-1}{2}$.

###### Proof.

The idea is that we can roughly show that the max cut space of an induced
$K_{n-1}$ within this graph is “nested” within the max cut space of this
graph. Since the former max cut space has dimension $\binom{n-1}{2}$, this
would yield the lemma.

To make this precise, let $V\subseteq\mathbb{R}^{\binom{n}{2}}$ be the
subspace spanned by $v_{i,j}$ for all $i\neq j$ such that $i,j\in[n-1]$, and
let $\mathcal{P}_{V}$ be the orthogonal projection onto $V$. Thus $V$ has
dimension $\binom{n-1}{2}$ and $\mathcal{P}_{V}$ is the operator that zeroes
out all coordinates corresponding to edges involving vertex $n$.

Let $X$ be the max cut space of $K_{n}$. Then it suffices to show that
$\mathcal{P}_{V}(X)=V$. Then the conclusion would follow since $\dim
X\geq\dim\mathcal{P}_{V}(X)=\dim V=\binom{n-1}{2}$.888To see why $\dim
X\geq\dim\mathcal{P}_{V}(X)$, let $d=\dim X$ and take a basis
$u_{1},u_{2},\ldots,u_{d}$ of $X$. Then $\mathcal{P}_{V}(X)$ is the span of
$\mathcal{P}_{V}(u_{1}),\mathcal{P}_{V}(u_{2}),\ldots,\mathcal{P}_{V}(u_{d})$
and thus has dimension at most $d$. This is an inequality since these $d$
vectors need not be linearly independent.

To do this, let $T\subseteq[n-1]$ be any set of size $(n-2)/2$ and let
$S=T\cup\left\\{n\right\\}$. Then $|S|=n/2$ so $S$ is a max cut, and we have:

$\displaystyle v_{S}$ $\displaystyle=\sum_{i\in S}\sum_{j\in[n]\backslash
S}v_{i,j}$ $\displaystyle=\sum_{i\in
T\cup\left\\{n\right\\}}\sum_{j\in[n-1]\backslash T}v_{i,j}.$

To find $\mathcal{P}_{V}(v_{S})$, we just need to zero out all terms here that
have one endpoint at $n$. This gives us:

$\displaystyle\mathcal{P}_{V}(v_{S})$ $\displaystyle=\sum_{i\in
T\cup\left\\{n\right\\}}\sum_{j\in[n-1]\backslash T}v_{i,j}$
$\displaystyle=\sum_{i\in T}\sum_{j\in[n-1]\backslash T}v_{i,j}$
$\displaystyle=v_{T,[n-1]\backslash T}.$

Since $X$ is the max cut space of $K_{n}$, we know that $v_{S}\in
X\Rightarrow\mathcal{P}_{V}(v_{S})\in\mathcal{P}_{V}(X)$. It follows that we
have:

$\displaystyle\mathcal{P}_{V}(X)$
$\displaystyle\supseteq\operatorname{span}(\left\\{\mathcal{P}_{V}(v_{S}):|S|=n/2\right\\})$
$\displaystyle\supseteq\operatorname{span}(\left\\{v_{T,[n-1]\backslash
T}:T\subseteq[n-1]\text{ and }|T|=(n-2)/2\right\\}).$

Now note that this is exactly the max cut space of the induced subgraph of our
$K_{n}$ on $[n-1]$, which is an instance of $K_{n-1}$. This is because any max
cut of this induced subgraph will have one side with $(n-2)/2$ vertices and
the other side with $n/2$ vertices, so we can take always take $T$ to be the
side with $(n-2)/2$ vertices. Since $n-1$ is odd and $n-1\geq 3$, Lemma A.1
tells us that this span is in fact all of $V$. Thus
$\mathcal{P}_{V}(X)\supseteq V$ and we have $\mathcal{P}_{V}(X)\subseteq V$ by
definition of $\mathcal{P}_{V}$, so this proves that $\mathcal{P}_{V}(X)=V$
and completes the proof of the lemma. ∎

######  Lemma A.3.

For $n\geq 4$ even, the max cut space of $K_{n}$ has dimension at most
$\binom{n-1}{2}$. Moreover, the max cut space of $K_{n}$ is exactly the space
of all weight vectors $w\in\mathbb{R}^{\binom{n}{2}}$ that have the same total
weight at each vertex.

###### Proof.

We first prove the stated upper bound on the dimension of the max cut space.
The idea is that all vertices have degree $n/2$ in any max cut of $K_{n}$ for
even $n$, and that this adds some linear constraints that restrict the
dimensionality of the max cut space. This is because a max cut will split the
vertices into two halves of size $n/2$ and each vertex is connected to all the
vertices on the opposite half. Writing this in our linear algebraic notation,
we have for any max cut $S$ and vertex $i\in[n]$ that:

$\displaystyle v_{S}^{T}v_{i,[n]\backslash\left\\{i\right\\}}$
$\displaystyle=v_{S}^{T}(\sum_{j\neq i}v_{i,j})$ $\displaystyle=\frac{n}{2}.$

Thus for any two distinct vertices $i,j$, we have:

$\displaystyle
v_{S}^{T}(v_{i,[n]\backslash\left\\{i\right\\}}-v_{j,[n]\backslash\left\\{j\right\\}})$
$\displaystyle=0.$

Now let $X$ be the max cut space of $K_{n}$. For any max cut $S$, the
indicator vector $v_{S}$ is orthogonal to
$v_{i,[n]\backslash\left\\{i\right\\}}-v_{j,[n]\backslash\left\\{j\right\\}}$.
Thus arbitrary linear combinations of the $v_{S}$’s are orthogonal to
$v_{i,[n]\backslash\left\\{i\right\\}}-v_{j,[n]\backslash\left\\{j\right\\}}$,
so that all vectors in $X$ are orthogonal to
$v_{i,[n]\backslash\left\\{i\right\\}}-v_{j,[n]\backslash\left\\{j\right\\}}$.
Thus let us define $Y$ to be the following subspace:

$\displaystyle Y$
$\displaystyle=\operatorname{span}(\left\\{v_{i,[n]\backslash\left\\{i\right\\}}-v_{j,[n]\backslash\left\\{j\right\\}}:i\neq
j\right\\}).$

Then what we have just argued is that $X\subseteq Y^{\perp}$. It follows that
$\dim X\leq\dim Y^{\perp}=\binom{n}{2}-\dim Y$. Thus it suffices to show that
$\dim Y\geq n-1$.

To do this, consider the following set of $n-1$ vectors $u_{i}$ for
$i\in[n-1]$, where we define $u_{i}$ as follows:

$\displaystyle u_{i}$
$\displaystyle=v_{i,[n]\backslash\left\\{i\right\\}}-v_{n,[n-1]}.$

Clearly $u_{i}\in Y$ for all $i$ so it suffices to show that
$u_{1},u_{2},\ldots,u_{n-1}$ are linearly independent. Indeed, suppose we have
scalars $\lambda_{i}\in\mathbb{R}$ such that:

$\displaystyle\sum_{i=1}^{n-1}\lambda_{i}u_{i}$ $\displaystyle=0$
$\displaystyle\Leftrightarrow\sum_{i=1}^{n-1}\lambda_{i}(v_{i,[n]\backslash\left\\{i\right\\}}-v_{n,[n-1]})$
$\displaystyle=0.$

For any distinct $i,j\in[n-1]$, the coefficient of $v_{i,j}$ on the LHS must
be 0 (equivalently, the inner product of the LHS with $v_{i,j}$ must be 0).
This is equivalent to $\lambda_{i}+\lambda_{j}=0$. Since this is true for all
distinct $i,j\in[n-1]$ and $n\geq 4$, this forces $\lambda_{i}=0$ for all
$i$.999To see this, note that for any $i\in[n-1]$ we can find two more indices
$j,k\in[n-1]$ such that $i,j,k$ are distinct (this is why we need $n\geq 4$)
and then we have
$\lambda_{i}+\lambda_{j}=\lambda_{j}+\lambda_{k}=\lambda_{k}+\lambda_{i}=0\Rightarrow\lambda_{i}=\lambda_{j}=\lambda_{k}=0$.
This implies the stated linear independence and thus that $\dim
X\leq\binom{n-1}{2}$. This addresses the first part of the lemma.

It follows by Lemma A.2 that this argument must be tight. Thus we must have
that $\dim Y=n-1$ and $X=Y^{\perp}$. Thus $X$ is exactly the orthogonal
complement of $Y$. In other words, the max cut space is the space of all
weight vectors in $\mathbb{R}^{\binom{n}{2}}$ that have the same total weight
at each vertex. This completes the proof of the lemma. ∎

###  A.3 Finding an MSF Requires $\Omega(n^{2})$ Queries

Since we are proving a lower bound in this section, we can restrict attention
to connected graphs and hence work with “maximum spanning trees” (MSTs)
instead of “maximum spanning forests”. We begin by adapting the notion of max
cut dimension to spanning trees.

######  Definition A.4.

Suppose $G$ is connected. For any tree $\mathcal{T}\subseteq G$, let the _tree
vector_ $a(\mathcal{T})\in\mathbb{R}^{|E(G)|}$ be defined as follows:

$\displaystyle a(\mathcal{T})_{i,j}$
$\displaystyle=\begin{cases}1,&(i,j)\text{ is included in }\mathcal{T},\\\
0,&\text{ otherwise}.\end{cases}$

Note that once again, if we describe the graph’s weights with a vector
$w\in\mathbb{R}^{|E(G)|}$, the total weight of a given tree $\mathcal{T}$ is
equal to the inner product $w^{T}a(\mathcal{T})$.

######  Definition A.5.

Suppose $G$ is connected. Then we define the _max tree dimension_ of $G$ to be
equal to the dimension of the span of:

$\left\\{a(\mathcal{T}):\mathcal{T}\text{ is a max spanning tree of
}G\right\\}.$

Call this span the _max tree space_ of the graph.

The following lemma is the adaptation of the cut dimension lemma by [GPRW20]
that we need:

######  Lemma A.6.

Suppose there exists a connected graph $G$ on $n$ vertices with max tree
dimension $d$. Then any deterministic algorithm that finds the total weight of
the maximum spanning tree exactly must use at least $d$ queries.

###### Proof.

This proceeds identically to the proof in Section A.1. $X$ will now be the max
tree space of $G$, and instead of a max cut $C$ we will now take an MST
$\mathcal{T}$ such that $z^{T}a(\mathcal{T})\neq 0$. At the final step, the
graph $G^{\prime}$ defined by $w+\epsilon z$ will agree with $G$ on all cut
queries but the tree defined by $\mathcal{T}$ will now have value strictly
greater than $w^{T}a(\mathcal{T})$, so the total weight of the max spanning
tree in $G^{\prime}$ will be strictly greater than the total weight of the max
spanning tree in $G$. ∎

To finish, we will show that $K_{n}$ has max tree dimension $\Omega(n^{2})$,
which will in turn imply that $\Omega(n^{2})$ queries are needed to
deterministically find an MST:

######  Lemma A.7.

Suppose $n\geq 3$, and let $G=K_{n}$ be the graph on $n$ vertices where all
pairs of distinct vertices share an edge of weight 1. Then the max tree
dimension of $G$ is $\binom{n}{2}$.

###### Proof.

Note that $|E(G)|=\binom{n}{2}$ so it just suffices to show that the max tree
dimension of $G$ is at least $\binom{n}{2}$. Let $X$ be the max tree space of
$K_{n}$. Note that any tree on $K_{n}$ has total weight $n-1$ and is hence a
max spanning tree.

As in the proofs in Section A.2, for distinct vertices $a,b$ let $v_{a,b}$ be
the indicator vector that is 1 for the edge between $a$ and $b$ and 0
everywhere else. We proceed in steps to show that $X$ contains $v_{a,b}$ for
all pairs of distinct vertices $(a,b)$, which we do by just taking appropriate
linear combinations of the indicator vectors of max cuts. This would imply the
desired result since the $v_{a,b}$’s form a complete orthonormal basis.

Step 1. $v_{a,b}-v_{a,c}\in X$ whenever $a\neq b$ and $a\neq c$.

If $b=c$ then we have $v_{a,b}-v_{a,c}=0\in X$ since $X$ is a subspace. Thus
from now assume that $b\neq c$ also. Number the remaining vertices of $G$ by
$1,2,\ldots,n-3$. Consider the following two path graphs on $G$:

  1. 1.

$A$: passes through the vertices in order $1,2,\ldots,n-3,a,b,c$ (i.e. its
edges are $(i,i+1)$ for $i\in[n-4]$ and then $(n-3,a),(a,b),(b,c)$.

  2. 2.

$B$: passes through the vertices in order $1,2,\ldots,n-3,a,c,b$.

$A$ and $B$ are both MSTs on $G$ so we have $a(A),a(B)\in X$. Thus we must
also have $a(A)-a(B)\in X\Rightarrow v_{a,b}-v_{a,c}\in X$ as desired.

Step 2. $v_{a,b}-v_{c,d}\in X$ whenever $a\neq b$ and $c\neq d$.

If $\left\\{a,b\right\\}$ and $\left\\{c,d\right\\}$ intersect then this is a
special case of Step 1, so assume they are disjoint. In this case, this
follows since $v_{a,b}-v_{c,d}=[v_{a,b}-v_{a,c}]+[v_{a,c}-v_{c,d}]\in X$ (the
term in each bracket is in $X$ by Step 1).

Step 3. $v_{a,b}\in X$ whenever $a\neq b$.

Take an arbitrary MST $\mathcal{T}$. Then we have

$a(\mathcal{T})=\sum_{(c,d)\in\mathcal{T}}v_{c,d}\in X.$

We also have by Step 2 that

$\sum_{(c,d)\in\mathcal{T}}[v_{a,b}-v_{c,d}]\in X.$

Adding these gives:

$\sum_{(c,d)\in\mathcal{T}}v_{a,b}=(n-1)v_{a,b}\in X.$

∎

We clearly have $n-1\neq 0$ so dividing by this scalar yields that $v_{a,b}\in
X$ as desired.

##  Appendix B Lemmas from Section 3.2

###  B.1 Proof of Corollary 3.6

This is equivalent to showing that for any positive
$\alpha<\frac{(\sqrt{c}-\sqrt{1-c})^{4}}{108c(2c-1)}$ and $n$ sufficiently
large (where the threshold for being “sufficiently large” might depend on
$\alpha$), $\alpha n$ queries do not suffice to deterministically achieve a
$c$-approximation. By Theorem 3.5, it suffices to show that there exists
$\epsilon\in(0,1)$ such that $c>\frac{1}{1+\epsilon^{2}}$ and
$\alpha<\frac{(1-\epsilon)^{3}}{108(1+\epsilon)}$.

To do this, let $\mu=\sqrt{\frac{1-c}{c}}\in(0,1)$, so that
$c=\frac{1}{1+\mu^{2}}$. Then we have:

$\displaystyle\frac{(1-\mu)^{3}}{108(1+\mu)}$
$\displaystyle=\frac{(1-\sqrt{\frac{1-c}{c}})^{3}}{108(1+\sqrt{\frac{1-c}{c}})}$
$\displaystyle=\frac{(\sqrt{c}-\sqrt{1-c})^{3}}{108c(\sqrt{c}+\sqrt{1-c})}$
$\displaystyle=\frac{(\sqrt{c}-\sqrt{1-c})^{4}}{108c(2c-1)}$
$\displaystyle>\alpha.$

By continuity, there exists an open interval $I$ containing $\mu$ such that
for all $t\in I$ we have $t\in(0,1)$ and $\frac{(1-t)^{3}}{108(1+t)}>\alpha$.
Take $\epsilon\in I$ such that $\epsilon>\mu$ (this exists since $I$ is open
and $\mu\in I$). Then we have $\epsilon\in(0,1)$ and
$\frac{(1-\epsilon)^{3}}{108(1+\epsilon)}>\alpha$, and we have
$\frac{1}{1+\epsilon^{2}}<\frac{1}{1+\mu^{2}}=c$, so this $\epsilon$ satisfies
all conditions. This completes the proof of the corollary.

###  B.2 Proof of Lemma 3.8

It remains to show that it suffices to find a near-max cut $C$ and a
perturbation $z$ such that in addition to the aforementioned constraints we
have:

$\displaystyle z^{T}v_{C}\geq\frac{\epsilon^{2}n^{2}}{4}.$ (3)

To see this, let us analyse the max cut values of the graphs corresponding to
$\mathbf{1}$ and $\mathbf{1}+z$. The graph corresponding to $\mathbf{1}$ is
$K_{n}$ and has max cut value
$\lfloor\frac{1}{4}n^{2}\rfloor\leq\frac{1}{4}n^{2}$. On the other hand, the
graph corresponding to $\mathbf{1}+z$ has max cut value greater than or equal
to the value of the cut $C$, which is

$\displaystyle(\mathbf{1}+z)^{T}v_{C}$
$\displaystyle=\mathbf{1}^{T}v_{C}+z^{T}v_{C}$
$\displaystyle=|C|(n-|C|)+z^{T}v_{C}$
$\displaystyle\geq(\frac{1}{4}n^{2}-n\log n)+\frac{\epsilon^{2}n^{2}}{4}$
$\displaystyle\sim(\frac{1+\epsilon^{2}}{4})n^{2}.$

It follows that the approximation ratio achieved by the algorithm is at most

$\displaystyle\frac{\frac{1}{4}n^{2}}{(\frac{1+\epsilon^{2}}{4}-o(1))n^{2}}$
$\displaystyle=\frac{1}{1+\epsilon^{2}-o(1)}$
$\displaystyle=\frac{1}{1+\epsilon^{2}}+o(1)$ $\displaystyle<c,$

for $n$ sufficiently large, as desired.

###  B.3 Proof of Lemma 3.9

First, suppose that LP1 has value $\geq\epsilon^{2}n^{2}/4$ and let $z$ be a
feasible point attaining the optimum. Then for the matrix LP, define $Z$ as
follows:

$\displaystyle(Z)_{i,j}$ $\displaystyle=\begin{cases}z_{i,j},&i\neq j,\\\
0,&\text{ otherwise}.\end{cases}$

We claim that $Z$ satisfies is feasible for the matrix LP and attains value
$\geq\epsilon^{2}n^{2}/2$. It is clear that $Z\geq-\mathbf{1}$ since any
nonzero entry of $Z$ is also an entry of $z$. Now, we have for any vertex set
$S$ that:

$\displaystyle\langle Z,M_{S}\rangle$
$\displaystyle=\sum_{i_{1},i_{2}}(Z)_{i_{1},i_{2}}(M_{S})_{i_{1},i_{2}}$
$\displaystyle=\sum_{i_{1}\neq
i_{2}}(z)_{i_{1},i_{2}}(v_{S})_{i_{1},i_{2}}\text{ (since $M_{S}$'s diagonal
entries are 0)}$
$\displaystyle=\sum_{i_{1}<i_{2}}2(z)_{i_{1},i_{2}}(v_{S})_{i_{1},i_{2}}$
$\displaystyle=2z^{T}v_{S}.$

Thus we have $\langle Z,M_{Q_{j}}\rangle=2z^{T}v_{Q_{j}}=0$ for all $j$, so
$Z$ satisfies the orthogonality constraints. Moreover, we have $\langle
Z,M_{C}\rangle=2z^{T}v_{C}\geq\epsilon^{2}n^{2}/2$, thus the matrix LP has
value $\geq\epsilon^{2}n^{2}/2$.

Conversely (note that this is the direction that is necessary for the proof of
Theorem 3.5), suppose that the matrix LP has value $\geq\epsilon^{2}n^{2}/2$
and let $Z$ be a feasible point attaining the optimum. Then define $z$ by
$z_{i,j}=\frac{1}{2}(Z_{i,j}+Z_{j,i})$. First for feasibility: note that
$z_{i,j}\geq\frac{1}{2}((-1)+(-1))=-1$. Now, we have for any vertex set $S$
that:

$\displaystyle z^{T}v_{S}$
$\displaystyle=\sum_{i_{1}<i_{2}}(z)_{i_{1},i_{2}}(v_{S})_{i_{1},i_{2}}$
$\displaystyle=\frac{1}{2}\sum_{i_{1}<i_{2}}((Z)_{i_{1},i_{2}}+(Z)_{i_{2},i_{1}})(M_{S})_{i_{1},i_{2}}$
$\displaystyle=\frac{1}{2}\sum_{i_{1}<i_{2}}((Z)_{i_{1},i_{2}}(M_{S})_{i_{1},i_{2}}+(Z)_{i_{2},i_{1}}(M_{S})_{i_{2},i_{1}})\text{
(since $M_{S}$ is symmetric)}$ $\displaystyle=\frac{1}{2}\sum_{i_{1}\neq
i_{2}}(Z)_{i_{1},i_{2}}(M_{S})_{i_{1},i_{2}}$
$\displaystyle=\frac{1}{2}\sum_{i_{1},i_{2}}(Z)_{i_{1},i_{2}}(M_{S})_{i_{1},i_{2}}\text{
(since $M_{S}$'s diagonal entries are 0)}$ $\displaystyle=\frac{1}{2}\langle
Z,M_{S}\rangle.$

Thus we have $z^{T}v_{Q_{j}}=\frac{1}{2}\langle Z,M_{Q_{j}}\rangle=0$ for all
$j$, so $z$ satisfies the orthogonality constraints. Finally, we similarly
have that $z^{T}v_{C}=\frac{1}{2}\langle
Z,M_{C}\rangle\geq\epsilon^{2}n^{2}/4$, thus LP1 has value
$\geq\epsilon^{2}n^{2}/4$. This completes the proof of the lemma.

###  B.4 Proof of Lemma 3.10

First we address the feasibility of $Z=-yy^{T}$. For all $i,j$ we have
$|Z|_{i,j}=|y_{i}|\cdot|y_{j}|\leq 1$ so in particular we have
$Z\geq-\mathbf{1}$. Now for the remaining parts, observe that for any vectors
$u,v\in\mathbb{R}^{n}$ we have $\langle
uu^{T},vv^{T}\rangle=\operatorname{tr}(uu^{T}vv^{T})=\operatorname{tr}(u^{T}vv^{T}u)=(u^{T}v)^{2}$.
Thus for any vertex set $S$ we have:

$\displaystyle\langle Z,M_{S}\rangle$ $\displaystyle=\langle-
yy^{T},\frac{\mathbf{1}\mathbf{1}^{T}-u_{S}u_{S}^{T}}{2}\rangle$
$\displaystyle=-\frac{1}{2}\langle
yy^{T},\mathbf{1}\mathbf{1}^{T}\rangle+\frac{1}{2}\langle
yy^{T},u_{S}u_{S}^{T}\rangle$
$\displaystyle=-\frac{1}{2}(y^{T}\mathbf{1})^{2}+\frac{1}{2}(y^{T}u_{S})^{2}$
$\displaystyle=\frac{1}{2}(y^{T}u_{S})^{2}$

Thus the orthogonality requirement follows, since $\langle
Z,M_{Q_{j}}\rangle=\frac{1}{2}(y^{T}u_{Q_{j}})^{2}=0$. Thus $Z$ is feasible,
and its value in the matrix LP is $\langle
Z,M_{C}\rangle=\frac{1}{2}(y^{T}u_{C})^{2}\geq\epsilon^{2}n^{2}/2$. This
completes the proof.

###  B.5 Proof of Lemma 3.11

We go ahead and take the dual of the stated LP. For the constraint
$-\mathbf{1}\leq z$ take the dual vector $l\geq 0$, for the constraint
$z^{T}w_{i}=0$ take the dual variable $\lambda_{i}\in\mathbb{R}$, and for the
constraint $z\leq\mathbf{1}$ take the dual vector $r\geq 0$. The constraints
thus obtained are:

$\displaystyle
l^{T}(-\mathbf{1}-z)+r^{T}(z-\mathbf{1})+z^{T}\sum_{i=1}^{k}\lambda_{i}w_{i}$
$\displaystyle\leq 0$ $\displaystyle\Leftrightarrow
z^{T}(\sum_{i=1}^{k}\lambda_{i}w_{i}+r-l)$
$\displaystyle\leq\mathbf{1}^{T}(r+l).$

So the dual LP is to minimize $\mathbf{1}^{T}(r+l)$ subject to $r,l\geq 0$ and
$\sum_{i=1}^{k}\lambda_{i}w_{i}+r-l=w$.

Before continuing, we make a brief comment on notation: to avoid confusion
with the vectors $w_{1},\ldots,w_{k}$, we label components of vectors
differently here. Namely, for $j\in[d]$ and a vector $u\in\mathbb{R}^{d}$, we
let $u(j)$ denote the $j$th entry of $u$.

Now let $v=\sum_{i=1}^{k}\lambda_{i}w_{i}$. $v$ ranges over $W$ as the
$\lambda_{i}$’s range over $\mathbb{R}$. Now temporarily fix the
$\lambda_{i}$’s and hence $v$. Then we require $l-r=v-w$ and we want to
minimize $\mathbf{1}^{T}(r+l)$. This is an independent problem for each
coordinate: in entries $j$ where $v(j)\geq w(j)$ it is optimal to take
$r(j)=0$ and $l(j)=v(j)-w(j)$, and in entries where $v(j)<w(j)$ it is optimal
to take $l(j)=0$ and $r(j)=w(j)-v(j)$. Either way we have
$l(j)+r(j)=|v(j)-w(j)|$, so we will have
$\mathbf{1}^{T}(r+l)=\sum_{j}|v(j)-w(j)|=||v-w||_{1}$. Thus the dual LP is
equivalent to minimizing $||v-w||_{1}$ subject to $v\in W$.

We now finish using the strong LP duality theorem [GW11]. The dual LP is
clearly bounded since its objective function is at least 0, and moreover it is
feasible since $v=0\in W$ is a feasible point for example. Thus the dual LP
has finite minimum which is $\min_{v\in W}||v-w||_{1}$, so strong duality
tells us that the primal LP also has the same value. This completes the proof
of the lemma.

###  B.6 Proof of Lemma 3.12

We apply a volume argument. Specifically, we estimate the size of
$(D+B_{\epsilon n})\cap\left\\{-1,1\right\\}^{n}$ using an $\ell_{1}$
$\epsilon$-net argument and show that this must be much less than $2^{n}$.
Since almost all $p\in\left\\{-1,1\right\\}^{n}$ satisfy
$|\mathbf{1}^{T}p|\leq 2\sqrt{n\log n}$ by concentration, some such $p$ will
not be covered by $D+B_{\epsilon n}$, as desired.

We now make this precise. Let $\lambda=\frac{1-\epsilon}{3}>0$ and let
$r=\lambda n$. Observe that $\epsilon+2\lambda<1$. We will prove the lemma
with an $\epsilon$-net argument. Let
$H^{\prime}=\left\\{p\in\left\\{-1,1\right\\}^{n}:|\mathbf{1}^{T}p|\leq
2\sqrt{n\log n}\right\\}$ and $H=[-1,1]^{n}$. Note that clearly
$H^{\prime}\subseteq H$. Also $D$ being a linear subspace is convex and
$B_{\epsilon n}$ being an $\ell_{1}$ ball is convex.

Suppose for the sake of contradiction that $H^{\prime}\subseteq D+B_{\epsilon
n}$. Let $S=(H+B_{\epsilon n})\cap D$. Note that $H^{\prime}\subseteq
S+B_{\epsilon n}$. This is because any $h\in H^{\prime}$ can be expressed as
$h=d+b$ where $d\in D$ and $b\in B_{\epsilon n}$. Then $d=h-b=h+(-b)\in
H^{\prime}+B_{\epsilon n}\subseteq H+B_{\epsilon n}$. But also we have $d\in
D$ so taking the intersection gives $d\in S$. Thus $h=d+b\in S+B_{\epsilon
n}$. This is true for all $h\in H^{\prime}$ so we have $H^{\prime}\subseteq
S+B_{\epsilon n}$ as claimed. The point of introducing $S$ is that it is a
finite piece of $D$ so now we can bound its volume (within $D$) from above.
Note also that $H,B_{\epsilon n}$ are convex so $H+B_{\epsilon n}$ is convex,
and since $D$ is also convex we have that $S$ is convex.

We bound $S$ above with a simpler set in order to estimate its $d$-dimensional
volume. For any point $x\in S$, we can write it as $h+b$ with $h\in H$ and
$b\in B_{\epsilon n}$. So we have $||x||_{1}\leq||h||_{1}+||b||_{1}\leq
n+\epsilon n=(1+\epsilon)n\Rightarrow x\in B_{(1+\epsilon)n}$. We also have
$S\subseteq D$ so we have $x\in D$. This implies that $S\subseteq
B_{(1+\epsilon)n}\cap D$. Call this larger set $T$. We hence have
$H^{\prime}\subseteq S+B_{\epsilon n}\subseteq T+B_{\epsilon n}$.

Now we apply the $\epsilon$-net argument. Let $x_{1},x_{2},\ldots,x_{k}$ be a
maximal subset of $T$ such that $||x_{i}-x_{j}||_{1}\geq 2r$ for all $i\neq
j$. We first show that $k$ cannot be too large, and then use this to upper
bound $|(D+B_{\epsilon n})\cap\left\\{-1,1\right\\}^{n}|$. For the upper bound
on $k$, we have the following:

######  Lemma B.1.

We have $k\leq\exp(\alpha^{\prime}\log(2(1+\epsilon)/\lambda)n)$.

###### Proof.

Note that the condition means that the $x_{i}+B_{r}=x_{i}+B_{\lambda n}$ are
pairwise almost disjoint. Hence we have:

$\displaystyle|T|$ $\displaystyle\geq\sum_{i=1}^{k}|(x_{i}+B_{\lambda n})\cap
T|,$

where $|\cdot|$ denotes volume in $D$. We next show for each $i$ that there
exists $y_{i}\in D$ such that $(x_{i}+B_{\lambda n})\cap
T\supseteq(y_{i}+B_{\lambda n/2})\cap D$. Note that the LHS is
$(x_{i}+B_{\lambda n})\cap B_{(1+\epsilon)n}\cap D$ so it suffices to show
that $(x_{i}+B_{\lambda n})\cap B_{(1+\epsilon)n}\supseteq y_{i}+B_{\lambda
n/2}$. This is intuitively clear but below is a formal proof:

Define the point $y_{i}$ as follows: if
$||x_{i}||_{1}\leq(1+\epsilon-\frac{\lambda}{2})n$ then let $y_{i}=x_{i}$.
Otherwise let
$y_{i}=(1+\epsilon-\frac{\lambda}{2})n\frac{x_{i}}{||x_{i}||_{1}}$. In other
words, $y_{i}$ is the same as $x_{i}$ but scaled down if necessary to have
$\ell_{1}$ norm at most $(1+\epsilon-\frac{\lambda}{2})n$. Note that this is
all well-defined since $1+\epsilon\geq 1\geq 2\lambda>\frac{\lambda}{2}$. We
check the three conditions we need $y_{i}$ to satisfy:

  * •

$y_{i}$ is a scalar multiple of $x_{i}$, so since $x_{i}\in T\subseteq D$ and
$D$ is a linear subspace we also have $y_{i}\in D$.

  * •

$y_{i}+B_{\lambda n/2}\subseteq B_{(1+\epsilon)n}$ is immediate from the
triangle inequality since $||y_{i}||_{1}\leq(1+\epsilon-\frac{\lambda}{2})n$.

  * •

$y_{i}+B_{\lambda n/2}\subseteq x_{i}+B_{\lambda n}$ would also follow from
the triangle inequality if we can show that $||y_{i}-x_{i}||_{1}\leq\lambda
n/2$. This is immediate in the case that $y_{i}=x_{i}$, and in the other case
we have
$||y_{i}-x_{i}||_{1}=||x_{i}||_{1}-||y_{i}||_{1}\leq(1+\epsilon)n-(1+\epsilon-\frac{\lambda}{2})n=\lambda
n/2$ as desired.

Thus our claim is proven. The next observation is that since $y_{i}\in D$ and
$D$ is a linear subspace, we have $(y_{i}+B_{\lambda n/2})\cap
D=y_{i}+(B_{\lambda n/2}\cap D)$. Finally, note that for any radius $t$, again
by linearity of $D$ we have $B_{t}\cap D=t(B_{1}\cap D)\Rightarrow|B_{t}\cap
D|=t^{d}|B_{1}\cap D|$. Putting this all together gives:

$\displaystyle((1+\epsilon)n)^{d}|B_{1}\cap D|$
$\displaystyle=|B_{(1+\epsilon)n}\cap D|$ $\displaystyle=|T|$
$\displaystyle\geq\sum_{i=1}^{k}|(x_{i}+B_{\lambda n})\cap T|$
$\displaystyle\geq\sum_{i=1}^{k}|(y_{i}+B_{\lambda n/2})\cap D|$
$\displaystyle=\sum_{i=1}^{k}|y_{i}+(B_{\lambda n/2}\cap D)|$
$\displaystyle=k|B_{\lambda n/2}\cap D|$ $\displaystyle=k(\lambda
n/2)^{d}|B_{1}\cap D|$ $\displaystyle\Leftrightarrow k$
$\displaystyle\leq(\frac{2(1+\epsilon)}{\lambda})^{d}$
$\displaystyle=\exp(d\log(2(1+\epsilon)/\lambda))$
$\displaystyle\leq\exp(\alpha^{\prime}\log(2(1+\epsilon)/\lambda)n),$

which proves the lemma. ∎

Now we complete our $\epsilon$-net argument using this lemma. Note that by
maximality, for any $x\in T$ there exists $i\in[k]$ such that
$||x-x_{i}||_{1}\leq 2r\Leftrightarrow x\in x_{i}+B_{2r}$. Hence
$T\subseteq\bigcup_{i=1}^{k}(x_{i}+B_{2r})$. From here, $|\cdot|$ denotes
cardinality rather than any kind of volume since it will only be applied to
finite and discrete sets. Thus we have:

$\displaystyle H^{\prime}$ $\displaystyle\subseteq T+B_{\epsilon n}$
$\displaystyle\subseteq(\bigcup_{i=1}^{k}(x_{i}+B_{2r}))+B_{\epsilon n}$
$\displaystyle\subseteq\bigcup_{i=1}^{k}(x_{i}+B_{2r+\epsilon n})$
$\displaystyle=\bigcup_{i=1}^{k}(x_{i}+B_{(\epsilon+2\lambda)n})$
$\displaystyle\Rightarrow H^{\prime}$
$\displaystyle\subseteq\bigcup_{i=1}^{k}((x_{i}+B_{(\epsilon+2\lambda)n})\cap
H^{\prime})$ $\displaystyle\Rightarrow|H^{\prime}|$
$\displaystyle\leq\sum_{i=1}^{k}|(x_{i}+B_{(\epsilon+2\lambda)n})\cap
H^{\prime}|$ $\displaystyle\Leftrightarrow\frac{|H^{\prime}|}{2^{n}}$
$\displaystyle\leq\sum_{i=1}^{k}\frac{|(x_{i}+B_{(\epsilon+2\lambda)n})\cap
H^{\prime}|}{2^{n}}$
$\displaystyle\leq\sum_{i=1}^{k}\frac{|(x_{i}+B_{(\epsilon+2\lambda)n})\cap\left\\{-1,1\right\\}^{n}|}{2^{n}}.$
(4)

The final step is to estimate both sides of (4) to get a contradiction. First
we address the LHS:

######  Lemma B.2.

We have $\frac{|H^{\prime}|}{2^{n}}\geq 1-2/n^{2}$.

###### Proof.

$\frac{|H^{\prime}|}{2^{n}}$ is exactly the probability that for $p$ chosen
uniformly at random in $\left\\{-1,1\right\\}^{n}$, we have
$|\mathbf{1}^{T}p|\leq 2\sqrt{n\log n}$. By Hoeffding’s inequality this is:

$\displaystyle 1-\Pr[|\mathbf{1}^{T}p|>2\sqrt{n\log n}]$
$\displaystyle=1-\Pr[|\sum_{j=1}^{n}p(j)|>2\sqrt{n\log n}]$
$\displaystyle=1-\Pr[|\frac{1}{n}\sum_{j=1}^{n}p(j)|>2\sqrt{\frac{\log
n}{n}}]$ $\displaystyle\geq 1-2\exp(-2n\cdot(4\log n/n)/4)$
$\displaystyle=1-2\exp(-2\log n)$ $\displaystyle=1-2/n^{2}.$

∎

Next we address the RHS of (4):

######  Lemma B.3.

For any $x\in\mathbb{R}^{n}$,
$\frac{|(x+B_{(\epsilon+2\lambda)n})\cap\left\\{-1,1\right\\}^{n}|}{2^{n}}\leq\exp(-n(1-\epsilon-2\lambda)^{2}/2)$.

###### Proof.

We make a brief comment on notation first: to avoid confusion with the vectors
$x_{1},\ldots,x_{k}$, we label components of vectors differently here. Namely,
for $j\in[n]$ and a vector $u\in\mathbb{R}^{n}$, we let $u(j)$ denote the
$j$th entry of $u$.

Now we turn to the lemma.
$\frac{|(x+B_{(\epsilon+2\lambda)n})\cap\left\\{-1,1\right\\}^{n}|}{2^{n}}$ is
the probability that for $p$ chosen uniformly at random in
$\left\\{-1,1\right\\}^{n}$, we have $||p-x||_{1}\leq(\epsilon+2\lambda)n$.

For each $j$, let $D_{j}$ be the distribution of $|p(j)-x(j)|$. The $D_{j}$’s
are all independent. Also define the distribution $D^{\prime}_{j}$ as follows:
if $x(j)\in[-1,1]$ let $D^{\prime}_{j}=D_{j}$, else let $D^{\prime}_{j}$ be
the uniform distribution on $\left\\{0,2\right\\}$. We claim that
$D^{\prime}_{j}$ satisfies two properties:

  1. 1.

$D_{j}$ and $D^{\prime}_{j}$ can be coupled such that a sample from $D_{j}$ is
greater than or equal to its coupled sample from $D^{\prime}_{j}$.

  2. 2.

$D^{\prime}_{j}$ is bounded in $[0,2]$ and has expectation 1.

First we check property 1. This is straightforward when $x(j)\in[-1,1]$ since
then samples can just be coupled to themselves. Next if $x(j)>1$ or $x(j)<-1$
\- assume WLOG that $x(j)>1$ by symmetry about 0 - $D_{j}$ is the uniform
distribution on $\left\\{x(j)-1,x(j)+1\right\\}$. We can couple $x(j)+1$ from
$D_{j}$ with $2$ from $D^{\prime}_{j}$ and $x(j)-1$ from $D_{j}$ with $0$ from
$D^{\prime}_{j}$ so this works.

Next we check property 2. This is clear when $|x(j)|>1$. In the other case,
$D^{\prime}_{j}$ is the uniform distribution on
$\left\\{1-x(j),1+x(j)\right\\}$. Indeed we have $0\leq 1-|x(j)|\leq|1\pm
x(j)|\leq 1+|x(j)|\leq 2$. Clearly $D^{\prime}_{j}$ has expectation 1. This
establishes our claim.

Thus we can proceed as follows, once again applying Hoeffding’s inequality:

$\displaystyle\Pr[||p-x||_{1}\leq(\epsilon+2\lambda)n]$
$\displaystyle=\Pr[\frac{1}{n}\sum_{j=1}^{n}|p(j)-x(j)|\leq\epsilon+2\lambda]$
$\displaystyle=\Pr_{a_{j}\sim D_{j}\text{,
indep.}}[\frac{1}{n}\sum_{j=1}^{n}a_{j}\leq\epsilon+2\lambda]$
$\displaystyle\leq\Pr_{a^{\prime}_{j}\sim D^{\prime}_{j}\text{,
indep.}}[\frac{1}{n}\sum_{j=1}^{n}a^{\prime}_{j}\leq\epsilon+2\lambda]$
$\displaystyle\leq\exp(-2n\cdot(1-\epsilon-2\lambda)^{2}/4)$
$\displaystyle=\exp(-n(1-\epsilon-2\lambda)^{2}/2),$

which yields the lemma. ∎

With the estimates from Lemmas B.2 and B.3, we can finish as follows:

$\displaystyle 1-2/n^{2}$ $\displaystyle\leq\frac{|H^{\prime}|}{2^{n}}$
$\displaystyle\leq\sum_{i=1}^{k}\frac{|(x_{i}+B_{(\epsilon+2\lambda)n})\cap\left\\{-1,1\right\\}^{n}|}{2^{n}}$
$\displaystyle\leq\sum_{i=1}^{k}\exp(-n(1-\epsilon-2\lambda)^{2}/2)$
$\displaystyle=k\exp(-n(1-\epsilon-2\lambda)^{2}/2)$
$\displaystyle\leq\exp(\alpha^{\prime}\log(2(1+\epsilon)/\lambda)n-n(1-\epsilon-2\lambda)^{2}/2)$
$\displaystyle=\exp((\alpha^{\prime}\log(\frac{2(1+\epsilon)}{\lambda})-\frac{(1-\epsilon-2\lambda)^{2}}{2})n).$

For this to hold for any $n$ sufficiently large, we must have
$\alpha^{\prime}\log(\frac{2(1+\epsilon)}{\lambda})-\frac{(1-\epsilon-2\lambda)^{2}}{2}\geq
0$ so it suffices to show that this isn’t the case. We do this as follows:

$\displaystyle\alpha^{\prime}\log(\frac{2(1+\epsilon)}{\lambda})-\frac{(1-\epsilon-2\lambda)^{2}}{2}$
$\displaystyle\leq\alpha^{\prime}(\frac{2(1+\epsilon)}{\lambda})-\frac{(1-\epsilon-2\lambda)^{2}}{2}$
$\displaystyle=\alpha^{\prime}(\frac{6(1+\epsilon)}{1-\epsilon})-\frac{(1-\epsilon)^{2}}{18}$
$\displaystyle<0,$

by definition of $\alpha^{\prime}$. This contradiction completes the proof of
Lemma 3.12.

###  B.7 Proof of Corollary 3.13

We have $\dim V\leq q+1=\alpha n+1<\alpha^{\prime}n$ for any
$\alpha^{\prime}\in(\alpha,\frac{(1-\epsilon)^{3}}{108(1+\epsilon)})$ and $n$
sufficiently large. Then all conditions of Lemma 3.12 apply so the lemma tells
us that there exists $p\in\left\\{-1,1\right\\}^{n}$ such that $p\notin
V+B_{\epsilon n}$ and $|\mathbf{1}^{T}p|\leq 2\sqrt{n\log n}$.

Since $p\in\left\\{-1,1\right\\}^{n}$, let $C\subseteq[n]$ be the cut such
that $u_{C}=p$ (i.e. $C$ is the set of indices where $p$ has an entry of 1).
Now note that

$\displaystyle\mathbf{1}^{T}u_{C}$ $\displaystyle=|C|-(n-|C|)$
$\displaystyle=2|C|-n.$

So we have:

$\displaystyle|\mathbf{1}^{T}u_{C}|$ $\displaystyle\leq 2\sqrt{n\log n}$
$\displaystyle\Leftrightarrow|2|C|-n|$ $\displaystyle\leq 2\sqrt{n\log n}$
$\displaystyle\Leftrightarrow||C|-\frac{n}{2}|$ $\displaystyle\leq\sqrt{n\log
n}$ $\displaystyle\Leftrightarrow|C|$
$\displaystyle\in[\frac{n}{2}-\sqrt{n\log n},\frac{n}{2}+\sqrt{n\log n}].$

Thus $C$ is a near-max cut. Moreover we have $u_{C}\notin V+B_{\epsilon n}$ so
this completes the proof of this corollary and thus Theorem 3.5.

##  Appendix C Lemmas from Section 3.3

###  C.1 Proof of Lemma 3.15

We use the notation “$(b\pm c)$” to denote some number in $[b-c,b+c]$. Also,
since $E(B)=E(\overline{B})$, the problem is invariant under replacing $B$
with $\overline{B}$ so assume WLOG that $|B|\geq n/2$.

Note that $|A|$ is the sum of $n$ i.i.d. random 0/1 variables that are each 1
with probability 1/2. Hence by Hoeffding’s inequality we have
$\Pr[|A|\notin(\frac{1}{2}\pm\epsilon)n]\leq 2\exp(-2\epsilon^{2}n)$. Also,
every vertex in $B$ also belongs to $A$ with probability $\frac{1}{2}$ and
this selection is independent. Thus we similarly have $\Pr[|A\cap
B|\notin(\frac{1}{2}\pm\epsilon)|B|]\leq 2\exp(-2\epsilon^{2}|B|)\leq
2\exp(-\epsilon^{2}n)$. Taking a union bound, we have:

$\displaystyle\Pr[|A|\in(\frac{1}{2}\pm\epsilon)n\text{ and }|A\cap
B|\in(\frac{1}{2}\pm\epsilon)|B|]$ $\displaystyle\geq
1-2\exp(-2\epsilon^{2}n)-2\exp(-\epsilon^{2}n)$ $\displaystyle\geq
1-4\exp(-\epsilon^{2}n).$

We next turn our attention to estimating $\frac{|E(A)\cap E(B)|}{|E(A)|}$
assuming the event inside the LHS is true. First, we have:

$\displaystyle|E(A)|$ $\displaystyle=|A|(n-|A|)$
$\displaystyle=\frac{1}{4}n^{2}-(|A|-\frac{n}{2})^{2}$
$\displaystyle\geq(\frac{1}{4}-\epsilon^{2})n^{2}.$

Now for the numerator, note that for $(i,j)$ to be in both $E(A)$ and $E(B)$
we must have either that one vertex is in $A\cap B$ and the other is in
$\overline{A}\cap\overline{B}$, or that one vertex is in $A\cap\overline{B}$
and the other is in $\overline{A}\cap B$. Let $a=|A|$, $b=|B|$, and $t=|A\cap
B|$. Then we have:

$\displaystyle|A\cap\overline{B}|$ $\displaystyle=a-t$
$\displaystyle|\overline{A}\cap B|$ $\displaystyle=|B|-|A\cap B|$
$\displaystyle=b-t$ $\displaystyle|\overline{A}\cap\overline{B}|$
$\displaystyle=|\overline{A}|-|\overline{A}\cap B|$
$\displaystyle=(n-a)-(b-t)$ $\displaystyle=n-a-b+t.$

Thus we have:

$\displaystyle|E(A)\cap E(B)|$ $\displaystyle=(a-t)(b-t)+t(n-a-b+t)$
$\displaystyle=(t^{2}-t(a+b)+ab)+(t^{2}-t(a+b)+tn)$
$\displaystyle=2t^{2}+t(n-2a-2b)+ab$
$\displaystyle=2(t^{2}+t(\frac{n}{2}-a-b)+\frac{ab}{2})$
$\displaystyle=2((t+\frac{n}{4}-\frac{a+b}{2})^{2}+\frac{ab}{2}-(\frac{n}{4}-\frac{a+b}{2})^{2})$
$\displaystyle=2((t+\frac{n}{4}-\frac{a+b}{2})^{2}+\frac{ab}{2}-\frac{n^{2}}{16}-\frac{(a+b)^{2}}{4}+\frac{n(a+b)}{4})$
$\displaystyle=2((t+\frac{n}{4}-\frac{a+b}{2})^{2}-\frac{n^{2}}{16}+\frac{a(n-a)}{4}+\frac{b(n-b)}{4}).$

We estimate each piece of this as follows:

$\displaystyle\frac{a(n-a)}{4}$
$\displaystyle\leq\frac{(a+(n-a))^{2}}{16}\text{ (AM-GM/Cauchy-Schwarz)}$
$\displaystyle=\frac{n^{2}}{16}$ $\displaystyle\frac{b(n-b)}{4}$
$\displaystyle\leq\frac{n^{2}}{16}\text{ (similarly)}$
$\displaystyle(t+\frac{n}{4}-\frac{a+b}{2})^{2}$
$\displaystyle=|t+\frac{n}{4}-\frac{a+b}{2}|^{2}$
$\displaystyle\leq(|t-\frac{b}{2}|+\frac{1}{2}|\frac{n}{2}-a|)^{2}$
$\displaystyle\leq(\epsilon b+\frac{1}{2}\epsilon n)^{2}$
$\displaystyle\leq(\frac{3}{2}\epsilon n)^{2}$
$\displaystyle=\frac{9}{4}\epsilon^{2}n^{2}.$

Combining these gives:

$\displaystyle|E(A)\cap E(B)|$ $\displaystyle\leq
2(\frac{9}{4}\epsilon^{2}n^{2}-\frac{n^{2}}{16}+\frac{n^{2}}{16}+\frac{n^{2}}{16})$
$\displaystyle=2(\frac{9}{4}\epsilon^{2}n^{2}+\frac{n^{2}}{16})$
$\displaystyle=(\frac{1+36\epsilon^{2}}{8})n^{2}.$

Putting this together with our estimate of $|E(A)|$ gives:

$\displaystyle\frac{|E(A)\cap E(B)|}{|E(A)|}$
$\displaystyle\leq\frac{(\frac{1+36\epsilon^{2}}{8})n^{2}}{(\frac{1}{4}-\epsilon^{2})n^{2}}$
$\displaystyle=\frac{1+36\epsilon^{2}}{2-8\epsilon^{2}}$ $\displaystyle<c,$

by our choice of $\epsilon$. Thus we have:

$\displaystyle\Pr[\frac{|E(A)\cap E(B)|}{|E(A)|}<c]$
$\displaystyle\geq\Pr[|A|\in(\frac{1}{2}\pm\epsilon)n\text{ and }|A\cap
B|\in(\frac{1}{2}\pm\epsilon)|B|]$ $\displaystyle\geq 1-4\exp(-\epsilon^{2}n)$
$\displaystyle\Rightarrow\Pr[\frac{|E(A)\cap E(B)|}{|E(A)|}\geq c]$
$\displaystyle\leq 4\exp(-\epsilon^{2}n),$

which completes the proof of the lemma.

###  C.2 Proof of Theorem 3.14

We make our intuitive approach precise by defining the following random
variables:

  * •

$R$: the sequence of query results given to the algorithm

  * •

$C$: the cut output by the algorithm

  * •

$I$: an indicator that is 1 if 1 if $C$ achieves a $c$-approximation and 0
otherwise.

Step 1 is straightforward: each query’s result is an integer in
$[0,\binom{n}{2}]$ since all edges in our graph are 0 or 1 and hence has
entropy at most $2\lg n$. Thus $H(R)\leq 2q\lg n$. Moreover since we are
assuming the algorithm is deterministic, $C$ is a deterministic function of
$R$ so we have $H(C)\leq H(R)\leq 2q\lg n$. This yields the following lower
bound on $H(A\mid C)$:

$\displaystyle H(A\mid C)$ $\displaystyle=H(A,C)-H(C)$ $\displaystyle\geq
H(A,C)-2q\lg n$ $\displaystyle=H(C\mid A)+H(A)-2q\lg n$ $\displaystyle\geq
H(A)-2q\lg n$ $\displaystyle=n-2q\lg n.$

It remains to formalize step 2 by upper bounding $H(A\mid C)$. We proceed very
similarly to the proof of Fano’s inequality [CT06]; indeed, if the success
condition for the algorithm was “$C=A$” rather than “$C$ approximately agrees
with $A$”, then Fano’s inequality would be directly applicable. We apply a
similar bounding argument as follows:

$\displaystyle H(A\mid C)$ $\displaystyle=H(A\mid C)+H(I\mid A,C)\text{ ($I$
is fixed given $A$ and $C$)}$ $\displaystyle=H(I,A\mid C)$
$\displaystyle=H(A\mid I,C)+H(I\mid C)$ $\displaystyle\leq H(A\mid I,C)+1$
$\displaystyle=H(A\mid C,I=1)\Pr[I=1]+H(A\mid C,I=0)\Pr[I=0]+1$
$\displaystyle\leq(H(A\mid C,I=1)-n)\Pr[I=1]+n+1$ ($A$ is supported on a set
of size $2^{n}$ so its entropy conditioned on anything is $\leq n$)
$\displaystyle\leq(H(A\mid C,I=1)-n)p+n+1\text{ ($\Pr[I=1]\geq p$, and
$H(A\mid C,I=1)\leq n$)}$ $\displaystyle=H(A\mid C,I=1)p+n(1-p)+1.$

Now observe that $H(A\mid C,I=1)=\mathbb{E}_{B\sim\mu_{C\mid I=1}}H(A\mid
C=B,I=1)$, where $\mu_{C\mid I=1}$ denotes the marginal distribution of $C$
conditioned on $I=1$. Temporarily fix $B$ and consider the distribution of $A$
conditioned on $C=B$ and $I=1$. Since we are conditioning on $I=1$, the value
of the cut defined by $B$ must be at least $c|E(A)|$. But the value of this
cut is exactly $|E(A)\cap E(B)|$.

Thus Corollary 3.16 tells us that there are at most $2^{n}\cdot
4\exp(-\epsilon^{2}n)$ sets $A$ that can appear with positive probability in
this distribution. Then it follows that:

$\displaystyle H(A\mid C=B,I=1)$ $\displaystyle\leq\lg(2^{n}\cdot
4\exp(-\epsilon^{2}n))$ $\displaystyle=n+2-\epsilon^{2}(\lg e)n$
$\displaystyle=(1-\epsilon^{2}(\lg e))n+2.$

Taking the expectation over $B$ again gives $H(A\mid
C,I=1)\leq(1-\epsilon^{2}(\lg e))n+2$. Plugging this in gives:

$\displaystyle H(A\mid C)$ $\displaystyle\leq H(A\mid C,I=1)p+n(1-p)+1$
$\displaystyle\leq((1-\epsilon^{2}(\lg e))n+2)p+n(1-p)+1$
$\displaystyle=n(1-p+p(1-\epsilon^{2}\lg e))+2p+1$
$\displaystyle=n(1-p\epsilon^{2}\lg e)+2p+1.$

Finally, putting together our two bounds on $H(A\mid C)$ gives:

$\displaystyle n(1-p\epsilon^{2}\lg e)+2p+1$ $\displaystyle\geq n-2q\lg n$
$\displaystyle\Leftrightarrow q$ $\displaystyle\geq\frac{n\cdot
p\epsilon^{2}\lg e-2p-1}{2\lg n}$ $\displaystyle=\frac{n}{\log
n}(\frac{p\epsilon^{2}}{2}-o(1)),$

which proves the theorem.

##  Appendix D Lemmas from Section 3.4

###  D.1 Proof of Lemma 3.18

For every vertex $a\in[n]$, we can assign it a $q$-bit string as follows: the
$b$th bit indicates which side of the cut $Q_{b}$ $a$ is placed on. We thus
define a partition of the $n$ vertices into $2^{q}$ buckets. $(i,j)$ crosses
some queried cut if and only if $i$ and $j$ have distinct bit-strings i.e.
they belong to distinct buckets. Let $B=2^{q}$ and let the $B$ buckets have
sizes $n_{1},n_{2},\ldots,n_{B}$. Noting that $(i,j)$ is chosen uniformly at
random, we have the following:

$\displaystyle\Pr[(i,j)\text{ never crossed}]$
$\displaystyle=\frac{2}{n(n-1)}\sum_{b=1}^{B}\binom{n_{b}}{2}$
$\displaystyle=\frac{1}{n(n-1)}\sum_{b=1}^{B}(n_{b}^{2}-n_{b})$
$\displaystyle=\frac{1}{n(n-1)}((\sum_{b=1}^{B}n_{b}^{2})-n)$
$\displaystyle\geq\frac{1}{n(n-1)}(\frac{1}{B}(\sum_{b=1}^{B}n_{b})^{2}-n)(\text{Cauchy-
Schwarz})$ $\displaystyle=\frac{1}{n(n-1)}(\frac{n^{2}}{B}-n)$
$\displaystyle=\frac{1}{n-1}(\frac{n}{B}-1)$
$\displaystyle=\frac{1}{n-1}(\frac{n}{2^{q}}-1)$
$\displaystyle=\frac{n-2^{q}}{2^{q}(n-1)},$

which completes the proof of the lemma.

###  D.2 Proof of Corollary 3.19

Suppose the algorithm uses $q$ queries. Then this algorithm must achieve a
$c$-approximation with probability 1, so Theorem 3.17 tells us that we must
have:

$\displaystyle 1$ $\displaystyle\leq 1-\frac{n-2^{q}}{2^{q+1}(n-1)}$
$\displaystyle\Leftrightarrow\frac{n-2^{q}}{2^{q+1}(n-1)}$ $\displaystyle\leq
0$ $\displaystyle\Rightarrow q$ $\displaystyle\geq\lg n,$