
In this paper we improve the deterministic complexity of two fundamental
communication primitives in the classical model of adhoc radio networks with
unknown topology: broadcasting and wakeup. We consider an unknown radio
network, in which all nodes have no prior knowledge about network topology, and
know only the size of the network $n$, the maximum indegree of any node
$\Delta$, and the eccentricity of the network $D$.
For such networks, we first give an algorithm for wakeup, based on the
existence of small universal synchronizers. This algorithm runs in
$O(\frac{\min\{n, D \Delta\} \log n \log \Delta}{\log\log \Delta})$ time, the
fastest known in both directed and undirected networks, improving over the
previous best $O(n \log^2n)$time result across all ranges of parameters, but
particularly when maximum indegree is small.
Next, we introduce a new combinatorial framework of block synchronizers and
prove the existence of such objects of low size. Using this framework, we
design a new deterministic algorithm for the fundamental problem of
broadcasting, running in $O(n \log D \log\log\frac{D \Delta}{n})$ time. This is
the fastest known algorithm for the problem in directed networks, improving
upon the $O(n \log n \log \log n)$time algorithm of De Marco (2010) and the
$O(n \log^2 D)$time algorithm due to Czumaj and Rytter (2003). It is also the
first to come within a loglogarithmic factor of the $\Omega(n \log D)$ lower
bound due to Clementi et al.\ (2003).
Our results also have direct implications on the fastest \emph{deterministic
leader election} and \emph{clock synchronization} algorithms in both directed
and undirected radio networks, tasks which are commonly used as building blocks
for more complex procedures.

The \emph{beep model} is a very weak communications model in which devices in
a network can communicate only via beeps and silence. As a result of its weak
assumptions, it has broad applicability to many different implementations of
communications networks. This comes at the cost of a restrictive environment
for algorithm design.
Despite being only recently introduced, the beep model has received
considerable attention, in part due to its relationship with other
communication models such as that of adhoc radio networks. However, there has
been no definitive published result for several fundamental tasks in the model.
We aim to rectify this with our paper.
We present algorithms and lower bounds for a variety of fundamental global
communications tasks in the model.

In this paper we present a framework for leader election in multihop radio
networks which yield randomized leader election algorithms taking
$O(\text{broadcasting time})$ in expectation, and another which yields
algorithms taking fixed $O(\sqrt{\log n})$times broadcasting time. Both
succeed with high probability.
We show how to implement these frameworks in radio networks without collision
detection, and in networks with collision detection (in fact in the strictly
weaker beep model). In doing so, we obtain the first optimal expectedtime
leader election algorithms in both settings, and also improve the worstcase
running time in directed networks without collision detection by an $O(\sqrt
{\log n})$ factor.

We initiate the study of property testing in arbitrary planar graphs. We
prove that bipartiteness can be tested in constant time, improving on the
previous bound of $\tilde{O}(\sqrt{n})$ for graphs on $n$ vertices. The
constanttime testability was only known for planar graphs with bounded degree.
Our algorithm is based on random walks. Since planar graphs have good
separators, i.e., bad expansion, our analysis diverges from standard techniques
that involve the fast convergence of random walks on expanders. We reduce the
problem to the task of detecting an oddparity cycle in a multigraph induced by
constantlength cycles. We iteratively reduce the length of cycles while
preserving the detection probability, until the multigraph collapses to a
collection of easily discoverable selfloops.
Our approach extends to arbitrary minorfree graphs. We also believe that our
techniques will find applications to testing other properties in arbitrary
minorfree graphs.

