The Communication Complexity of Local Search

Introduction

In the context of computational complexity, local search problems are captured by the complexity class PLS [Johnson et al., 1988] which is a subset of the well studied class TFNP (defined in [Megiddo and Papadimitriou, 1991] and studied, e.g., in [Papadimitriou et al., 1990, Beame et al., 1998, Daskalakis et al., 2009, Hubácek et al., 2017]): search problems for which a witness always exists (“total search problems”) and can by efficiently verified (“in NP”). The problem has also been widely studied in the model of query complexity where the cost of an algorithm is the number of black-box queries to the objective function $f$, from the pioneering work of [Aldous, 1983] on the Boolean hypercube, to a rather complete characterization of not only the deterministic query complexity but also the randomized and even quantum complexities on any graph [Santha and Szegedy, 2004, Aaronson, 2006, Sun and Yao, 2009].

Definition: For a fixed, commonly known graph $G=(V,E)$, the $\textsc{SumLS}(G)$ communication problem is the following: Alice holds a function $f_{A}:V\rightarrow\{1,...,W\}$, Bob holds a function $f_{B}:V\rightarrow\{1,...,W\}$, and their goal is to find a vertex $v^{*}\in V$ such that $f_{A}(v^{*})+f_{B}(v^{*})\geq f_{A}(u)+f_{B}(u)$ for all $u\in V$ with $(v^{*},u)\in E$.

Determining the communication complexity of SumLS on certain families of graphs is easy. For example, a simple reduction from disjointness shows that the communication complexity of SumLS on the clique with $n$ vertices is $\Omega(n)$. Our main theorem proves optimal lower bounds for several important families of graphs, all have small degree. The technical challenge is that the non-deterministic communication complexity of the problem on small degree graphs is clearly low: to verify that $v^{*}$ is a local optimum, Alice and Bob need only communicate the values $f(u)$ and $g(u)$ for the small number of $v^{*}$’s neighbours in the graph (note that the degree of all graphs that we consider is indeed small: $\log N$ or even constant). There are only a few results in the communication complexity literature that manage to prove good lower bounds for total problems where verification is easy, most notably for Karchmer-Wigderson games [Karchmer and Wigderson, 1990, Karchmer et al., 1995, Raz and McKenzie, 1997] and for PPAD-like communication problems [Babichenko and Rubinstein, 2016, Göös and Rubinstein, 2018].

The communication complexity of local search on the $n$-dimensional hypercube with $N=2^{n}$ vertices is $\Omega(\sqrt{N})$.

The communication complexity of local search on a constant-dimension grid with $N$ vertices is $\Omega(\sqrt{N})$.

The communication complexity of local search on a specific family of constant degree graphs with $N$ vertices is $\Omega(\sqrt{N})$.

The communication complexity of local search on the odd graph with $N$ vertices is $\Omega(\sqrt{N})$.

We note that all our bounds hold for randomized communication complexity. Interestingly, the first three bounds are optimal: first, since for these families of graphs an algorithm by Aldous finds a local optimum with $O(\sqrt{N})$ queries in expectation, which clearly implies an analogous communication algorithm with the same efficiency.

Our proof starts from considering the communication variant of a pebbling game Göös and Pitassi . $D=(V,E)$ is a known directed acyclic graph. The input is a boolean assignment for the vertices $b:V\rightarrow\{0,1\}$ such that every source is true ($b(v)=1$) and every sink is false ($b(v)=0$). The output is a false vertex whose all predecessors are true (i.e., $v\in V$ such that $b(v)=0$ and $b(u)=1$ for all $u\in V$, $(u,v)\in E$). [Göös and Pitassi, 2014] consider the communication variant of the game which is obtained by distributing the information $b(v)\in\{0,1\}$ of every vertex by a constant size index-gadget $\{0,1\}^{3}\times\rightarrow\{0,1\}$. They show that for some constant-degree graph $D$ with $N$ vertices the communication complexity of the problem is $\Theta(\sqrt{N})$, which is optimal.

Our proof is composed of three steps. The first step shows how to reduce the pebbling game to a variant of local search on a graph $G$ (VetoLS) where Alice holds the function $f$ and Bob holds a set of valid vertices. The goal is to find a local maximum in the subgraph that is composed of the valid vertices.

The second step is the most technically challenging one. We first define a notion of embedding one graph to the other, and show that if a graph $G$ can be embedded into $H$ then the communication of $\textsc{VetoLS}(H)$ is at least that of $\textsc{VetoLS}(H)$. We then show that the graph $G$ obtained in the previous step can be embedded into each of the families considered in the theorem. This embedding is quite delicate and uses specifics properties of the graph $G$, since the number of vertices of $G$ and $H$ must be almost the same, in order to obtain an optimal bound of $\Omega(\sqrt{N})$ for $\textsc{VetoLS}(H)$, where $N$ is the number of vertices of $H$.

Finally, in the third step we show that the communication complexity of VetoLS on any graph is at least that of local search, thus establishing the theorem.

The constants that are obtained in our theorem are quite big (the dimension of the grid has to be at least $119$, and the degree of the constant degree graph is $36$). Thus, we also provide an alternative proof that obtains better constants, at the cost of a worse communication bound. Specifically, we show that there exists a specific family of $4$-degree graphs for which the communication complexity of local search is $\Omega(N^{c})$ for some constant $c>0$. We also show a lower bound of the form $\Omega(N^{c})$ for the three dimensional grid $N\times N\times 2$. The alternative proof uses the more recent and more generic “simulation” lemmas that “lift” lower bounds from the query complexity setting to the communication complexity setting [Göös et al., 2017, 2015, Raz and McKenzie, 1997], instead of the “simulation” lemma of [Göös and Pitassi, 2014] that was developed for specific settings like the pebbling game. The main technical difficulty that we overcome is that the “combination gadgets” used in these lemmas (specifically the index function) are very different from the simple sum that we desire.

