Search

We study the scheduling of flows on a switch with the goal of optimizing metrics related to the response time of the flows. The input to the problem is a sequence of flow requests on a switch, where the switch is represented by a bipartite graph with a capacity on each vertex (or port), and a flow request is an edge with associated demand. In each round, a subset of edges can be scheduled subject to the constraint that the total demand of the scheduled edges incident on any vertex is at most the capacity of the vertex. Previous work has essentially settled the complexity of metrics based on {\em completion time}. The objective of average or maximum {\em response time}, however, is much more challenging. We present approximation algorithms for flow scheduling over a switch to optimize response time based metrics. For the average response time metric, whose NP-hardness follows directly from past work, we present an offline $O(1 + O(\log(n))/c)$ approximation algorithm for unit flows, assuming that the port capacities of the switch can be increased by a factor of $1 + c$, for any given positive integer $c$. For the maximum response time metric, we first establish that it is NP-hard to achieve an approximation factor of better than 4/3 without augmenting capacity. We then present an offline algorithm that achieves {\em optimal maximum response time}, assuming the capacity of each port is increased by at most $2 d_{max} - 1$, where $d_{max}$ is the maximum demand of any flow. Both algorithms are based on linear programming relaxations. We also study the online version of flow scheduling using the lens of competitive analysis, and present preliminary results along with experiments that evaluate the performance of fast online heuristics.

We consider the problem of scheduling $n$ precedence-constrained jobs on $m$ uniformly-related machines in the presence of an arbitrary, fixed communication delay $\rho$. We consider a model that allows job duplication, i.e. processing of the same job on multiple machines, which, as we show, can reduce the length of a schedule (i.e., its makespan) by a logarithmic factor. Our main result is an $O(\log m \log \rho / \log \log \rho)$-approximation algorithm for minimizing makespan, assuming the minimum makespan is at least $\rho$. Our algorithm is based on rounding a linear programming relaxation for the problem, which includes carefully designed constraints capturing the interaction among communication delay, precedence requirements, varying speeds, and job duplication. Our result builds on two previous lines of work, one with communication delay but identical machines (Lepere, Rapine 2002) and the other with uniformly-related machines but no communication delay (Chudak, Shmoys 1999). We next show that the integrality gap of our mathematical program is $\Omega(\sqrt{\log \rho})$. Our gap construction employs expander graphs and exploits a property of robust expansion and its generalization to paths of longer length. Finally, we quantify the advantage of duplication in scheduling with communication delay. We show that the best schedule without duplication can have makespan $\Omega(\rho/\log \rho)$ or $\Omega(\log m/\log\log m)$ or $\Omega(\log n/\log \log n)$ times that of an optimal schedule allowing duplication. Nevertheless, we present a polynomial time algorithm to transform any schedule to a schedule without duplication at the cost of a $O(\log^2 n \log m)$ factor increase in makespan. Together with our makespan approximation algorithm for schedules allowing duplication, this also yields a polylogarithmic-approximation algorithm for the setting where duplication is not allowed.

We demonstrate use of iteratively pruned deep learning model ensembles for detecting pulmonary manifestation of COVID-19 with chest X-rays. This disease is caused by the novel Severe Acute Respiratory Syndrome Coronavirus 2 (SARS-CoV-2) virus, also known as the novel Coronavirus (2019-nCoV). A custom convolutional neural network and a selection of ImageNet pretrained models are trained and evaluated at patient-level on publicly available CXR collections to learn modality-specific feature representations. The learned knowledge is transferred and fine-tuned to improve performance and generalization in the related task of classifying CXRs as normal, showing bacterial pneumonia, or COVID-19-viral abnormalities. The best performing models are iteratively pruned to reduce complexity and improve memory efficiency. The predictions of the best-performing pruned models are combined through different ensemble strategies to improve classification performance. Empirical evaluations demonstrate that the weighted average of the best-performing pruned models significantly improves performance resulting in an accuracy of 99.01% and area under the curve of 0.9972 in detecting COVID-19 findings on CXRs. The combined use of modality-specific knowledge transfer, iterative model pruning, and ensemble learning resulted in improved predictions. We expect that this model can be quickly adopted for COVID-19 screening using chest radiographs., Comment: 11 pages, 8 figures, IEEE Access journal published version

