
Computing shortest paths is one of the central problems in the theory of
distributed computing. For the last few years, substantial progress has been
made on the approximate single source shortest paths problem, culminating in an
algorithm of Becker et al. [DISC'17] which deterministically computes
$(1+o(1))$approximate shortest paths in $\tilde O(D+\sqrt n)$ time, where $D$
is the hopdiameter of the graph. Up to logarithmic factors, this time
complexity is optimal, matching the lower bound of Elkin [STOC'04].
The question of exact shortest paths however saw no algorithmic progress for
decades, until the recent breakthrough of Elkin [STOC'17], which established a
sublineartime algorithm for exact single source shortest paths on undirected
graphs. Shortly after, Huang et al. [FOCS'17] provided improved algorithms for
exact all pairs shortest paths problem on directed graphs.
In this paper, we present a new singlesource shortest path algorithm with
complexity $\tilde O(n^{3/4}D^{1/4})$. For polylogarithmic $D$, this improves
on Elkin's $\tilde{O}(n^{5/6})$ bound and gets closer to the
$\tilde{\Omega}(n^{1/2})$ lower bound of Elkin [STOC'04]. For larger values of
$D$, we present an improved variant of our algorithm which achieves complexity
$\tilde{O}\left( n^{3/4+o(1)}+ \min\{ n^{3/4}D^{1/6},n^{6/7}\}+D\right)$, and
thus compares favorably with Elkin's bound of $\tilde{O}(n^{5/6} +
n^{2/3}D^{1/3} + D ) $ in essentially the entire range of parameters. This
algorithm provides also a qualitative improvement, because it works for the
more challenging case of directed graphs (i.e., graphs where the two directions
of an edge can have different weights), constituting the first sublineartime
algorithm for directed graphs. Our algorithm also extends to the case of exact
$\kappa$source shortest paths...

We study the problem of deleting the smallest set $S$ of vertices (resp.\
edges) from a given graph $G$ such that the induced subgraph (resp.\ subgraph)
$G \setminus S$ belongs to some class $\mathcal{H}$.
We consider the case where graphs in $\mathcal{H}$ have treewidth bounded by
$t$, and give a general framework to obtain approximation algorithms for both
vertex and edgedeletion settings from approximation algorithms for certain
natural graph partitioning problems called $k$Subset Vertex Separator and
$k$Subset Edge Separator, respectively.
For the vertex deletion setting, our framework combined with the current best
result for $k$Subset Vertex Separator, yields a significant improvement in the
approximation ratios for basic problems such as $k$Treewidth Vertex Deletion
and Planar$F$ Vertex Deletion. Our algorithms are simpler than previous works
and give the first uniform approximation algorithms under the natural
parameterization.
For the edge deletion setting, we give improved approximation algorithms for
$k$Subset Edge Separator combining ideas from LP relaxations and important
separators. We present their applications in boundeddegree graphs, and also
give an APXhardness result for the edge deletion problems.

A long series of recent results and breakthroughs have led to faster and
better distributed approximation algorithms for single source shortest paths
(SSSP) and related problems in the CONGEST model. The runtime of all these
algorithms, however, is $\tilde{\Omega}(\sqrt{n})$, regardless of the network
topology, even on nice networks with a (poly)logarithmic network diameter $D$.
While this is known to be necessary for some pathological networks, most
topologies of interest are arguably not of this type.
We give the first distributed approximation algorithms for shortest paths
problems that adjust to the topology they are run on, thus achieving
significantly faster running times on many topologies of interest. The running
time of our algorithms depends on and is close to $Q$, where $Q$ is the quality
of the best shortcut that exists for the given topology. While $Q =
\tilde{\Theta}(\sqrt{n} + D)$ for pathological worstcase topologies, many
topologies of interest have $Q = \tilde{\Theta}(D)$, which results in near
instance optimal running times for our algorithm, given the trivial $\Omega(D)$
lower bound.
The problems we consider are as follows: (1) an approximate shortest path
tree and SSSP distances, (2) a polylogarithmic size distance label for every
node such that from the labels of any two nodes alone one can determine their
distance (approximately), and (3) an (approximately) optimal flow for the
transshipment problem.
Our algorithms have a tunable tradeoff between running time and approximation
ratio. Our fastest algorithms have an arbitrarily good polynomial approximation
guarantee and an essentially optimal $\tilde{O}(Q)$ running time. On the other
end of the spectrum, we achieve polylogarithmic approximations in $\tilde{O}(Q
\cdot n^{\epsilon})$ rounds for any $\epsilon > 0$. It seems likely that
eventually, our nontrivial approximation algorithms for the...

Distributed network optimization algorithms, such as minimum spanning tree,
minimum cut, and shortest path, are an active research area in distributed
computing. This paper presents a fast distributed algorithm for such problems
in the CONGEST model, on networks that exclude a fixed minor.
On general graphs, many optimization problems, including the ones mentioned
above, require $\tilde\Omega(\sqrt n)$ rounds of communication in the CONGEST
model, even if the network graph has a much smaller diameter. Naturally, the
next step in algorithm design is to design efficient algorithms which bypass
this lower bound on a restricted class of graphs. Currently, the only known
method of doing so uses the lowcongestion shortcut framework of Ghaffari and
Haeupler [SODA'16]. Building off of their work, this paper proves that excluded
minor graphs admit highquality shortcuts, leading to an $\tilde O(D^2)$ round
algorithm for the aforementioned problems, where $D$ is the diameter of the
network graph. To work with excluded minor graph families, we utilize the Graph
Structure Theorem of Robertson and Seymour. To the best of our knowledge, this
is the first time the Graph Structure Theorem has been used for an algorithmic
result in the distributed setting.
Even though the proof is involved, merely showing the existence of good
shortcuts is sufficient to obtain simple, efficient distributed algorithms. In
particular, the shortcut framework can efficiently construct nearoptimal
shortcuts and then use them to solve the optimization problems. This, combined
with the very general family of excluded minor graphs, which includes most
other important graph classes, makes this result of significant interest.

Accretion onto a supermassive black hole of a rotating inflow is a
particularly difficult problem to study because of the wide range of length
scales involved. There have been broadly utilized analytic and numerical
treatments of the global properties of accretion flows, but detailed numerical
simulations are required to address certain critical aspects. We use the ZEUS
code to run hydrodynamical simulations of rotating, axisymmetric accretion
flows with Bremsstrahlung cooling, considering solutions for which the
centrifugal balance radius significantly exceeds the Schwarzschild radius, with
and without viscous angular momentum transport. Infalling gas is followed from
well beyond the Bondi radius down to the vicinity of the black hole. We produce
a continuum of solutions with respect to the single parameter
Mdot_Bondi/Mdot_Edd, and there is a sharp transition between two general
classes of solutions at an Eddington ratio of Mdot_Bondi/Mdot_Edd ~ few x
10^(2). Our high inflow solutions are very similar to the standard Shakura &
Sunyaev (1973) results. But our low inflow results are to zeroth order the
stationary Papaloizou and Pringle (1984) solution, which has no accretion. To
next order in the small, assumed viscosity they show circulation, with disk and
conical wind outflows almost balancing inflow. These solutions are
characterized by hot, vertically extended disks, and net accretion proceeds at
an extremely low rate, only of order alpha times the inflow rate. Our
simulations have converged with respect to spatial resolution and temporal
duration, and they do not depend strongly on our choice of boundary conditions.

Consider the free algebra A_n generated over Q by n generators x_1, ..., x_n.
Interesting objects attached to A = A_n are members of its lower central
series, L_i = L_i(A), defined inductively by L_1 = A, L_{i+1} = [A,L_{i}], and
their associated graded components B_i = B_i(A) defined as B_i=L_i/L_{i+1}.
These quotients B_i, for i at least 2, as well as the reduced quotient
\bar{B}_1=A/(L_2+A L_3), exhibit a rich geometric structure, as shown by Feigin
and Shoikhet and later authors,
(DobrovolskaKimMa,DobrovolskaEtingof,ArbesfeldJordan,BapatJordan).
We study the same problem over the integers Z and finite fields F_p. New
phenomena arise, namely, torsion in B_i over Z, and jumps in dimension over
F_p. We describe the torsion in the reduced quotient RB_1 and B_2 geometrically
in terms of the De Rham cohomology of Z^n. As a corollary we obtain a complete
description of \bar{B}_1(A_n(Z)) and \bar{B}_1(A_n(F_p)), as well as of
B_2(A_n(Z[1/2])) and B_2(A_n(F_p)), p>2. We also give theoretical and
experimental results for B_i with i>2, formulating a number of conjectures and
questions based on them. Finally, we discuss the supercase, when some of the
generators are odd (fermionic) and some are even (bosonic), and provide some
theoretical results and experimental data in this case.

Magnetospheres of pulsars are thought to be filled with plasma, and
variations in plasma supply can affect both pulsar emission properties and
spindown rates. A number of recently discovered "intermittent" pulsars switch
between two distinct states: an "on", radioloud state, and an "off",
radioquiet state. Spindown rates in the two states differ by a large factor,
$\sim 1.52.5$, which is not easily understood in the context of current
models. In this Letter we present selfconsistent numerical solutions of "on"
and "off" states of intermittent pulsar magnetospheres. We model the "on" state
as a nearly ideal forcefree magnetosphere with abundant magnetospheric plasma
supply. The lack of radio emission in the "off" state is associated with plasma
supply disruption that results in lower plasma density on the open field lines.
We model the "off" state using nearly vacuum conditions on the open field lines
and nearly ideal forcefree conditions on the closed field lines, where plasma
can remain trapped even in the absence of pair production. The toroidal
advection of plasma in the closed zone in the "off" state causes spindowns
that are a factor of $\sim 2$ higher than vacuum values, and we naturally
obtain a range of spindown ratios between the "on" and "off" states, $\sim
1.22.9$, which corresponds to a likely range of pulsar inclination angles of
$30{}90^\circ$. We consider the implications of our model to a number of
poorly understood but possibly related pulsar phenomena, including nulling,
timing noise, and rotating radio transients.

The current state of the art in the modeling of pulsar magnetospheres invokes
either the vacuum or forcefree limits for the magnetospheric plasma. Neither
of these limits can simultaneously account for both the plasma currents and the
accelerating electric fields that are needed to explain the morphology and
spectra of highenergy emission from pulsars. To better understand the
structure of such magnetospheres, we combine accelerating fields and forcefree
solutions by considering models of magnetospheres filled with resistive plasma.
We formulate Ohm's Law in the minimal velocity fluid frame and construct a
family of resistive solutions that smoothly bridges the gap between the vacuum
and the forcefree magnetosphere solutions. The spindown luminosity, open
field line potential drop, and the fraction of open field lines all transition
between the vacuum and forcefree values as the plasma conductivity varies from
zero to infinity. For fixed inclination angle, we find that the spindown
luminosity depends linearly on the open field line potential drop. We consider
the implications of our resistive solutions for the spin down of intermittent
pulsars and subpulse drift phenomena in radio pulsars.

Many global circulation models predict supersonic zonal winds and large
vertical shears in the atmospheres of shortperiod jovian exoplanets. Using
linear analysis and nonlinear local simulations, we investigate hydrodynamic
dissipation mechanisms to balance the thermal acceleration of these winds. The
adiabatic Richardson criterion remains a good guide to linear stability,
although thermal diffusion allows some modes to violate it at very long
wavelengths and very low growth rates. Nonlinearly, wind speeds saturate at
Mach numbers $\approx 2$ and Richardson numbers $\lesssim 1/4$ for a broad
range of plausible diffusivities and forcing strengths. Turbulence and vertical
mixing, though accompanied by weak shocks, dominate the dissipation, which
appears to be the outcome of a recurrent KelvinHelmholtz instability. An
explicit shear viscosity, as well as thermal diffusivity, is added to ZEUS to
capture dissipation outside of shocks. The wind speed is not monotonic nor
single valued for shear viscosities larger than about $10^{3}$ of the sound
speed times the pressure scale height. Coarsening the numerical resolution can
also increase the speed. Hence global simulations that are incapable of
representing vertical turbulence and shocks, either because of reduced physics
or because of limited resolution, may overestimate wind speeds. We recommend
that such simulations include artificial dissipation terms to control the Mach
and Richardson numbers and to capture mechanical dissipation as heat.