
The girth of a graph, i.e. the length of its shortest cycle, is a fundamental
graph parameter. Unfortunately all known algorithms for computing, even
approximately, the girth and girthrelated structures in directed weighted
$m$edge and $n$node graphs require $\Omega(\min\{n^{\omega}, mn\})$ time (for
$2\leq\omega<2.373$). In this paper, we drastically improve these runtimes as
follows:
* Multiplicative Approximations in Nearly Linear Time: We give an algorithm
that in $\widetilde{O}(m)$ time computes an $\widetilde{O}(1)$multiplicative
approximation of the girth as well as an $\widetilde{O}(1)$multiplicative
roundtrip spanner with $\widetilde{O}(n)$ edges with high probability (w.h.p).
* Nearly Tight Additive Approximations: For unweighted graphs and any $\alpha
\in (0,1)$ we give an algorithm that in $\widetilde{O}(mn^{1  \alpha})$ time
computes an $O(n^\alpha)$additive approximation of the girth w.h.p, and
partially derandomize it. We show that the runtime of our algorithm cannot be
significantly improved without a breakthrough in combinatorial Boolean matrix
multiplication.
Our main technical contribution to achieve these results is the first nearly
linear time algorithm for computing roundtrip covers, a directed graph
decomposition concept key to previous roundtrip spanner constructions.
Previously it was not known how to compute these significantly faster than
$\Omega(\min\{n^\omega, mn\})$ time. Given the traditional difficulty in
efficiently processing directed graphs, we hope our techniques may find further
applications.

Reinforcement learning algorithms can train agents that solve problems in
complex, interesting environments. Normally, the complexity of the trained
agent is closely related to the complexity of the environment. This suggests
that a highly capable agent requires a complex environment for training. In
this paper, we point out that a competitive multiagent environment trained
with selfplay can produce behaviors that are far more complex than the
environment itself. We also point out that such environments come with a
natural curriculum, because for any skill level, an environment full of agents
of this level will have the right level of difficulty. This work introduces
several competitive multiagent environments where agents compete in a 3D world
with simulated physics. The trained agents learn a wide variety of complex and
interesting skills, even though the environment themselves are relatively
simple. The skills include behaviors such as running, blocking, ducking,
tackling, fooling opponents, kicking, and defending using both arms and legs. A
highlight of the learned behaviors can be found here: https://goo.gl/eR7fbX

In the communication problem $\mathbf{UR}$ (universal relation) [KRW95],
Alice and Bob respectively receive $x, y \in\{0,1\}^n$ with the promise that
$x\neq y$. The last player to receive a message must output an index $i$ such
that $x_i\neq y_i$. We prove that the randomized oneway communication
complexity of this problem in the public coin model is exactly
$\Theta(\min\{n,\log(1/\delta)\log^2(\frac n{\log(1/\delta)})\})$ for failure
probability $\delta$. Our lower bound holds even if promised
$\mathop{support}(y)\subset \mathop{support}(x)$. As a corollary, we obtain
optimal lower bounds for $\ell_p$sampling in strict turnstile streams for
$0\le p < 2$, as well as for the problem of finding duplicates in a stream. Our
lower bounds do not need to use large weights, and hold even if promised
$x\in\{0,1\}^n$ at all points in the stream.
We give two different proofs of our main result. The first proof demonstrates
that any algorithm $\mathcal A$ solving sampling problems in turnstile streams
in low memory can be used to encode subsets of $[n]$ of certain sizes into a
number of bits below the information theoretic minimum. Our encoder makes
adaptive queries to $\mathcal A$ throughout its execution, but done carefully
so as to not violate correctness. This is accomplished by injecting random
noise into the encoder's interactions with $\mathcal A$, which is loosely
motivated by techniques in differential privacy. Our second proof is via a
novel randomized reduction from Augmented Indexing [MNSW98] which needs to
interact with $\mathcal A$ adaptively. To handle the adaptivity we identify
certain likely interaction patterns and union bound over them to guarantee
correct interaction on all of them. To guarantee correctness, it is important
that the interaction hides some of its randomness from $\mathcal A$ in the
reduction.