With the massive increase in the number of IoT devices being deployed in smart cities, it becomes paramount for middlewares to be able to handle very high loads and support demanding use-cases. In order to do so, middlewares must scale horizontally while providing a commensurate increase in availability and throughput. Currently, most open-source IoT middlewares do not provide out-of-the-box support for scaling horizontally. In this paper, we present "Vermillion'', a scalable, secure and open-source IoT middleware for smart cities which provides in-built support for scaling-out. We make three contributions in this paper. Firstly, the middleware platform itself along with a formal process for data exchange between data producers and consumers. Secondly, we propose the use of hash-based federation to distribute and manage load across various message broker nodes while eliminating inter-node synchronisation overheads. Thirdly, we discuss a case study where Vermillion was deployed in a city and briefly discuss about deployment considerations using the obtained results.

Support size estimation and the related problem of unseen species estimation have wide applications in ecology and database analysis. Perhaps the most used support size estimator is the Chao estimator. Despite its wide spread use, little is known about its theoretical properties. We analyze the Chao estimator and show that its worst case mean squared error (MSE) is smaller than the MSE of the plug-in estimator by a factor of $\mathcal{O} ((k/n)^4)$, where $k$ is the maximum support size and $n$ is the number of samples. Our main technical contribution is a new method to analyze rational estimators for discrete distribution properties, which may be of independent interest., Comment: 20 pages, 1 figure, short version presented at International Symposium on Information Theory (ISIT) 2019

We show how to produce antideuteron, antihelium, and other antinuclei in large fractions from the decays of a new particle $\phi$ that carries baryon number. Close to threshold, the production of nuclear bound states is preferred over the decay into individual nucleons, effectively decoupling antinuclei and antiproton fluxes and allowing the former to dominate, in clear contrast to antimatter production via coalescence. $\phi$ can either form dark matter itself or be produced by it, and can give rise to a potentially testable amount of antinuclei., Comment: 11 pages, includes discussion of antideuteron; matches published version

We construct a theory in which the solution to the strong CP problem is an emergent property of the background of the dark matter in the Universe. The role of the axion degree of freedom is played by multi-body collective excitations similar to spin-waves in the medium of the dark matter of the Galactic halo. The dark matter is a vector particle whose low energy interactions with the Standard Model take the form of its spin density coupled to $G \widetilde{G}$, which induces a potential on the average spin density inducing it to compensate $\overline{\theta}$, effectively removing CP violation in the strong sector in regions of the Universe with sufficient dark matter density. We discuss the viable parameter space, finding that light dark matter masses within a few orders of magnitude of the fuzzy limit are preferred, and discuss the associated signals with this type of solution to the strong CP problem., Comment: 5 pages, 2 figures. Version published in PRL

We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices, so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the mapping to the cycle is the identity map. This problem has its roots in the rich theory of retraction of topological spaces, and has strong ties to well-studied metric embedding problems such as minimum bandwidth and 0-extension. Our first result is an O(min{k, sqrt{n}})-approximation for retracting any graph on n nodes to a cycle with k nodes. We also show a surprising connection to Sperner's Lemma that rules out the possibility of improving this result using natural convex relaxations of the problem. Nevertheless, if the problem is restricted to planar graphs, we show that we can overcome these integrality gaps using an exact combinatorial algorithm, which is the technical centerpiece of the paper. Building on our planar graph algorithm, we also obtain a constant-factor approximation algorithm for retraction of points in the Euclidean plane to a uniform cycle.

We consider models of light dark matter coupled to quarks through a vector current interaction. For low energies, these models must be treated through the effective couplings to mesons, which are implemented here through the chiral Lagrangian. We find the rates of dark matter annihilation and decay to the light mesons, and find the expected photon spectrum from the decay of the hadrons. We compare to current and future observations, and show that there is a significant discovery reach for these models., Comment: 14 pages

For a three dimensional magnetohydrodynamic (MHD) plasma the dynamo action with ABC flow as initial condition has been studied. The study delineates crucial parameter that gives a transition from coherent nonlinear oscillation to dynamo. Further, for both kinematic and dynamic models at magnetic Prandtl number equal to unity the dynamo action is studied for driven ABC flows. The magnetic resistivity has been chosen at a value where the fast dynamo occurs and the growth rate shows no further variation with the change of magnetic Reynold's number. The exponent of growth of magnetic energy increases, indicating a faster dynamo, if a higher wave number is excited compared to the one with a lower wave number. The result has been found to hold good for both kinematic and externally forced dynamic dynamos where the backreaction of magnetic field on the velocity field is no more negligible. In case of an externally forced dynamic dynamo, the super Alfvenic flows have been found to excite strong dynamos giving rise to the growth of magnetic energy of seven orders of magnitude. The back-reaction of magnetic field on the velocity field through Lorentz force term has been found to affect the dynamics of the velocity field and in turn the dynamics of magnetic field, leading to a saturation, when the dynamo action is very prominent.

