• ### Improved Distributed Algorithms for Exact Shortest Paths(1712.09121)

April 11, 2018 cs.DC, cs.DS
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 hop-diameter 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 sublinear-time 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 single-source 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 sublinear-time algorithm for directed graphs. Our algorithm also extends to the case of exact $\kappa$-source shortest paths...
• ### Losing Treewidth by Separating Subsets(1804.01366)

April 4, 2018 cs.DS
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 edge-deletion 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 bounded-degree graphs, and also give an APX-hardness result for the edge deletion problems.
• ### Faster Distributed Shortest Path Approximations via Shortcuts(1802.03671)

Feb. 11, 2018 cs.DS
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 worst-case 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 non-trivial approximation algorithms for the...
• ### Minor Excluded Network Families Admit Fast Distributed Algorithms(1801.06237)

Jan. 18, 2018 cs.DS
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 low-congestion shortcut framework of Ghaffari and Haeupler [SODA'16]. Building off of their work, this paper proves that excluded minor graphs admit high-quality 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 near-optimal 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.
• ### Rotating Accretion Flows: From Infinity to the Black Hole(1206.4059)

March 27, 2013 astro-ph.GA, astro-ph.HE
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.
• ### Lower central series of a free associative algebra over the integers and finite fields(1203.1893)

March 8, 2012 math.QA, math.RA
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, (Dobrovolska-Kim-Ma,Dobrovolska-Etingof,Arbesfeld-Jordan,Bapat-Jordan). 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.
• ### On the Spin-Down of Intermittent Pulsars(1201.2182)

Jan. 10, 2012 astro-ph.HE
Magnetospheres of pulsars are thought to be filled with plasma, and variations in plasma supply can affect both pulsar emission properties and spin-down rates. A number of recently discovered "intermittent" pulsars switch between two distinct states: an "on", radio-loud state, and an "off", radio-quiet state. Spin-down rates in the two states differ by a large factor, $\sim 1.5-2.5$, which is not easily understood in the context of current models. In this Letter we present self-consistent numerical solutions of "on" and "off" states of intermittent pulsar magnetospheres. We model the "on" state as a nearly ideal force-free 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 force-free 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 spin-downs that are a factor of $\sim 2$ higher than vacuum values, and we naturally obtain a range of spin-down ratios between the "on" and "off" states, $\sim 1.2-2.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.
• ### Resistive Solutions for Pulsar Magnetospheres(1107.0979)

Nov. 17, 2011 astro-ph.HE
The current state of the art in the modeling of pulsar magnetospheres invokes either the vacuum or force-free 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 high-energy emission from pulsars. To better understand the structure of such magnetospheres, we combine accelerating fields and force-free 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 force-free magnetosphere solutions. The spin-down luminosity, open field line potential drop, and the fraction of open field lines all transition between the vacuum and force-free values as the plasma conductivity varies from zero to infinity. For fixed inclination angle, we find that the spin-down 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 sub-pulse drift phenomena in radio pulsars.
• ### Circulation and Dissipation on Hot Jupiters(1005.0589)

May 4, 2010 astro-ph.EP
Many global circulation models predict supersonic zonal winds and large vertical shears in the atmospheres of short-period 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 Kelvin-Helmholtz 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.