For over a decade now we have been witnessing the success of {\em massive
parallel computation} (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or
Spark. One of the reasons for their success is the fact that these frameworks
are able to accurately capture the nature of largescale computation. In
particular, compared to the classic distributed algorithms or PRAM models,
these frameworks allow for much more local computation. The fundamental
question that arises in this context is though: can we leverage this additional
power to obtain even faster parallel algorithms?
A prominent example here is the {\em maximum matching} problemone of the
most classic graph problems. It is well known that in the PRAM model one can
compute a 2approximate maximum matching in $O(\log{n})$ rounds. However, the
exact complexity of this problem in the MPC framework is still far from
understood. Lattanzi et al. showed that if each machine has $n^{1+\Omega(1)}$
memory, this problem can also be solved $2$approximately in a constant number
of rounds. These techniques, as well as the approaches developed in the follow
up work, seem though to get stuck in a fundamental way at roughly $O(\log{n})$
rounds once we enter the nearlinear memory regime. It is thus entirely
possible that in this regime, which captures in particular the case of sparse
graph computations, the best MPC round complexity matches what one can already
get in the PRAM model, without the need to take advantage of the extra local
computation power.
In this paper, we finally refute that perplexing possibility. That is, we
break the above $O(\log n)$ round complexity bound even in the case of {\em
slightly sublinear} memory per machine. In fact, our improvement here is {\em
almost exponential}: we are able to deliver a $(2+\epsilon)$approximation to
maximum matching, for any fixed constant $\epsilon>0$, in $O((\log \log n)^2)$
rounds.

We study two fundamental communication primitives: broadcasting and leader
election in the classical model of multihop radio networks with unknown
topology and without collision detection mechanisms.
It has been known for almost 20 years that in undirected networks with n
nodes and diameter D, randomized broadcasting requires Omega(D log n/D + log^2
n) rounds in expectation, assuming that uninformed nodes are not allowed to
communicate (until they are informed). Only very recently, Haeupler and Wajc
(PODC'2016) showed that this bound can be slightly improved for the model with
spontaneous transmissions, providing an O(D log n loglog n / log D + log^O(1)
n)time broadcasting algorithm. In this paper, we give a new and faster
algorithm that completes broadcasting in O(D log n/log D + log^O(1) n) time,
with high probability. This yields the first optimal O(D)time broadcasting
algorithm whenever D is polynomial in n.
Furthermore, our approach can be applied to design a new leader election
algorithm that matches the performance of our broadcasting algorithm.
Previously, all fast randomized leader election algorithms have been using
broadcasting as their subroutine and their complexity have been asymptotically
strictly bigger than the complexity of broadcasting. In particular, the fastest
previously known randomized leader election algorithm of Ghaffari and Haeupler
(SODA'2013) requires O(D log n/D min{loglog n, log n/D} + log^O(1) n)time with
high probability. Our new algorithm requires O(D log n / log D + log^O(1) n)
time with high probability, and it achieves the optimal O(D) time whenever D is
polynomial in n.

We present a new, distributed method to compute approximate Nash equilibria
in bimatrix games. In contrast to previous approaches that analyze the two
payoff matrices at the same time (for example, by solving a single LP that
combines the two players payoffs), our algorithm first solves two independent
LPs, each of which is derived from one of the two payoff matrices, and then
compute approximate Nash equilibria using only limited communication between
the players.
Our method has several applications for improved bounds for efficient
computations of approximate Nash equilibria in bimatrix games. First, it yields
a best polynomialtime algorithm for computing \emph{approximate wellsupported
Nash equilibria (WSNE)}, which guarantees to find a 0.6528WSNE in polynomial
time. Furthermore, since our algorithm solves the two LPs separately, it can be
used to improve upon the best known algorithms in the limited communication
setting: the algorithm can be implemented to obtain a randomized
expectedpolynomialtime algorithm that uses polylogarithmic communication and
finds a 0.6528WSNE. The algorithm can also be carried out to beat the best
known bound in the query complexity setting, requiring $O(n \log n)$ payoff
queries to compute a 0.6528WSNE. Finally, our approach can also be adapted to
provide the best known communication efficient algorithm for computing
\emph{approximate Nash equilibria}: it uses polylogarithmic communication to
find a 0.382approximate Nash equilibrium.

We study the problem of recognizing the cluster structure of a graph in the
framework of property testing in the bounded degree model. Given a parameter
$\varepsilon$, a $d$bounded degree graph is defined to be $(k,
\phi)$clusterable, if it can be partitioned into no more than $k$ parts, such
that the (inner) conductance of the induced subgraph on each part is at least
$\phi$ and the (outer) conductance of each part is at most
$c_{d,k}\varepsilon^4\phi^2$, where $c_{d,k}$ depends only on $d,k$. Our main
result is a sublinear algorithm with the running time
$\widetilde{O}(\sqrt{n}\cdot\mathrm{poly}(\phi,k,1/\varepsilon))$ that takes as
input a graph with maximum degree bounded by $d$, parameters $k$, $\phi$,
$\varepsilon$, and with probability at least $\frac23$, accepts the graph if it
is $(k,\phi)$clusterable and rejects the graph if it is $\varepsilon$far from
$(k, \phi^*)$clusterable for $\phi^* = c'_{d,k}\frac{\phi^2
\varepsilon^4}{\log n}$, where $c'_{d,k}$ depends only on $d,k$. By the lower
bound of $\Omega(\sqrt{n})$ on the number of queries needed for testing graph
expansion, which corresponds to $k=1$ in our problem, our algorithm is
asymptotically optimal up to polylogarithmic factors.

The $\varepsilon$wellsupported Nash equilibrium is a strong notion of
approximation of a Nash equilibrium, where no player has an incentive greater
than $\varepsilon$ to deviate from any of the pure strategies that she uses in
her mixed strategy. The smallest constant $\varepsilon$ currently known for
which there is a polynomialtime algorithm that computes an
$\varepsilon$wellsupported Nash equilibrium in bimatrix games is slightly
below $2/3$. In this paper we study this problem for symmetric bimatrix games
and we provide a polynomialtime algorithm that gives a
$(1/2+\delta)$wellsupported Nash equilibrium, for an arbitrarily small
positive constant $\delta$.

We present sublineartime (randomized) algorithms for finding simple cycles
of length at least $k\geq 3$ and treeminors in boundeddegree graphs. The
complexity of these algorithms is related to the distance of the graph from
being $C_k$minorfree (resp., free from having the corresponding treeminor).
In particular, if the graph is far (i.e., $\Omega(1)$far) {from} being
cyclefree, i.e. if one has to delete a constant fraction of edges to make it
cyclefree, then the algorithm finds a cycle of polylogarithmic length in time
$\tildeO(\sqrt{N})$, where $N$ denotes the number of vertices. This time
complexity is optimal up to polylogarithmic factors.
The foregoing results are the outcome of our study of the complexity of {\em
onesided error} property testing algorithms in the boundeddegree graphs
model. For example, we show that cyclefreeness of $N$vertex graphs can be
tested with onesided error within time complexity
$\tildeO(\poly(1/\e)\cdot\sqrt{N})$. This matches the known $\Omega(\sqrt{N})$
query lower bound, and contrasts with the fact that any minorfree property
admits a {\em twosided error} tester of query complexity that only depends on
the proximity parameter $\e$. For any constant $k\geq3$, we extend this result
to testing whether the input graph has a simple cycle of length at least $k$.
On the other hand, for any fixed tree $T$, we show that $T$minorfreeness has
a onesided error tester of query complexity that only depends on the proximity
parameter $\e$.
Our algorithm for finding cycles in boundeddegree graphs extends to general
graphs, where distances are measured with respect to the actual number of
edges. Such an extension is not possible with respect to finding treeminors in
$o(\sqrt{N})$ complexity.

Let P be a set of n points in the Euclidean plane and let O be the origin
point in the plane. In the ktour cover problem (called frequently the
capacitated vehicle routing problem), the goal is to minimize the total length
of tours that cover all points in P, such that each tour starts and ends in O
and covers at most k points from P.
The ktour cover problem is known to be NPhard. It is also known to admit
constant factor approximation algorithms for all values of k and even a
polynomialtime approximation scheme (PTAS) for small values of k, i.e.,
k=O(log n / log log n).
We significantly enlarge the set of values of k for which a PTAS is provable.
We present a new PTAS for all values of k <= 2^{log^{\delta}n}, where \delta =
\delta(\epsilon). The main technical result proved in the paper is a novel
reduction of the ktour cover problem with a set of n points to a small set of
instances of the problem, each with O((k/\epsilon)^O(1)) points.