In the communication problem $\mathbf{UR}$ (universal relation) [KRW95],
Alice and Bob respectively receive $x$ and $y$ in $\{0,1\}^n$ with the promise
that $x\neq y$. The last player to receive a message must output an index $i$
such that $x_i\neq y_i$. We prove that the randomized oneway communication
complexity of this problem in the public coin model is exactly $\Theta(\min\{n,
\log(1/\delta)\log^2(\frac{n}{\log(1/\delta)})\})$ bits for failure probability
$\delta$. Our lower bound holds even if promised $\mathop{support}(y)\subset
\mathop{support}(x)$. As a corollary, we obtain optimal lower bounds for
$\ell_p$sampling in strict turnstile streams for $0\le p < 2$, as well as for
the problem of finding duplicates in a stream. Our lower bounds do not need to
use large weights, and hold even if it is promised that $x\in\{0,1\}^n$ at all
points in the stream.
Our lower bound demonstrates that any algorithm $\mathcal{A}$ solving
sampling problems in turnstile streams in low memory can be used to encode
subsets of $[n]$ of certain sizes into a number of bits below the information
theoretic minimum. Our encoder makes adaptive queries to $\mathcal{A}$
throughout its execution, but done carefully so as to not violate correctness.
This is accomplished by injecting random noise into the encoder's interactions
with $\mathcal{A}$, which is loosely motivated by techniques in differential
privacy. Our correctness analysis involves understanding the ability of
$\mathcal{A}$ to correctly answer adaptive queries which have positive but
bounded mutual information with $\mathcal{A}$'s internal randomness, and may be
of independent interest in the newly emerging area of adaptive data analysis
with a theoretical computer science lens.

We develop new methods based on graph motifs for graph clustering, allowing
more efficient detection of communities within networks. We focus on triangles
within graphs, but our techniques extend to other clique motifs as well. Our
intuition, which has been suggested but not formalized similarly in previous
works, is that triangles are a better signature of community than edges. We
therefore generalize the notion of conductance for a graph to {\em triangle
conductance}, where the edges are weighted according to the number of triangles
containing the edge. This methodology allows us to develop variations of
several existing clustering techniques, including spectral clustering, that
minimize triangles split by the cluster instead of edges cut by the cluster. We
provide theoretical results in a planted partition model to demonstrate the
potential for triangle conductance in clustering problems. We then show
experimentally the effectiveness of our methods to multiple applications in
machine learning and graph mining.

A spectral sparsifier of a graph $G$ is a sparser graph $H$ that
approximately preserves the quadratic form of $G$, i.e. for all vectors $x$,
$x^T L_G x \approx x^T L_H x$, where $L_G$ and $L_H$ denote the respective
graph Laplacians. Spectral sparsifiers generalize cut sparsifiers, and have
found many applications in designing graph algorithms. In recent years, there
has been interest in computing spectral sparsifiers in semistreaming and
dynamic settings. Natural algorithms in these settings often involve repeated
sparsification of a graph, and accumulation of errors across these steps. We
present a framework for analyzing algorithms that perform repeated
sparsifications that only incur error corresponding to a single sparsification
step, leading to better results for many resparsificationbased algorithms. As
an application, we show how to maintain a spectral sparsifier in the
semistreaming setting: We present a simple algorithm that, for a graph $G$ on
$n$ vertices and $m$ edges, computes a spectral sparsifier of $G$ with $O(n
\log n)$ edges in a single pass over $G$, using only $O(n \log n)$ space, and
$O(m \log^2 n)$ total time. This improves on previous best semistreaming
algorithms for both spectral and cut sparsifiers by a factor of $\log{n}$ in
both space and runtime. The algorithm extends to semistreaming row sampling
for general PSD matrices. We also use our framework to combine a spectral
sparsification algorithm by Koutis with improved spanner constructions to give
a parallel algorithm for constructing $O(n\log^2{n}\log\log{n})$ sized spectral
sparsifiers in $O(m\log^2{n}\log\log{n})$ time. This is the best known
combinatorial graph sparsification algorithm.The size of the sparsifiers is
only a factor $\log{n}\log\log{n}$ more than ones produced by numerical
routines.