The evolution of isotropic, nondispersive, inertial wave, emerging from an unsteady initial coherent vortex is studied for strongly correlated Yukawa medium using 2D molecular dynamics simulation. In this study, the effect of azimuthal speed of vortex source, strong correlation, large screening and the compressibility of the medium over the propagation of generated inertial wave have been presented. It has been observed that these inertial waves only exist when the speed of the vortex source (U_0) is larger or equal to the longitudinal sound speed of the system. Estimated speed of the nonlinear wave (C_NLW ) is found to be always larger than the transverse sound speed (C_t ) of the system for the range of coupling and screening parameters. In this study, we find that spontaneously generated nonlinear inertial wave speed in Yukawa medium is suppressed by compressibility and dust-neutral a drag of the system and is less sensitive to coupling strength. A transition from incompressible to compressible Yukawa liquid is observed. This transition depends on the screening parameter and azimuthal speed of vortex source. The existence of a critical Mach number Mc~0.35 is found above which nonlinear wave is found to exists, indicating the compressible nature of the medium.

Strongly coupled dusty plasma medium is often described as a viscoelastic fluid that retains its memory. In a flowing dusty plasma medium, vortices of different sizes appear when the flow does not remain laminar. The vortices also merge to transfer energy between different scales. In the present work, we study the effect of viscoelasticity and compressibility over a localized vortex structure and multiple rotational vortexes in a strongly coupled viscoelastic dusty plasma medium. In case of single rotating vortex flow, a transverse wave is generated from the localized vortex source and the evolution time of generated waves is found to be reduced due to finite viscoelasticity and compressibility of the medium. It is found that the viscoelasticity suppresses the dispersion of vorticity. In the presence of multiple vortices, we find, the vortex mergers get highly affected in the presence of memory effect of the fluid, and thus the dynamics of the medium gets completely altered compared to a non-viscoelastic fluid. For a compressible fluid, viscoelasticity damps out the energy in the sonic waves generated in the medium. Thus a highly viscoelastic and compressible fluid, in some cases, behaves similarly to an incompressible viscoelastic fluid. The wave-front like rings propagate in elliptical orbits keeping the footprint of the earlier position of the point-vortex. The rings collide with each other even within the patch vortex region forming regions of high vorticity at the point of intersection and pass through each other.

A versatile scheduling problem to model a three-way tradeoff between delay/age, distortion, and energy is considered. The considered problem called the age and quality of information (AQI) is to select which packets to transmit at each time slot to minimize a linear combination of the distortion cost, the age/delay cost and the energy transmission cost in an online fashion. AQI generalizes multiple important problems such as age of information (AoI), the remote estimation problem with sampling constraint, the classical speed scaling problem among others. The worst case input model is considered, where the performance metric is the competitive ratio. A greedy algorithm is proposed that is shown to be 2-competitive, independent of all parameters of the problem. For the special case of AQI problem, a greedy online maximum weight matching based algorithm is also shown to be 2-competitive.

Since the advent of Taylor-Woltjer theory [J B Taylor, PRL, 33, 1139 (1974), L Woltjer, PNAS, 44, 489 (1958)], it has been widely believed that situations with perfectly conducting boundaries and near ideal conditions, the final state of MHD system would be force-free Taylor-Woltjer states defined as $\vec{\nabla} \times \vec{B} = \alpha \vec{B}$ with $\alpha$ as a constant and $\vec{B}$ is the magnetic field defined over a volume $V$. These states are of fundamental importance in fusion plasmas [J B Taylor, RMP 58, 741 (1986)]. More recently, several new MHD models have been proposed - for example Reduced Multi-region relaxed MHD [S R Hudson {\it et al}, Phys. Plasmas, 19, 112502 (2012)] and arbitrary scale relaxation model to Taylor-Woltjer state [H Qin {\it et al}, PRL, 109, 235001 (2012)] to mention a few. In the present work, we use a 3D compressible MHD solver in cartesian geometry which can handle conducting or periodic as well has mixed boundary conditions to investigate numerically the arbitrary scale relaxation model proposed by Qin et al [H Qin {\it et al}, PRL, 109, 235001 (2012)]. For this purpose, we consider two volumes $V_{init}$ and $V_{final}$. We load the 3D MHD solver in the limit of zero compressibility with a Taylor-Woltjer state $B_{init}(x,y,z,t=0)$ and let it again a numerical evolve with conducting boundaries at $V_{init}$ to make sure that we have obtained a numerically steady Taylor - Woltjer state for volume $V_{init}$. Followed by this procedure, we "suddenly" relax the boundaries to a new volume $V_{final}$, such that $V_{init}$ $<$ $V_{final}$ and evaluate whether or not the system attains quasi-steady state. Details of the numerical method used, the protocol followed, the expansion technique and the novelty of this numerical experiment and details of our results have been presented in this paper., Comment: Preprint of 27th IAEA Fusion Energy Conference (FEC 2018), Page 476, Poster