We now describe two applications of our basic lower bound. In both applications we study communication variants of problems that are known to be PLS complete, have low non-deterministic complexity and, as we show, high communication complexity.

The communication requirements for reaching various types of equilibria in different types of games have received a significant amount of recent interest (Babichenko and Rubinstein , Göös and Rubinstein ) as they essentially capture the convergence time of arbitrary dynamics in scenarios where each player only knows his own utilities (“uncoupled dynamics” [Hart and Mas-Colell, 2003, Hart and Mansour, 2010]) and must “learn” information about the others. Of particular importance here is the class of potential games [Monderer and Shapley, 1996].

The class of exact potential games includes, in particular, all congestion games. A key property of potential games (exact or ordinal) is that every sequence of better responses converges to an equilibrium and therefore every potential game always has a pure Nash equilibrium.

[Hart and Mansour, 2010] study the communication complexity of pure Nash equilibrium in ordinal potential games. They consider $n$-player games where each player has four actions and show (by a reduction from disjointness) that exponential communication is required to distinguish between the case where the game is an ordinal potential game (and thus has a Nash equilibrium) and the case where the game is not a potential game and does not admit any Nash equilibrium. This immediately implies that finding an equilibrium in games that are guaranteed to have one takes $exp(n)$ bits of communication.

Does finding an equilibrium become any easier for exact potential games? In [Nisan, 2009b] it was shown that exponentially many queries are needed to find an equilibrium, but maybe in the communication model the problem becomes much easier. The technical challenge is again that the non-deterministic communication complexity of the problem is low, i.e, verifying that a certain profile is a Nash equilibrium does not require much communication (each player only has to make sure that he plays his best response). Nevertheless, we provide a ray of hope and show that in contrast to ordinal potential games, there is a randomized protocol that uses only $\textsf{polylog}(|A|)$ (when $|A|=|A_{1}|\cdot...\cdot|A_{n}|$ is the game size) bits of communication and determines whether the game is an exact potential game or not.

We then show that although it is easy to recognize whether a game is an exact potential game or not, finding an equilibrium requires polynomial (in the size of the game) communication (and in particular exponential in the number of players). These results provide a negative answer to an open question posed in [Nisan, 2009a].

For some constant $c>0$, the following problem requires at least $N^{c}$ communication (even randomized): Alice gets an $N\times N$ matrix $u_{A}$ and Bob gets an $N\times N$ matrix $u_{B}$, they are promised that the game defined by these matrices is an (exact) potential game and they must output a pure Nash equilibrium of the game.

For some constant $c>0$, the following problem requires at least $2^{cn}$ communication (even randomized): Alice gets the utility functions of the first $n$ players in a $2n$-player $2$-action game. Bob gets the utility functions of the last $n$ players. They are promised that the game defined by these matrices is an (exact) potential game and they must output a pure Nash equilibrium of the game.

Our proofs are via reductions from local search on (certain) degree 4 graphs in the two-player $N$-action case, and from local search on the hypercube in the $2n$-player 2-action case. While the relation between equilibria of potential games and local maxima is well known and very simple, the reduction is actually quite subtle. First the neighbourhood structures do not naturally match (in the two-player case), but more crucially the input to the players here is very limited: only very specifically related matrices $u_{A}$ and $u_{B}$ give an (exact) potential game, while the lower bounds for local search were for arbitrary inputs.

We also show that the search for a pure Nash equilibrium in exact potential games can be formulated as a total search problem: Either find a pure Nash equilibrium (that is guaranteed to exist in exact potential games) or provide a succinct evidence that the game is not an exact potential game. Interestingly such a succinct evidence of violation of exact potential property is guaranteed to exist by [Monderer and Shapley, 1996]. As an immediate corollary from our results we deduce hardness of this total search problem.

2 Local Optima in Combinatorial Auctions

Our second application concerns attempts to weaken the global optimality constraints in market allocations. Consider a combinatorial auction of $m$ indivisible items among $n$ players, each with his own valuation function $v_{i}$ that gives a real value to every subset of the items. The usual goal of optimizing social welfare aims to globally maximize $\sum_{i}v_{i}(S_{i})$ over all allocations $(S_{1},...,S_{n})$ of the items.

A corresponding notion of equilibrium is the Walrasian equilibrium, which includes also a vector of prices $p_{1},...,p_{m}$ such that every player receives his globally-optimal set of items at these prices. While these notions provide very strong guarantees, they are usually “too good to be true”: Walreasian equilibria only rarely exist and optimizing social welfare is usually infeasible, in essentially any sense of the word, and in particular in the sense of requiring exponential communication [Nisan and Segal, 2006].

Several papers have tried to relax the notion of a Walrasian equilibrium or similarly view the allocation problem as a game and analyze the equilibria in this game. In particular, in the model of simultaneous second price auctions [Christodoulou et al., 2008] it is easy to see that when the valuations are submodular every allocation that is locally optimal can be part of an equilibrium in the game, and the same goes for the endowed equilibrium of [Babaioff et al., 2018]. Recall that a locally optimal allocation in a combinatorial auction is an allocation of the items $(S_{1},\ldots,S_{n})$ such that transferring any single item $j\in S_{i}$ to some other player $i^{\prime}$ does not improve the welfare.

Since local optima play a central role in various relaxed notions of equilibria, an obvious question is whether they are easy to find. In [Babaioff et al., 2018] it is shown that for some succinctly represented submodular valuations it is PLS hard to compute a locally optimal allocation in combinatorial auction. Furthermore, in the query model it is shown that finding a locally optimal allocation is as hard as finding a local maximum in the odd graph. Combining the same reduction with our communication hardness of local search on the odd graph, we get that:

The communication complexity of finding a locally optimal allocation between two players with submodular valuations is $2^{\Omega(n)}$.

Local Search over Graphs

In this section we provide communication lower bounds on the communication complexity of local search over several families of graphs.

The following bound holds for the randomized communication complexity of SumLS:

$CC(\textsc{SumLS}(G))=\Omega(\sqrt{N})$, when $G$ is a specific constant-degree (36) graph with $N$ vertices.