In this paper we provide faster algorithms for solving the geometric median
problem: given $n$ points in $\mathbb{R}^{d}$ compute a point that minimizes
the sum of Euclidean distances to the points. This is one of the oldest
nontrivial problems in computational geometry yet despite an abundance of
research the previous fastest algorithms for computing a
$(1+\epsilon)$approximate geometric median were $O(d\cdot
n^{4/3}\epsilon^{8/3})$ by Chin et. al,
$\tilde{O}(d\exp{\epsilon^{4}\log\epsilon^{1}})$ by Badoiu et. al,
$O(nd+\mathrm{poly}(d,\epsilon^{1})$ by Feldman and Langberg, and
$O((nd)^{O(1)}\log\frac{1}{\epsilon})$ by Parrilo and Sturmfels and Xue and Ye.
In this paper we show how to compute a $(1+\epsilon)$approximate geometric
median in time $O(nd\log^{3}\frac{1}{\epsilon})$ and $O(d\epsilon^{2})$. While
our $O(d\epsilon^{2})$ is a fairly straightforward application of stochastic
subgradient descent, our $O(nd\log^{3}\frac{1}{\epsilon})$ time algorithm is a
novel long step interior point method. To achieve this running time we start
with a simple $O((nd)^{O(1)}\log\frac{1}{\epsilon})$ time interior point method
and show how to improve it, ultimately building an algorithm that is quite
nonstandard from the perspective of interior point literature. Our result is
one of very few cases we are aware of outperforming traditional interior point
theory and the only we are aware of using interior point methods to obtain a
nearly linear time algorithm for a canonical optimization problem that
traditionally requires superlinear time. We hope our work leads to further
improvements in this line of research.

We show that schemes for sparsifying matrices based on iteratively resampling
rows yield guarantees matching classic 'offline' sparsifiers (see e.g. Spielman
and Srivastava [STOC 2008]).
In particular, this gives a formal analysis of a scheme very similar to the
one proposed by Kelner and Levin [TCS 2013].

Finding a small spectral approximation for a tall $n \times d$ matrix $A$ is
a fundamental numerical primitive. For a number of reasons, one often seeks an
approximation whose rows are sampled from those of $A$. Row sampling improves
interpretability, saves space when $A$ is sparse, and preserves row structure,
which is especially important, for example, when $A$ represents a graph.
However, correctly sampling rows from $A$ can be costly when the matrix is
large and cannot be stored and processed in memory. Hence, a number of recent
publications focus on row sampling in the streaming setting, using little more
space than what is required to store the outputted approximation [KL13,
KLM+14].
Inspired by a growing body of work on online algorithms for machine learning
and data analysis, we extend this work to a more restrictive online setting: we
read rows of $A$ one by one and immediately decide whether each row should be
kept in the spectral approximation or discarded, without ever retracting these
decisions. We present an extremely simple algorithm that approximates $A$ up to
multiplicative error $\epsilon$ and additive error $\delta$ using $O(d \log d
\log(\epsilonA_2/\delta)/\epsilon^2)$ online samples, with memory overhead
proportional to the cost of storing the spectral approximation. We also present
an algorithm that uses $O(d^2$) memory but only requires
$O(d\log(\epsilonA_2/\delta)/\epsilon^2)$ samples, which we show is
optimal.
Our methods are clean and intuitive, allow for lower memory usage than prior
work, and expose new theoretical properties of leverage score based matrix
approximation.

We introduce the notion of balance for directed graphs: a weighted directed
graph is $\alpha$balanced if for every cut $S \subseteq V$, the total weight
of edges going from $S$ to $V\setminus S$ is within factor $\alpha$ of the
total weight of edges going from $V\setminus S$ to $S$. Several important
families of graphs are nearly balanced, in particular, Eulerian graphs (with
$\alpha = 1$) and residual graphs of $(1+\epsilon)$approximate undirected
maximum flows (with $\alpha=O(1/\epsilon)$).
We use the notion of balance to give a more finegrained understanding of
several wellstudied routing questions that are considerably harder in directed
graphs. We first revisit oblivious routings in directed graphs. Our main
algorithmic result is an oblivious routing scheme for singlesource instances
that achieve an $O(\alpha \cdot \log^3 n / \log \log n)$ competitive ratio. In
the process, we make several technical contributions which may be of
independent interest. In particular, we give an efficient algorithm for
computing lowradius decompositions of directed graphs parameterized by
balance. We also define and construct lowstretch arborescences, a
generalization of lowstretch spanning trees to directed graphs.
On the negative side, we present new lower bounds for oblivious routing
problems on directed graphs. We show that the competitive ratio of oblivious
routing algorithms for directed graphs is $\Omega(n)$ in general; this result
improves upon the longstanding best known lower bound of $\Omega(\sqrt{n})$
given by Hajiaghayi, Kleinberg, Leighton and R\"acke in 2006. We also show that
our restriction to singlesource instances is necessary by showing an
$\Omega(\sqrt{n})$ lower bound for multiplesource oblivious routing in
Eulerian graphs.
We also give a fast algorithm for the maximum flow problem in balanced
directed graphs.

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if
there is a homomorphism from graph $G$ to graph $H$ cannot be done in time
$V(H)^{o(V(G))}$. We also show an exponentialtime reduction from Graph
Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a
possibility of $V(H)^{o(V(H))}$time algorithm deciding if graph $G$ is a
subgraph of $H$. For both problems our lower bounds asymptotically match the
running time of bruteforce algorithms trying all possible mappings of one
graph into another. Thus, our work closes the gap in the known complexity of
these fundamental problems.
Moreover, as a consequence of our reductions conditional lower bounds follow
for other related problems such as Locally Injective Homomorphism, Graph
Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic
Assignment Problem.

Subgraph Isomorphism is a very basic graph problem, where given two graphs
$G$ and $H$ one is to check whether $G$ is a subgraph of $H$. Despite its
simple definition, the Subgraph Isomorphism problem turns out to be very broad,
as it generalizes problems such as Clique, $r$Coloring, Hamiltonicity, Set
Packing and Bandwidth. However, for all of the mentioned problems
$2^{\mathcal{O}(n)}$ time algorithms exist, so a natural and frequently asked
question in the past was whether there exists a $2^{\mathcal{O}(n)}$ time
algorithm for Subgraph Isomorphism. In the monograph of Fomin and Kratsch
[Springer'10] this question is highlighted as an open problem, among few
others.
Our main result is a reduction from 3SAT, producing a subexponential number
of sublinear instances of the Subgraph Isomorphism problem. In particular, our
reduction implies a $2^{\Omega(n \sqrt{\log n})}$ lower bound for Subgraph
Isomorphism under the Exponential Time Hypothesis. This shows that there exist
classes of graphs that are strictly harder to embed than cliques or Hamiltonian
cycles.
The core of our reduction consists of two steps. First, we preprocess and
pack variables and clauses of a 3SAT formula into groups of logarithmic size.
However, the grouping is not arbitrary, since as a result we obtain only a
limited interaction between the groups. In the second step, we overcome the
technical hardness of encoding evaluations as permutations by a simple, yet
fruitful scheme of guessing the sizes of preimages of an arbitrary mapping,
reducing the case of arbitrary mapping to bijections. In fact, when applying
this step to a recent independent result of Fomin et al.[arXiv:1502.05447
(2015)], who showed hardness of Graph Homomorphism, we can transfer their
hardness result to Subgraph Isomorphism, implying a nearly tight lower bound of
$2^{\Omega(n \log n / \log \log n)}$.

We derive a simple efficient algorithm for Abelian periods knowing all
Abelian squares in a string. An efficient algorithm for the latter problem was
given by Cummings and Smyth in 1997. By the way we show an alternative
algorithm for Abelian squares. We also obtain a linear time algorithm finding
all `long' Abelian periods. The aim of the paper is a (new) reduction of the
problem of all Abelian periods to that of (already solved) all Abelian squares
which provides new insight into both connected problems.