We examine the phenomenology of a simplified model of fermionic dark matter coupled to a light scalar mediator carrying lepton number 2. We find that the mediator can be very light and still consistent with laboratory and cosmological bounds. This model satisfies the thermal relic condition for natural values of dimensionless coupling constants and admits a mediator in the $10 - 100 ~\text{MeV}$ mass range favored by small scale structure observations. As such, this model provides an excellent candidate for self-interacting dark matter., Comment: 9 pages, 4 figures; v3: published version

We report on a numerical observation of recurrence phenomenon in a three dimensional magneto-hydrodynamic (MHD) plasma for certain classes of initial flow profiles. Our simulations discover such a behaviour for an initial Taylor-Green (TG) type of flow whereas under identical conditions an initial Arnold-Beltrami-Childress (ABC) flow fails to show recurrent behaviour. This difference in the dynamical behaviours is traced to the nature of the Rayleigh quotient in each case. The Rayleigh quotient which is an approximate measure of the number of active degrees of freedom in a dynamical system is found to remain small and bounded in time for the TG flow but grows indefinitely in time for the ABC flow. An estimate of the effective degrees of freedom for the TG flow case is provided and its practical implications for the nonlinear behaviour of the continuum nonlinear MHD plasma system is discussed.

Single fluid magnetohydrodynamic (MHD) equations have been studied through direct numerical simulations (DNS) using pseudo-spectral methods in two as well as three spatial dimensions. At Alfv\'en resonance, a reversible periodic exchange of energy between kinetic and magnetic variables is observed. The oscillations are identified as nonlinear dispersionless Alfv\'en waves that have been predicted earlier on theoretical grounds but not observed in large scale numerical simulations. A systematic study of their occurrence for various initial conditions and a range of Alfven velocities is carried out. An analysis based on a finite mode representation of the incompressible single fluid MHD equations in two spatial dimensions reproduces the essential features of these oscillations.

The classical problem of maximizing a submodular function under a matroid constraint is considered. Defining a new measure for the increments made by the greedy algorithm at each step, called the discriminant, improved approximation ratio guarantees are derived for the greedy algorithm. At each step, discriminant measures the multiplicative gap in the incremental valuation between the item chosen by the greedy algorithm and the largest potential incremental valuation for eligible items not selected by it. The new guarantee subsumes all the previous known results for the greedy algorithm, including the curvature based ones, and the derived guarantees are shown to be tight via constructing specific instances. More refined approximation guarantee is derived for a special case called the submodular welfare maximization/partition problem that is also tight, for both the offline and the online case., Comment: 24 pages

This paper presents the benchmarking and scaling studies of a GPU accelerated three dimensional compressible magnetohydrodynamic code. The code is developed keeping an eye to explain the large and intermediate scale magnetic field generation is cosmos as well as in nuclear fusion reactors in the light of the theory given by Eugene Newman Parker. The spatial derivatives of the code are pseudo-spectral method based and the time solvers are explicit. GPU acceleration is achieved with minimal code changes through OpenACC parallelization and use of NVIDIA CUDA Fast Fourier Transform library (cuFFT). NVIDIAs unified memory is leveraged to enable over-subscription of the GPU device memory for seamless out-of-core processing of large grids. Our experimental results indicate that the GPU accelerated code is able to achieve upto two orders of magnitude speedup over a corresponding OpenMP parallel, FFTW library based code, on a NVIDIA Tesla P100 GPU. For large grids that require out-of-core processing on the GPU, we see a 7x speedup over the OpenMP, FFTW based code, on the Tesla P100 GPU. We also present performance analysis of the GPU accelerated code on different GPU architectures - Kepler, Pascal and Volta.

The magnetic moment of the $\tau$ lepton is an interesting quantity that is potentially sensitive to physics beyond the Standard Model. Electroweak gauge invariance implies that a heavy new physics contribution to it takes the form of an operator which involves the Higgs boson, implying that rare Higgs decays are able to probe the same physics as $a_\tau$. We examine the prospects for rare Higgs decays at future high energy lepton (electron or muon) colliders, and find that such a project collecting a few ab$^{-1}$ would be able to advance our understanding of this physics by roughly a factor of 10 compared to the expected reach of the high luminosity LHC.

Invariant tensors play an important role in gauge theories, for example, in dualities of N=1 gauge theories. However, for theories with fields in representations larger than the fundamental, the full set of invariant tensors is often difficult to construct. We present a new approach to the construction of these tensors, and use it to find the complete set of invariant tensors of a theory of SO(3) with fields in the symmetric tensor representation.

Leptoquarks provide some of the simplest explanations to the hints of lepton flavor non-universality in $B$ decays. In particular, a new confining gauge group can provide a natural and appealing origin for the leptoquarks. So far, direct collider searches have been based on two body decays, namely to a quark and a lepton. We study how composite dynamics can give rise to additional states resulting in modified collider signatures of leptoquarks, as well as new production modes in cascade decays of heavier states. Instead of the standard signature, each leptoquark can result in as many as four jets and a lepton. We reinterpret relevant ATLAS and CMS searches to set limits on this scenario, show how this can relax the current bounds, and propose ways to better constrain this class of models in the future. For example, we show that a leptoquark related to the $R_{D^{(*)}}$ anomaly could still be as light as 500 GeV., Comment: 9 pages, 5 figures. v3: matches PRD version. v2: 2nd gen leptoquark search updated to new CMS results, refs added. Recasting material (scripts, validation material) attached as ancillary files

We propose a novel online learning algorithm for Restricted Boltzmann Machines (RBM), namely, the Online Generative Discriminative Restricted Boltzmann Machine (OGD-RBM), that provides the ability to build and adapt the network architecture of RBM according to the statistics of streaming data. The OGD-RBM is trained in two phases: (1) an online generative phase for unsupervised feature representation at the hidden layer and (2) a discriminative phase for classification. The online generative training begins with zero neurons in the hidden layer, adds and updates the neurons to adapt to statistics of streaming data in a single pass unsupervised manner, resulting in a feature representation best suited to the data. The discriminative phase is based on stochastic gradient descent and associates the represented features to the class labels. We demonstrate the OGD-RBM on a set of multi-category and binary classification problems for data sets having varying degrees of class-imbalance. We first apply the OGD-RBM algorithm on the multi-class MNIST dataset to characterize the network evolution. We demonstrate that the online generative phase converges to a stable, concise network architecture, wherein individual neurons are inherently discriminative to the class labels despite unsupervised training. We then benchmark OGD-RBM performance to other machine learning, neural network and ClassRBM techniques for credit scoring applications using 3 public non-stationary two-class credit datasets with varying degrees of class-imbalance. We report that OGD-RBM improves accuracy by 2.5-3% over batch learning techniques while requiring at least 24%-70% fewer neurons and fewer training samples. This online generative training approach can be extended greedily to multiple layers for training Deep Belief Networks in non-stationary data mining applications without the need for a priori fixed architectures., Comment: 14 pages, 4 figures, 2 tables

The effect of compressibility in hydrodynamic vortex merging has been discussed. In the past, in incompressible limit it has been observed that the merging of a collection of intense point-like vortices arranged uniformly outside a circular vortex, can lead to quasistationary vortex patch and transient hole pattern inside the patch via nonlinear merger process. These patterns are akin to \textquoteleft vortex crystals\textquoteright. Compressibility can introduce a natural acoustic scale to the problem. We find that the natural mode is independent of the number of point-like vortices and the amplitude scales linearly with compressibility. Further it has been identified that after merging, the system exhibits oscillation at a natural frequency together with its harmonics and beats with its own harmonics. The power of the frequency is found to scale as $M^{-2}$, where $M$ is the Mach number. Also the vortex crystals formed out of the merging process are found to melt faster as compressibility is increased.

Under the influence of gravity, light scalar fields can form bound compact objects called boson stars. We use the technique of matching asymptotic expansions to obtain the profile for boson stars where the constituent particles have self-interactions. We obtain parametric representations of these profiles as a function of the self-interactions, including the case of very strong self-interactions. We show that our methods agree with solutions obtained by purely numerical methods. Significant distortions are found as compared to the noninteracting case., Comment: 13 pages, Version 2: updated after accepted by journal, references updated, minor changes