$CC(\textsc{SumLS}(\textsf{Hyp}_{n}))=\Omega(\sqrt{N})=\Omega(2^{n/2})$ where $N=2^{n}$ is the number of vertices.

$CC(\textsc{SumLS}(H)=\Omega(\sqrt{N})$, when $H$ is a grid with a constant dimension (119) grid with $N$ vertices.

$CC(\textsc{SumLS}(\textsf{Odd}_{n}))=\Omega(2^{n/2})$.

We note that results 1, 2, and 3 are optimal since Aldous provides a randomized algorithm that finds a local maximum in these graph using $O(\sqrt{N})$ value queries. Result 4, on the other hand, is not necessarily optimal because the odd graph has $N\approx 4^{n}$ vertices, so in terms of the number of vertices our lower bound is $\Omega(\sqrt{N})$.

Result 3 proves an optimal bound for a grid with a constant dimension, but this dimension is quite large (119). We are able to show that finding a local optimum in the three-dimensional grid is hard, but our lower bound in this case is only $\Omega(N^{c})$, for some constant $c>0$ (in contrast to an optimal bound of $\Omega(\sqrt{N})$ for the $119$-dimensional grid). To prove this, we first show that finding a local maximum is hard even for degree $4$ graphs.

There exists a constant $c>0$ such that the randomized communication complexity of SumLS satisfies:

$CC(\textsc{SumLS}(G))\geq N^{c}$, when $G$ is a specific degree 4 graph with $N$ vertices.

$CC(\textsc{SumLS}(\textsf{Grid}_{N\times N\times})=N^{c}$.

The overall structure of the proofs of Theorems 2.1 and 2.2 is similar, but the proofs use different techniques. The proof of Theorem 2.1 appears in Section 3 and the proof of Theorem 2.2 appears in Section 4.

Proof of Theorem 2.1

Our starting point is a communication variant of a pebbling game. In this problem, $D=(V,E)$ is a known directed acyclic graph. The input is a boolean assignment for the vertices $b:V\rightarrow\{0,1\}$ such that every source is true ($b(v)=1$) and every sink is false ($b(v)=0$). The output is a false vertex whose all predecessors are true (i.e., $v\in V$ such that $b(v)=0$ and $b(u)=1$ for all $u\in V$, $(u,v)\in E$). Note that the problem is total.

The communication variant of the pebbling game Pebb(D) is defined by distributing the information $b(v)\in\{0,1\}$ of every vertex by a constant size index-gadget $\{0,1\}^{3}\times\rightarrow\{0,1\}$.

In [Göös and Pitassi, 2014] it is shown that there exists a constant degree graph $D$ with $N$ vertices where both the randomized communication complexity of the problem is $\Theta(\sqrt{N})$. The proof is done in three steps.

We introduce an intermediate communication problem $\textsc{VetoLS}(G)$ where Alice holds the potential function and Bob holds a subset of valid vertices (equivalently, Bob vetoes the vertices that are not in the set that he holds). The goal is to find a valid local maximum: a valid vertex whose valid neighbours have (weakly) lower potential. Given a graph $D$ as above, we construct a constant degree graph $G$ with $O(N)$ vertices and reduce Peb(D) to $\textsc{VetoLS}(G)$. This gives us an optimal communication lower bound for VetoLS for a concrete graph $G$.

We define a certain notion of “embedding” of one graph into the other. We show that if $G^{\prime}$ can be embedded in $G$, then $CC(\textsc{VetoLS}(G^{\prime}))\geq CC(\textsc{VetoLS}(G))$. We use this observation to prove optimal hardness bound of VetoLS over the hypercube by embedding $G$ into an hypercube of dimension $\log(N)+c$ for a constant $c$.

For every graph $G$, we show that $CC(\textsc{VetoLS}(G))\approx CC(\textsc{SumLS}(G))$.

We now provide a detailed description of each step.

1 Starting Point: Pebbling Games

In Section 3.3 we use the concrete structure of the constant degree graph $D$ for which the hardness of the pebbling game is proved. Hence, we start with providing an explicit description of the graph $D$.

The vertices of $D$ are given by $V=[M^{3}]\times[M]\times[M]\times[M]$. Each vertex $v=(k_{1},k_{2},k_{3},k_{4})$ has six successors:

where the $\pm 1$ addition in the last three coordinates is done modulo $M$. The addition in the first coordinate is the standard addition. Thus, each vertex has six predecessors:

The sources of the graph are $\{(1,\cdot,\cdot,\cdot)\}$ and its sinks are $\{(M^{3},\cdot,\cdot,\cdot)\}$.

In [Göös and Pitassi, 2014] an optimal bound on the communication complexity is proved the following optimal bound on the communication of the following variant of pebbling games. In the communication problem $\textsc{Pebb}(D)$, Alice’s input is an assignment $b:V\times\rightarrow\{0,1\}$. Bob’s input is an index for each vertex $I:V\rightarrow$. The input satisfies $b(v,I(v))=1$ for every source $v$, and $b(v,I(v))=0$ for every sink $v$. The output is a vertex $v\in S$ such that $b(v,I(v))=0$ and for every predecessor $u$ of $v$ holds $b(u,I(u))=1$.

$CC(\textsc{Pebb}(D))=\Omega(M^{3})$. This bound also holds for randomized protocols.

2 Step 1: From Pebbling to VetoLS

Given a graph $G$, the communication problem $\textsc{VetoLS}(G)$ is defined as follows. Alice’s input is a function $f:V\rightarrow[W]$. Bob’s input is a non-empty subset $S\subset V$. The output is a vertex $v\in S$ such that $f(v)\geq f(w)$ for every $w\in S$ such that $\{v,w\}\in E$ (i.e., for every valid neighbour). We show that the communication complexity of $\textsc{VetoLS}(G)$ is at least that of $\textsc{Pebb}(D)$, for some $G$ that is related to $D$. Next we show how to obtain the graph $G$ from $D$.

We construct the graph $G$ in two stages. First, given a graph $D$ of the pebbling game, let $G^{\prime}$ be an undirected version of $D$ which additionally has an edge from every source of $D$ to some sink of $D$. Let $G$ be the graph that is obtained from $G^{\prime}$ by replacing each vertex in $G$ with three new vertices and duplicating the edges so that each new vertex is connected to all the copies of its neighbors in $G^{\prime}$. We call the graph $G$ the replication graph of $D$.

Let $D$ be a graph and $G$ be its replication graph. The communication complexity of $\textsc{VetoLS}(G)$ is at least that of $\textsc{Pebb}(D)$.

Alice’s input in $\textsc{Pebb}(D)$ is an assignment $b:V\times\rightarrow\{0,1\}$. We use this to define the potential function $f$ that Alice holds in $\textsc{VetoLS}(G)$: for vertex $v\in V^{\prime}$ let $f(v)=t(v)+6N\mathds{1}_{b(v)=0}$. Bob’s input in $\textsc{Pebb}(D)$ is the function $I:V\rightarrow$. Bob defines the set of valid vertices in $\textsc{VetoLS}(G)$ to be $S=\{(v,I(v)):v\in V\}$. Namely, among the three copies of $v$ only the one with correct index is valid. This choice of valid vertices has the desirable property that the subgraph of valid vertices is precisely $G^{\prime}$ and the assignment $b(v,i)$ over the vertices of $G^{\prime}$ is precisely the decomposed assignment $b(v,I(v))$.

We argue that the local maxima of $f$ are precisely all false vertices whose all incoming neighbours are true. Those are indeed local maxima, because their “predecessors” do not have the bonus of $6N$ and their “successors” have lower topological number. The source cannot be a local maximum because it is a “true” vertex and it is connected to a sink that is a “false” vertex. A true vertex (other than source) is not local maximum because its predecessor has higher topological number. Similarly, a false vertex with false predecessor is not local maximum. This leaves us only with false vertices whose predecessors are true. ∎

3 Step 2: Embedding the Bounded Degree Graph

In this step we define a certain notion of embedding of one graph into another. We will see that if a graph $G$ can be embedded into $H$ then the communication complexity of local search on $H$ is essentially at least as large as the communication complexity of local search on $G$. We will then see how to embed the graph $G$ of the previous steps into the three dimensional grid, the hypercube, and the odd graph.

A vertex-isolated edge-disjoint (VIED) embedding of a graph $G=(V_{G},E_{G})$ in a graph $H=(V_{H},E_{H})$ is a pair of mappings $\varphi:V_{G}\rightarrow V_{H}$ and $\chi:E_{G}\rightarrow P(H)$, where $P(H)$ is the set of simple paths on $H$, such that:

For every edge $\{v,w\}\in E_{G}$, the path $\chi(\{v,w\})$ connects $\varphi(v)$ to $\varphi(w)$.

The interior vertices of the paths $\chi(\{v,w\})$ and $\chi(\{v^{\prime},w^{\prime}\})$ are disjoint (edge disjointness).

For every $v\in V_{G}$ and every $\{w,w^{\prime}\}\in E_{G}$ such that $v\neq w,w^{\prime}$ holds $d(\varphi(v),\chi(\{w,w^{\prime}\}))\geq 2$, where $d$ denotes the distance in $H$ of the vertex from the path (vertex isolation).

That is, in a VIED embedding every edge of $G$ is replaced by a path in $H$ that connects the corresponding vertices such that these paths do not share a vertex. Moreover, for every $v\in V_{G}$, $\varphi(v)$ is isolated in the sense that no path passes through the neighbours of $\varphi(v)$.

Let $G$ be a graph and suppose it can be VIED embedded into some other graph $H$. Then $CC(\textsc{VetoLS}(G))\leq CC(\textsc{VetoLS}(H))$.

Alice’s potential is defined as follows. For vertices $w\in\varphi(V_{G})$ we define $f_{H}(\varphi(v))=f_{G}(v)$. Consider a vertex $w\in\chi(E_{G})$ that belongs to an edge $\{u,v\}\in E_{G}$. Suppose that $w$ is the $k$’th element in the path $\chi(\{u,v\})$ and $l$ is the total length of this path. Define:

In all other vertices Alice’s potential will not play a role because these vertices will not be valid, thus we can simply set $f_{H}(w)\equiv 0$ for all other vertices.

We recall that Bob’s input in $\textsc{VetoLS}(G)$ is $S_{G}\subset V_{G}$. We denote by $E_{G}(S_{G})\subset E_{G}$ the set of internal edges of $S_{G}$. Bob’s subset of valid vertices in $H$ is defined byBy $\chi(E_{G}(S_{G}))$ we obviously mean the corresponding vertices in these paths. $S_{H}=\varphi(S_{G})\cup\chi(E_{G}(S_{G}))$.

If $v\in V_{G}$ is a valid local maximum, then $\varphi(v)\in V_{H}$ is a valid local maximum because all its valid neighbours are valid edges in which $v$ participates (here we use the isolation property), and the value along these edges is a weighted average of $f_{G}(v)$ and $f_{G}(u)\leq f_{G}(v)$, where $u$ is a valid neighbour of $v$.

We argue that there are no additional valid local maxima in $H$. Indeed, if $v\in V_{G}$ is not a local maximum then $\varphi(v)\in V_{H}$ is not a local maximum because there is a valid edge where the potential increases. If $w\in\chi(E_{G}(S_{G}))$, by distinctness, $f_{G}(u)\neq f_{G}(v)$ therefore in one of the directions of the path $\chi(\{u,v\})$ the potential increases. All other vertices are invalid. ∎

In the embeddings we use the specifics of the DAG $D$ for which the hardness of pebbling games is proved in Göös and Pitassi . We now explicitly describe the replication graph $G$ that is obtained from $D$ so that Proposition 3.2 can be applied.

Let $G^{\prime}$ be the undirected version of the DAG $D$ for which the hardness of pebbling games is proved with additional edges that connect the sources and sinks of $D$ in a same way other vertices in $D$ are connected. Formally, the vertices of $G^{\prime}$ are $V=[M^{3}]\times[M]\times[M]\times[M]$, and the edges are:

Let $G$ be the graph that is obtained from $G^{\prime}$ by replacing each vertex in $G$ with three new vertices and duplicating the edges so that each new vertex is connected to all the copies of its neighbors in $G^{\prime}$. Formally, the vertices of $G$ are $\{(v,i):v\in V,i\in\}$ and the edges are $\{((u,i),(v,j)):(u,v)\in E,i,j\in\}$. Note that $G$ is a graph with $3M^{6}$ vertices and (constant) degree $d=36$.

3.2 Embedding into the Hypercube

In this section we show how to embed the replication graph $G$ obtained in the previous step into the hypercube. Moreover, the embedding is such that the number of vertices in the hypercube increases only by a constant factor. This small blowup is crucial for obtaining an optimal $2^{n/2}$ bound.

The graph $G$ (with $3M^{6}$ vertices) can be VIED-embedded into the $n$’th-dimensional hypercube $\textsf{Hyp}_{n}$ for $n=6\lceil\log M\rceil+111$. As a corollary, $CC(\textsc{VetoLS}(\textsf{Hyp}_{n}))=\Omega(2^{n/2})$.

For clarity of exposition we assume that $M=2^{c}$ is a power of 2. We start with some notations and properties of the graph $G$. Recall that the vertices of $G$ are $V=[M^{3}]\times[M]\times[M]\times[M]\times$. For a vertex $v=(k_{1},k_{2},k_{3},k_{4},i)$, $k_{1}$ is called the layer of $v$. Note that all edges connect $k$ layer vertices to $k+1$ layer vertices. $k_{1}+k_{2}+k_{3}+k_{4}\mod 2$ is called the parity of $v$. $i$ is called the replication index of $v$. We present an edge coloring of $G$ with $108$ colors in which no two adjacent edges are colored the same (a “valid” coloring). We first color all edges from layer 1 to layer 2 with $54$ colors. Given a vertex $v=(k_{2},k_{3},k_{4})$, edges are specified by a displacement $d\in\{\pm 1,0,0),(0,\pm 1,0),(0,0,\pm 1)\}$ that operates on $(k_{2},k_{3},k_{4})$ and pair of replication indices $i,j\in$ ($i$ is the replication index of the vertex at layer $1$ and $j$ is the replication index of the vertex at layer $2$). Note that we have $6\cdot 9=54$ such specifications. It is easy to verify that coloring these edges in $54$ different colors is a valid edge coloring. We proceed by coloring all edges between layers $2$ and $3$ with different $54$ colors using a similar coloring method. Similarly, all edges from layer $2k-1$ to layer $2k$ are colored as edges between layers $1$ and $2$ and all edges from layer $2k$ to layer $2k+1$ are colored as edges between layers $2$ and $3$. This defines an edge coloring of $G$.

Now we present some notation. The vertices of the hypercube are partitioned into blocks as follows:

For $i=1,...,5$ the $i$’th index block consists of bits that represent the $i$’th index. The sizes of the blocks are $(3c,c,c,c,2)$ for $i=1,2,3,4,5$ correspondingly.

A parity bit memorizes the parity of a vertex.

The counter block consists of $3$ bits that serves as a counter to keep track of the block on which we currently apply the changes along the embedding path (see below).

Let $(h_{1},...,h_{M^{3}})$ be a Hamiltonian path of the $3c$-dimensional hypercube. Let $(h^{\prime}_{1},...,h^{\prime}_{M})$ be a Hamiltonian path of the $c$-dimensional hypercube and $(h^{\prime\prime}_{1},...,h^{\prime\prime}_{4})$ be a Hamiltonian path of the $2$-dimensional hypercube. To define $\phi(v)$, we embed a vertex $v=(k_{1},k_{2},k_{3},k_{4},i)$ into the vertex of the hypercube whose first block is the bits of $h_{k_{1}}$, the second block is $h^{\prime}_{k_{2}}$, then $h^{\prime}_{k_{3}}$, $h^{\prime}_{k_{4}}$ and $h^{\prime\prime}_{k_{5}}$. We set the parity bit to be the parity of $v$, the edge block to 0, and the counter block to 0.

Note that the coloring of $G$ in $108$ colors naturally induces an order on the edges. Every vertex has at most one $m$’th edge, and two adjacent vertices agree on the index of this edge. The $m$’th edge of $v$, from $v$ in layer $k_{1}$ to $u$ in layer $k_{1}+1$, is defined by the following sequence of bit flipping.

The $m$’th bit in the edge block is flipped to 1.

A single bit in the counter block is flipped to encode the integer 1.

A single bit in the first index block is flipped to encode the integer $k_{1}+1$.

A single bit in the counter block is flipped to encode the integer 2.

If the displacement of the edge is $(\pm 1,0,0)$, a single bit in the second index block is flipped to encode the integer $k_{2}\pm 1$. If the displacement of the edge is $(0,\pm 1,0)$, a single bit in the third index block is flipped to encode the integer $k_{3}\pm 1$. If the displacement of the edge is $(0,0,\pm 1)$, a single bit in the fourth index block is flipped to encode the integer $k_{3}\pm 1$.

A single bit in the counter block is flipped to encode the integer 3.

The two bits of the fifth index block are flipped (one by one in a fixed order) to encode the integer $j$ (the replication index of $u$).

The $m$’th bit in the edge block is flipped back to 0.

It is easy to see that this path ends up at $\phi(u)$ (note that the parity of $v$ and $u$ is the same, and indeed we did not flip the parity bit). We argue that the defined paths are disjoint. It is sufficient to prove that given a node on the path one can recover the previous node. Given the color of the edge and the counter, it is immediate to recover the previous node in all intermediate steps excluding steps (3) and (5). In steps (3) and (5) it is unclear whether we should flip the corresponding index block or the counter block. To determine this we use the parity bit: In step (3), if the parity bit is equal to the parity of the encoded vertices, then it means that we did not flip yet a bit, and to get the previous vertex we set the counter block to encode 0. If the parity bit differs from the parity of the encoded indices, then it means that we have flip a bit, and to get the previous vertex we should flip a bit in the index block. In step (5) we do the opposite. If the parity bit differs from the parity of the encoded indices, then we flip the counter. If the parity bit is equal to the parity of the encoded indices, then we flip the index block.

It is easy to check that the embedding is vertex isolated because of the parity bit.

3.3 Embedding into the Grid

The graph $G$ (with $3M^{6}$ vertices) can be VIED-embedded in a constant-dimension grid with $O(M^{6})$ vertices. As a corollary, $CC(\textsc{VetoLS}(\textsf{Grid}_{d}))=\Omega(\sqrt{N})$ for some constant-dimension grid with $N$ vertices.

(sketch) The embedding is very similar to the one we presented in Lemma 3.5 for embedding into the hypercube. In the proof of Lemma 3.5 we only used the fact that the hypercube has an Hamiltonian cycle. For the grid, we will take advantage of the observation that the two-dimensional grid has an Hamiltonian cycle.

Specifically, a vertex $v=(k_{1},k_{2},k_{3},k_{4},i)$ is embedded into the vertex of the grid whose first block is the bits of that correspond to a Hamiltonian cycle on $\textsf{Grid}_{M^{1.5}\times M^{1.5}}$, blocks $2-4$ are specified using the Hamiltonian cycle on $\textsf{Grid}_{M^{0.5}\times M^{0.5}}$, and block $5$ using the Hamiltonian cycle on $\textsf{Grid}_{2}\times\textsf{Grid}_{2}$. We set the parity bit to be the parity of $v$, the edge block to 0, and the counter block to 0. Applying very similar arguments to the proof of Lemma 3.5 we establish the embedding of $G$ into the grid $[M^{1.5}]^{2}\times[M^{0.5}]^{6}\times^{111}$. ∎

3.4 Embedding into the Odd Graph

There exists a VIED embedding of $\textsf{Hyp}_{n}$ in $\textsf{Odd}_{n+2}$. As a corollary, $CC(\textsc{VetoLS}(\textsf{Odd}_{n}))=\Omega(2^{n/2})$.

We first embed $\textsf{Hyp}_{n}$ in $\textsf{Hyp}_{n+1}$ simply by $\phi_{1}(v)=(v,0)$ and $\chi_{1}(\{v,w\})=\{(v,0),(w,0)\}.$ Obviously this embedding is edge disjoint (but not vertex isolated).

We now embed $\textsf{Hyp}_{n+1}$ in $\textsf{Odd}_{n+2}$. We refer to each vertex of $\textsf{Hyp}_{n+1}$ as a subset $S\subset[n+1]$. We denote $S+n+1=\{i+n+1:i\in S\}$. We denote $T^{c}=[n+1]\setminus T$ (this notation will be relevant for subsets of $[n+1]$ rather than subsets of $[2n+3]$ as the vertices of $\textsf{Odd}_{n+2}$). The embedding is defined by

It is easy to check that this indeed defines a valid path on $\textsf{Odd}_{n+2}$. All the defined paths are disjoint because given a vertex on a path $T\cup(T^{\prime}+n)\cup\{2n+3\}$ we can identify the edge: $S=T^{\prime}$ and $i$ is the unique element that is missing from both sets $T$ and $T^{\prime}$.

Now we define the embedding of $\textsf{Hyp}_{n}$ in $\textsf{Odd}_{n+2}$ to be the decomposition of these two embeddings; I.e., $\phi(v)=\phi_{2}(\phi_{1}(v))$ and $\chi(e)=\chi_{2}(\chi_{1}(e))$. The embedding $(\phi,\chi)$ is edge disjoint because both embeddings $(\phi_{1},\chi_{1})$ and $(\phi_{2},\chi_{2})$ are edge disjoint. Now we prove that $(\phi,\chi)$ is vertex isolated. A vertex $\phi_{2}(\phi_{1}(v))=S\cup(S^{c}+2n)$ has $n+2$ neighbours in $\textsf{Odd}_{n+2}$. Among these neighbours, $n+1$ participate in an embedding of the outgoing edges of $S\in\textsf{Hyp}_{n+1}$. So there is a single neighbour, $S^{c}\cup(S+n+1)$, who is suspected to belong to an embedding of an independent edge. Note that $S^{c}\cup(S+n+1)=\phi_{2}(S^{c})$ and $S^{c}\in\textsf{Hyp}_{n+1}$ does not belong to the embedding of $\textsf{Hyp}_{n}$ in $\textsf{Hyp}_{n+1}$: indeed, for every vertex $v\in\textsf{Hyp}_{n}$ the complementary vertex $\overline{(v,0)}=(\overline{v},1)\in\textsf{Hyp}_{n+1}$ does not belong to the embedding of $\textsf{Hyp}_{n}$ in $\textsf{Hyp}_{n+1}$ (neither to $\phi_{1}(V_{\textsf{Hyp}_{n}})$ nor to $\chi_{1}(E_{\textsf{Hyp}_{n}})$). ∎

4 Step 3: From VetoLS to SumLS

First, recall that the potential function gets values in $[W]$. We reduce the problem $\textsc{VetoLS}(G)$ to $\textsc{SumLS}(G)$. Alice’s potential remains unchanged (i.e., $f_{A}(v):=f_{G}(v)$). Bob fixes some valid vertex $v^{*}\in S$ and sets his potential as follows: $f_{B}(v):=0$ if $v\in S$, otherwise he sets $f_{B}(v)=-d(v,v^{*})\cdot(W+1)$, where $d$ is the distance in $G$. Indeed every valid local maximum $v$ is a local maximum of the sum because all the valid neighbours have lower sum of potentials $f_{A}(v)+f_{B}(v)=f_{G}(v)\geq f_{G}(w)=f_{A}(v)+f_{B}(v)$ and all invalid neighbours have negative sum of potentials $f_{A}(w)+f_{B}(w)\leq W-(W+1)<0$. It is easy to check that every valid vertex that is not a local maximum is not a local maximum of the sum. Finally, every invalid vertex $v$ is not a local maximum of the sum because the neighbour $w$ in the direction of the shortest path to $v^{*}$ has higher sum of potentials:

We apply this reduction on the graphs considered in Lemmas 3.6, 3.5 and 3.7 to deduce the theorem.

Proof of Theorem 2.2

The overall structure of the proof is similar to that of Theorem 2.1.

We start with a local-search-related communicationally-hard problem over some graph $H$.

We use the intermediate problem $\textsc{VetoLS}(G)$, where $G$ is constructed from $H$.

We embed $G$ in the three-dimensional grid.

We reduce $\textsc{VetoLS}(\textsf{Grid})$ to $\textsc{SumLS}(\textsf{Grid})$.

However, in order to be able to embed $G$ in the three-dimensional grid, the degree of $G$ should be very low; at most 6. The pebbling game result of [Göös and Pitassi, 2014] does not serve our purposes because the degree of the graph $G$ is 36. Hence, our starting point is some different local-search-related communicationally hard problem over some degree 3 graph $H$. In Step 1, we carefully modify $H$ to $G$ by increasing the degree only by 1; i.e., $G$ is degree 4 graph. Now, in Step 2 we are able to embed $G$ in the three-dimensional grid. Step 3 is identical to that in the proof of Theorem 2.1.

1 Step 0: The Query Complexity of Local Search and its Simulated Variant

In the problem $\textsc{QuLS}(H)$ there is a graph $H$ and a function $h$ that gives a value $h(v)$ for every vertex. The function $h$ can only be accessed via queries $h(v)$. Furthermore, for each two vertices $v,u$ are distinct: $h(v)\neq h(u)$. The goal is to find a local maximum of $h$ while minimizing the number of queries.

Santha and Szegedy [Santha and Szegedy, 2004] introduced a general connection between the query complexity of the local search problem and the expansion of a graph. Since random $3$-regular graphs are expanders with high probability, we have that there exists a degree 3 graph $H$ with $N$ vertices for which finding a local maximum requires $\textsf{poly}(N)$ queries. However, their construction does not assume that $h(v)\neq h(u)$ for every two vertices $v$ and $u$. This is easy to fix: let $h^{\prime}(v)=2N\cdot h(v)+v$ (where $v\in[N]$ denotes the index of $v$). Observe that each local maximum of $h^{\prime}$ is also a local maximum of $h$ and that the query $h^{\prime}(v)$ can be computed by one query $h(v)$, so the number of queries required to find a local maximum of $h^{\prime}$ is at least the number of queries required to find a local maximum of $h$. We therefore have:

There exists a degree 3 graph $H$ with $N$ vertices and a function $h^{\prime}$ such that every vertex has a distinct value for which finding a local maximum requires $\textsf{poly}(N)$ queries.

The simulation theorems provides us a recipe to produce problems with high communication complexity, given a problem with high query complexity. In particular, [Göös et al., 2017, Anshu et al., 2017] suggest the index-gadget recipe, which starting from $\textsc{QuLS}(H)$ is translated to the following communication problem $\textsc{SimLS}(H)$: for each vertex $v\in H$, Alice holds an array of valuations $(f(v,i))_{i\in[M]}$ where $f(v,I(v))=h(v)$ andE.g., $M=N^{256}$ in [Göös et al., 2017]. $M=\textsf{poly}(N)$. Bob holds the correct index $I(v)\in[M]$. Their goal is to compute a local maximum of the function $f(v,I(v))$. Direct application of the simulation theorems to our setting gives that:

2 Step 1: The Communication Complexity of VetoLS

In this step we prove the communication hardness of VetoLS on a certain bounded degree graph. We recall the definition of $\textsc{VetoLS}(G)$. Alice’s input is a function $f_{G}:V\rightarrow[W]$. Bob’s input is a non-empty subset $S\subset V$. The output is a vertex $v\in S$ such that $f_{G}(v)\geq f_{G}(w)$ for every $w\in S$ such that $\{v,w\}\in E$ (i.e., for every valid neighbour).

Unlike the communication pebbling game problem that uses index gadgets of size 3, the simulated QuLS problem uses gadgets of size $M=\textsf{poly}N$ ($N$ is the number of vertices of $G$). The idea in the proof of Theorem 2.1 is to replicate each vertex according to the gadget size, and connect every vertex with all its replicated neighbours. This idea is impractical here, because the degree of the resulting graph will be huge. Instead, we replace each replicated vertex with degree $3M$ by a carefully chosen binary tree structure in order to reduce the degree.

Without loss of generality we assume that $M=2^{a}$ is a power of 2. We obtain our graph $G$ by replacing every vertex $v\in H$ by a tuple of $M$ graphs $(T^{out}(v,i)\cup T^{in}(v,i))_{i\in M}$, where $T^{out}(v,i)\cup T^{in}(v,i)$ denotes two binary trees with an overlapping root, both of depth $\log(M^{3})=3a$ (see Figure 1). Roughly speaking, the role of $T^{out}(v,i)$ is to decode the correct indices of the three neighbours, and in parallel to split the outgoing edges from $v_{i}$. The role of $T^{in}(v,i)$ is simply to gather the incoming edges into $v_{i}$.

More formally, the vertices of $T^{out}(v,i)$ at depth $d$ are denoted by $(t_{s}(v,i))_{s\in\{0,1\}^{d}}$. The vertices of $T^{in}(v,i)$ at depth $d$ are denoted by $(t^{\prime}_{s}(v,i))_{s\in\{0,1\}^{d}}$. The vertices at depth $3a$ will be called leavesNote that they are leaves only with respect to the tree. In the graph $G$ they will not be leaves.. As was mentioned above, the vertex at depth 0 of these two trees coincides (i.e., $t_{\emptyset}(v,i)=t^{\prime}_{\emptyset}(v,i)$). Now we describe how the leaves of $T^{out}(v,i)$ connect to the leaves of $T^{in}(w,j)$ for $w\neq v$. For a leaf $t_{s}(v,i)\in T^{out}(v,i)$ we denote $s=(j_{1},j_{2},j_{3})$ where $j_{1},j_{2},j_{3}\in[M]$ are the indices of the three neighbors of $v$, $w_{1},w_{2},w_{3}$. The leaf $t_{s}(v,i)\in G$ has a single edge to the tree $T^{in}(w_{1},j_{1})$, a single edge to the tree $T^{in}(w_{2},j_{2})$, and a single edge to the tree $T^{in}(w_{3},j_{3})$ (see Figure 1). In principle, we should specify which leaf exactly in $T^{in}(w_{1},j_{1})$ is connected to $t_{s}(v,i)$. However, since it will not play any role in our arguments, we just implement a counting argument to ensure that the number of neighbours from other trees of every leaf $t^{\prime}_{s^{\prime}}(w,j)$ is at most 3. If $w$ has a neighbour $v$, then for every $i\in[M]$ exactly $M^{2}$ vertices $t_{s}(v,i)$ will encode the index $j$. So from $T^{out}(v,i)$ we have $M\cdot M^{2}=M^{3}$ incoming edges. Summing over the 3 neighbours we get $3M^{3}$ incoming edges. If we distribute them equally among the $M^{3}$ vertices, we get 3 neighbours for each.

Alice’s potential function is defined by $f_{G}(t^{\prime}_{s}(v,i))=7af(v,i)+3a-|s|$ and $f_{G}(t_{s}(v,i))=7af(v,i)+3a+|s|$. Namely the potential in the tree $T^{\prime}_{s}(v,i)$ starts at a value of $7af(v,i)$ in the leaves of $T^{in}(v,i)$. It increases by $1$ after every edge until it gets to the root. At the root we move to the tree $T^{out}(v,i)$ where it proceeds to increase by $1$ until it gets to the leaves of $T^{out}(v,i)$ where the value of the potential is $7af(v,i)+6a$.

Now we define the subset of valid vertices $S$ held by Bob. Let $bin(i)\in\{0,1\}^{a}$ denote the binary representation of an index $i\in[M]$. We denote by $nbin(v)=(bin(I(w_{i})))_{i=1,2,3}$ the binary representation of the triple of $v$’s neighbours. For a binary string $b$ we denote by $b_{[k]}$ its first $k$ elements. A vertex $t_{s}(v,i)\in S$ iff $i=I(v)$ and $s=nbin(v)_{[|s|]}$ (recall that $I(v)$ is Bob’s input in SimLS). Informally speaking the valid vertices are those where the tree $T^{out}(v,i)$ (or $T^{in}(v,i)$) has the correct index, and if the vertex is in $T^{out}(v,i)$ we require, in addition, that the prefix of the encoding of the neighbours’ indices will be correct.

Since the potential of Alice increases starting from the leaves of $T^{in}(v,i)$ and ending at the leaves of $T^{out}(v,i)$, and in addition for every valid vertex there exists a valid neighbour with higher (lower) depth in $T^{out}(v,i)$ (in $T^{in}(v,i)$) the valid local maxima appear only on the leaves of $T^{out}(v,i)$. Every valid leaf of $T^{out}(v,i)$ has a potential of $7af(v,I(v))+6a$ (i.e., the correct potential) and is connected to leaves of $T^{in}(w_{j},I(w_{j}))$ for $j=1,2,3$ with a potential of $7af(w_{j},I(w_{j}))$ (i.e., the correct potential of the neighbours). Note that the potential values are integers. Therefore, $7af(v,I(v))+6a\geq 7af(w,I(w))$ if and only if $f(v,I(v))\geq f(w,I(w))$. Hence, there is a one-to-one correspondence between valid local maxima of $f_{G}$ with respects to the set if valid vertices $S$ and local maxima of $h$ over $H$.

This completes the proof item 1 of the Theorem.

3 Step 2: Embedding the Degree 4 Graph Into the Grid

We VIED embed (see Definition 3.3) the degree 4 graph $G$ obtained in the previous step into the grid. We use Lemma 3.4 to deduce hardness of VetoLS over the grid.

Every degree 4 graph $G$ with $N$ vertices can be VIED-embedded in $\textsf{Grid}_{4N\times(2N+2)\times 2}$. As a corollary, $CC(\textsc{VetoLS}(\textsf{Grid}_{N\times N\times 2}))=\textsf{poly}(N)$.

We embed the graph $G$ in the grid whose vertices are $\{3,4,...,4N+2\}\times\{-1,0,...,2N\}\times\{0,1\}$. We denote the vertices of $G$ by $\{v_{i}\}_{i\in[N]}$ and we embed $\phi(v_{i})=(4i,0,0)$. We use (for instance) the structure of Figure 2 to place the four outgoing edges of $(4i,0,0)$ at the points $(4i-1,1,0),(4i,1,0),(4i+1,1,0)$ and $(4i+2,1,0)$.

We denote by $\{e_{i}\}_{i\in[m]}$ the edges in the graph $G$. Note that $m\leq 4N/2=2N$ because the graph degree is 4. The embedding of the edges is by an increasing order $e_{1},...,e_{m}$. For an edge $e_{i}=(v_{j},v_{k})$ let $r_{j}\in\{-1,0,1,2\}$ be the minimal index such that the vertex $(4j+r_{j},1,0)$ is not yet used by previous edges $\{e_{i^{\prime}}\}_{i^{\prime}<i}$. Similarly we define $r_{k}$. The edge $e_{i}=(v_{j},v_{k})$ is embedded to the path: