bluuebunny/crossref_metadata_2025 huggingface dataset:
NEW NONLINEAR RECURRENT HIDDEN VARIABLE FRACTAL INTERPOLATION SURFACES
Authors: KIM HYONJIN , KIM JINMYONG , MUN HAKMYONG
Published: December 2019

In this paper, we present the construction of new nonlinear recurrent hidden variable fractal interpolation surfaces (RHVFISs) with function vertical scaling factors. We use Rakotch’s fixed point theorem which is a generalization of Banach’s fixed point theorem to get new nonlinear fractal surfaces. We construct recurrent vector-valued iterated function systems (IFSs) with function vertical scaling factors on rectangular grids and generate flexible and diverse RHVFISs which are attractors of the IFSs. We also give an explicit example to show the effectiveness of obtained results.
A TOP-DOWN APPROACH FOR THE MULTIPLE EXERCISES AND VALUATION OF EMPLOYEE STOCK OPTIONS
Authors: LEUNG TIM , ZHOU YANG
Published: December 2019

We propose a new framework to value employee stock options (ESOs) that capture multiple exercises of different quantities over time. We also model the ESO holder’s job termination risk and incorporate its impact on the payoffs of both vested and unvested ESOs. Numerical methods based on Fourier transform and finite differences are developed and implemented to solve the associated systems of PDEs. In addition, we introduce a new valuation method based on maturity randomization that yields analytic formulae for vested and unvested ESO costs. We examine the cost impact of job termination risk, exercise intensity and various contractual features.
Unique factorization property of non-unique factorization domains
Authors: Chang Gyu Whan
Published: December 2019

Let [Formula: see text] be an integral domain, [Formula: see text] be the polynomial ring over [Formula: see text], [Formula: see text] be the so-called [Formula: see text]-operation on [Formula: see text], and [Formula: see text]-Spec[Formula: see text] be the set of prime [Formula: see text]-ideals of [Formula: see text]. A nonzero nonunit of [Formula: see text] is said to be homogeneous if it is contained in a unique maximal [Formula: see text]-ideal of [Formula: see text]. We say that [Formula: see text] is a homogeneous factorization domain (HoFD) if each nonzero nonunit of [Formula: see text] can be written as a finite product of pairwise [Formula: see text]-comaximal homogeneous elements. In this paper, among other things, we show that (1) a Prüfer [Formula: see text]-multiplication domain (P[Formula: see text]MD) [Formula: see text] is an HoFD if and only if [Formula: see text] is an HoFD (2) if [Formula: see text] is integrally closed, then [Formula: see text] is a P[Formula: see text]MD if and only if [Formula: see text]-Spec[Formula: see text] is treed, and (3) [Formula: see text] is a weakly Matlis GCD-domain if and only if [Formula: see text] is an HoFD with [Formula: see text]-Spec[Formula: see text] treed. We also study the HoFD property of [Formula: see text] constructions, pullbacks, and semigroup rings.
Finite groups whose non-abelian self-centralizing subgroups are TI-subgroups or subnormal subgroups
Authors: Sun Yuqing , Lu Jiakuan , Meng Wei
Published: December 2019

In this paper, we prove that if every non-abelian self-centralizing subgroup of a finite group [Formula: see text] is a TI-subgroup or a subnormal subgroup of [Formula: see text], then every non-abelian subgroup of [Formula: see text] must be subnormal in [Formula: see text].
The lattice properties of 𝔛-local formations of finite groups
Authors: Tsarev Aleksandr
Published: December 2019

Let [Formula: see text] be a class of simple groups with a completeness property [Formula: see text]. Förster introduced the concept of [Formula: see text]-local formation in order to obtain a common extension of well-known theorems of Gaschütz–Lubeseder–Schmid and Baer [Publ. Mat. UAB 29(2–3) (1985) 39–76]. In this paper, it is proved that the lattice of all [Formula: see text]-local formations of finite groups is modular.
On the minimum degree of the power graph of a finite cyclic group
Authors: Panda Ramesh Prasad , Patra Kamal Lochan , Sahoo Binod Kumar
Published: December 2019

The power graph [Formula: see text] of a finite group [Formula: see text] is the undirected simple graph whose vertex set is [Formula: see text], in which two distinct vertices are adjacent if one of them is an integral power of the other. For an integer [Formula: see text], let [Formula: see text] denote the cyclic group of order [Formula: see text] and let [Formula: see text] be the number of distinct prime divisors of [Formula: see text]. The minimum degree [Formula: see text] of [Formula: see text] is known for [Formula: see text], see [R. P. Panda and K. V. Krishna, On the minimum degree, edge-connectivity and connectivity of power graphs of finite groups, Comm. Algebra 46(7) (2018) 3182–3197]. For [Formula: see text], under certain conditions involving the prime divisors of [Formula: see text], we identify at most [Formula: see text] vertices such that [Formula: see text] is equal to the degree of at least one of these vertices. If [Formula: see text], or that [Formula: see text] is a product of distinct primes, we are able to identify two such vertices without any condition on the prime divisors of [Formula: see text].
NECESSITY VERSUS OPPORTUNITY MOTIVATION: NASCENT FIRM PERFORMANCE IN CARIBBEAN SMALL ISLAND DEVELOPING STATES
Authors: MOHAN PREEYA S.
Published: December 2019

This paper investigates entry motivation of nascent entrepreneurs and their post-entry performance in Caribbean Small Island Developing States (SIDS). The study estimates the effect of being a nascent opportunity/necessity entrepreneur on three business-performance variables — firm growth, exports and innovation using regression analysis and control for time, country and sector effects. The data come from the Global Entrepreneurship Monitor (GEM) Adult Population Survey (APS) for Barbados, Jamaica and Trinidad and Tobago. The results show that opportunity versus necessity entrepreneurial start-up motivation tends to be related to a superior post-entry firm performance. In addition, personal and firm characteristics influence post-entry firm performance including gender, education, household income, number of owners, firm age and number of workers at start-up.
Fourier coefficients of the overconvergent generalized eigenform associated to a CM form
Authors: Hsu Chi-Yun
Published: December 2019

Let [Formula: see text] be a modular form with complex multiplication. If [Formula: see text] has critical slope, then Coleman’s classicality theorem implies that there is a [Formula: see text]-adic overconvergent generalized Hecke eigenform with the same Hecke eigenvalues as [Formula: see text]. We give a formula for the Fourier coefficients of this generalized Hecke eigenform. We also investigate the dimension of the generalized Hecke eigenspace of [Formula: see text]-adic overconvergent forms containing [Formula: see text].
Orthorecursive expansion of unity
Authors: Kalmynin A. B. , Kosenko P. R.
Published: December 2019

We study the properties of a sequence [Formula: see text] defined by the recursive relation [Formula: see text] for [Formula: see text] and [Formula: see text]. This sequence also has an alternative definition in terms of certain norm minimization in the space [Formula: see text]. We prove estimates on the growth order of [Formula: see text] and the sequence of its partial sums, infinite series identities, connecting [Formula: see text] with the harmonic numbers [Formula: see text] and also formulate some conjectures based on numerical computations.
THE MARKET FOR CRYPTOCURRENCY: HOW WILL IT EVOLVE?
Authors: ALLEN BROOKS , BRYANT SARAH K.
Published: December 2019

This study examines the concept of cryptocurrency and gives a brief history and overview of its characteristics. In an increasingly electronic society, cryptocurrency could be the next step in the evolution of finance in the same way that the internet was a step in the evolution of communication. In the coming years, countries may even announce the release of national cryptocurrencies, although certain conditions must be met for these efforts to be successful. Although the market is still in the early stages, as it begins to mature, cryptocurrency may become more prominent, until it becomes the new status quo.
Teaching Body Mass Index and Kleiber Law
Authors: Agrawal Dulli C.
Published: December 2019

Scaling laws advise that resting metabolic rates in animals and their corresponding body surfaces both should follow [Formula: see text] dependence. A pedagogic attempt has been made to validate this Kleiber law in case of human beings having spherical head and cylindrical arms, legs and trunk with the help of associated body mass index. It is observed that the metabolic rates of those persons who either lose or put on weight are not affected provided their body parts are functioning properly. It is suggested that matching body mass indices should also be worked out for animals.
Distinct Feature of Inverse Square Force and Harmonic Force: A Simplistic Proof of Bertrand’s Theorem
Authors: Ricardo Bernard , Ho Li Xiong Timothy
Published: December 2019

Bertrand’s theorem is essential to the discussion of the motion of particles under central force. The theorem states that among all central forces, the only two in which bound orbits are also closed orbits are the harmonic force and inverse-square force. As existing proofs of the theorem require advanced mathematics, this paper presents a much more simplistic proof of Bertrand’s theorem without having to solve any complicated integrals or using mathematical tools beyond the scope of high school curriculum. The first part of the proof shows that the radial force must be a single power law, and the second part of the proof — which is the main crux of this paper — uses the fact that the radial distance of the motion must be a power of a sinusoidal function of the polar angle in nature. With a simple mathematical manipulation, the proof is then completed. This derivation is expected to be of great interest to high school teachers and students as it enhances the understanding of this distinct feature of inverse square force and harmonic force.
Teaching Circuits with an Electromechanical Adder
Authors: Overduin James , Perry Jonathan , Klupt Jeffrey
Published: December 2019

Topics like series and parallel circuits are typically introduced to beginning students through entirely abstract problems, such as finding the equivalent resistance of a combination of resistors. To teach these concepts in a more context-rich way, we asked students in an introductory class how they would arrange a power supply, bulb and one or two switches to make an AND gate, a NOT gate, and an OR gate. Then, we challenged them to combine these gates to make an adder circuit with two input switches and two output bulbs that could add two numbers. Finally, we built the circuit, using large relays with transparent cases so that students can actually see (and hear) how, for example, current flows through the AND gate when both input switches are thrown. For many students, this is the first time they intuitively grasp the relevance of basic circuit concepts to the complicated devices, like computers, that we use in everyday life.
Building a Polyhedral Representation from an Instrumented Execution
Authors: Selva Manuel , Gruber Fabian , Sampaio Diogo , Guillon Christophe , Pouchet Louis-Noël , Rastello Fabrice
Published: December 2019

The polyhedral model has been successfully used in production compilers. Nevertheless, only a very restricted class of applications can benefit from it. Recent proposals investigated how runtime information could be used to apply polyhedral optimization on applications that do not statically fit the model. In this work, we go one step further in that direction. We propose the
folding-based analysis
that, from the output of an instrumented program execution, builds a compact polyhedral representation. It is able to accurately detect affine dependencies, fixed-stride memory accesses, and induction variables in programs. It scales to real-life applications, which often include some nonaffine dependencies and accesses in otherwise affine code. This is enabled by a safe fine-grained polyhedral overapproximation mechanism. We evaluate our analysis on the entire Rodinia benchmark suite, enabling accurate feedback about the potential for complex polyhedral transformations.
Lancet: Better Network Resilience by Designing for Pruned Failure Sets
Authors: Chang Yiyang , Jiang Chuan , Chandra Ashish , Rao Sanjay , Tawarmalani Mohit
Published: December 2019

Recently, researchers have started exploring the design of route protection schemes that ensure networks can sustain traffic demand without congestion under failures. Existing approaches focus on ensuring worst-case performance over simultaneous f-failure scenarios is acceptable. Unfortunately, even a single bad scenario may render the schemes unable to protect against any f-failure scenario. In this paper, we present Lancet, a system designed to handle most failures when not all can be tackled. Lancet comprises three components: (i) an algorithm to analyze which failure scenarios the network can intrinsically handle which provides a benchmark for any protection routing scheme, and guides the design of new schemes; (ii) an approach to efficiently design a protection schemes for more general failure sets than all f-failure scenarios; and (iii) techniques to determine which of combinatorially many scenarios to design for. Our evaluations with real topologies and validations on an emulation testbed show that Lancet outperforms a worst-case approach by protecting against many more scenarios, and can even match the scenarios that can be handled by optimal network response.
Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
Authors: Sinclair Sean R. , Banerjee Siddhartha , Yu Christina Lee
Published: December 2019

We present an efficient algorithm for model-free episodic reinforcement learning on large (potentially continuous) state-action spaces. Our algorithm is based on a novel Q-learning policy with adaptive data-driven discretization. The central idea is to maintain a finer partition of the state-action space in regions which are frequently visited in historical trajectories, and have higher payoff estimates. We demonstrate how our adaptive partitions take advantage of the shape of the optimal Q-function and the joint space, without sacrificing the worst-case performance. In particular, we recover the regret guarantees of prior algorithms for continuous state-action spaces, which additionally require either an optimal discretization as input, and/or access to a simulation oracle. Moreover, experiments demonstrate how our algorithm automatically adapts to the underlying structure of the problem, resulting in much better performance compared both to heuristics and Q-learning with uniform discretization.
Rateless Codes for Near-Perfect Load Balancing in Distributed Matrix-Vector Multiplication
Authors: Mallick Ankur , Chaudhari Malhar , Sheth Utsav , Palanikumar Ganesh , Joshi Gauri
Published: December 2019

Large-scale machine learning and data mining applications require computer systems to perform massive matrix-vector and matrix-matrix multiplication operations that need to be parallelized across multiple nodes. The presence of straggling nodes -- computing nodes that unpredictably slowdown or fail -- is a major bottleneck in such distributed computations. Ideal load balancing strategies that dynamically allocate more tasks to faster nodes require knowledge or monitoring of node speeds as well as the ability to quickly move data. Recently proposed fixed-rate erasure coding strategies can handle unpredictable node slowdown, but they ignore partial work done by straggling nodes thus resulting in a lot of redundant computation. We propose a rateless fountain coding strategy that achieves the best of both worlds -- we prove that its latency is asymptotically equal to ideal load balancing, and it performs asymptotically zero redundant computations. Our idea is to create linear combinations of the m rows of the matrix and assign these encoded rows to different worker nodes. The original matrix-vector product can be decoded as soon as slightly more than m row-vector products are collectively finished by the nodes. We conduct experiments in three computing environments: local parallel computing, Amazon EC2, and Amazon Lambda, which show that rateless coding gives as much as 3x speed-up over uncoded schemes.
Demystifying Complex Workload-DRAM Interactions
Authors: Ghose Saugata , Li Tianshi , Hajinazar Nastaran , Cali Damla Senol , Mutlu Onur
Published: December 2019

It has become increasingly difficult to understand the complex interactions between modern applications and main memory, composed of Dynamic Random Access Memory (DRAM) chips. Manufacturers are now selling and proposing many different types of DRAM, with each DRAM type catering to different needs (e.g., high throughput, low power, high memory density). At the same time, memory access patterns of prevalent and emerging applications are rapidly diverging, as these applications manipulate larger data sets in very different ways. As a result, the combined DRAM-workload behavior is often difficult to intuitively determine today, which can hinder memory optimizations in both hardware and software. In this work, we identify important families of workloads, as well as prevalent types of DRAM chips, and rigorously analyze the combined DRAM-workload behavior. To this end, we perform a comprehensive experimental study of the interaction between nine different DRAM types and 115 modern applications and multiprogrammed workloads. We draw 12 key observations from our characterization, enabled in part by our development of new metrics that take into account contention between memory requests due to hardware design. Notably, we find that (1) newer DRAM technologies such as DDR4 and HMC often do not outperform older technologies such as DDR3, due to higher access latencies and, also in the case of HMC, poor exploitation of locality; (2) there is no single memory type that can effectively cater to all of the components of a heterogeneous system (e.g., GDDR5 significantly outperforms other memories for multimedia acceleration, while HMC significantly outperforms other memories for network acceleration); and (3) there is still a strong need to lower DRAM latency, but unfortunately the current design trend of commodity DRAM is toward higher latencies to obtain other benefits. We hope that the trends we identify can drive optimizations in both hardware and software design. To aid further study, we open-source our extensively-modified simulator, as well as a benchmark suite containing our applications.
Nested MIMD-SIMD Parallelization for Heterogeneous Microprocessors
Authors: Gerzhoy Daniel , Sun Xiaowu , Zuzak Michael , Yeung Donald
Published: December 2019

Heterogeneous microprocessors integrate a CPU and GPU on the same chip, providing fast CPU-GPU communication and enabling cores to compute on data “in place.” This permits exploiting a finer granularity of parallelism on the integrated GPUs, and enables the use of GPUs for accelerating more complex and irregular codes. One challenge, however, is exposing enough parallelism such that both the CPU and GPU are effectively utilized to achieve maximum gain.

In this article, we propose exploiting nested parallelism for integrated CPU-GPU chips. We look for loop structures in which one or more regular data parallel loops are nested within a parallel outer loop that can contain irregular code (e.g., with control divergence). By scheduling the outer loop on multiple CPU cores, multiple dynamic instances of the inner regular loop(s) can be scheduled on the GPU cores. This boosts GPU utilization and parallelizes the outer loop. We find that such
nested MIMD-SIMD parallelization
provides greater levels of parallelism for integrated CPU-GPU chips, and additionally there is ample opportunity to perform such parallelization in OpenMP programs.

Our results show nested MIMD-SIMD parallelization provides a 16.1x and 8.67x speedup over sequential execution on a simulator and a physical machine, respectively. Our technique beats CPU-only parallelization by 4.13x and 2.40x, respectively, and GPU-only parallelization by 2.74x and 2.26x, respectively. Compared to the next-best scheme (either CPU- or GPU-only parallelization) per benchmark, our approach provides a 1.46x and 1.23x speedup for the simulator and physical machine, respectively.
Flextended Tiles
Authors: Zhao Jie , Cohen Albert
Published: December 2019

Loop tiling to exploit data locality and parallelism plays an essential role in a variety of general-purpose and domain-specific compilers. Affine transformations in polyhedral frameworks implement classical forms of rectangular and parallelogram tiling, but these lead to pipelined start with rather inefficient wavefront parallelism. Multiple extensions to polyhedral compilers evaluated sophisticated shapes such as trapezoid or diamond tiles, enabling concurrent start along the axes of the iteration space; yet these resort to custom schedulers and code generators insufficiently integrated within the general framework. One of these modified shapes referred to as overlapped tiling also lacks a unifying framework to reason about its composition with affine transformations; this prevents its application in general-purpose loop-nest optimizers and the fair comparison with other techniques. We revisit overlapped tiling, recasting it as an affine transformation on schedule trees composable with any affine scheduling algorithm. We demonstrate how to derive tighter tile shapes with less redundant computations. Our method models the traditional “scalene trapezoid” shapes and novel “right-rectangle” variants. It goes beyond the state of the art by avoiding the restriction to a domain-specific language or introducing post-pass rescheduling and custom code generation. We conduct experiments on the PolyMage benchmarks and iterated stencils, validating the effectiveness and applicability of our technique on both general-purpose multicores and GPU accelerators.
Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory
Authors: Su Lili , Zubeldia Martin , Lynch Nancy
Published: December 2019

We consider multi-armed bandit problems in social groups wherein each individual has bounded memory and shares the common goal of learning the best arm/option. We say an individual learns the best option if eventually (as t - ∞) it pulls only the arm with the highest expected reward. While this goal is provably impossible for an isolated individual due to bounded memory, we show that, in social groups, this goal can be achieved easily with the aid of social persuasion (i.e., communication) as long as the communication networks/graphs satisfy some mild conditions. In this work, we model and analyze a type of learning dynamics which are wellobserved in social groups. Specifically, under the learning dynamics of interest, an individual sequentially decides on which arm to pull next based on not only its private reward feedback but also the suggestion provided by a randomly chosen neighbor. To deal with the interplay between the randomness in the rewards and in the social interaction, we employ the mean-field approximation method. Considering the possibility that the individuals in the networks may not be exchangeable when the communication networks are not cliques, we go beyond the classic mean-field techniques and apply a refined version of mean-field approximation. Notably, our results hold even if the communication graphs are highly sparse.
Load Balancing Guardrails
Authors: Grosof Isaac , Scully Ziv , Harchol-Balter Mor
Published: December 2019

Load balancing systems, comprising a central dispatcher and a scheduling policy at each server, are widely used in practice, and their response time has been extensively studied in the theoretical literature. While much is known about the scenario where the scheduling at the servers is First-Come-First-Served (FCFS), to minimize mean response time we must use Shortest-Remaining- Processing-Time (SRPT) scheduling at the servers. Much less is known about dispatching polices when SRPT scheduling is used. Unfortunately, traditional dispatching policies that are used in practice in systems with FCFS servers often have poor performance in systems with SRPT servers. In this paper, we devise a simple fix that can be applied to any dispatching policy. This fix, called guardrails, ensures that the dispatching policy yields optimal mean response time under heavy traffic when used in a system with SRPT servers. Any dispatching policy, when augmented with guardrails, becomes heavy-traffic optimal. Our results yield the first analytical bounds on mean response time for load balancing systems with SRPT scheduling at the servers.
Inferring Catchment in Internet Routing
Authors: Sermpezis Pavlos , Kotronis Vasileios
Published: December 2019

BGP is the de-facto Internet routing protocol for interconnecting Autonomous Systems (AS). Each AS selects its preferred routes based on its routing policies, which are typically not disclosed. Due to the distributed route selection and information hiding, answering questions such as "what is the expected catchment of the anycast sites of a content provider at the AS-level, if new sites are deployed?", or "how will load-balancing behave if an ISP changes its routing policy for a prefix?", is a hard challenge. In this work, we propose a framework and methodology to infer the routing behavior in existing or hypothetical routing configurations, and provide new capabilities and insights for informative route inference (e.g., isolating the effect of randomness that is present in prior simulation-based approaches). The proposed framework can be useful in a number of applications: measurements/monitoring, traffic engineering, network planning, Internet routing models, etc.
The Segmentation-Thickness Tradeoff in Online Marketplaces
Authors: Alijani Reza , Banerjee Siddhartha , Gollapudi Sreenivas , Kollias Kostas , Munagala Kamesh
Published: December 2019

A core tension in the operations of online marketplaces is between segmentation (wherein platforms can increase revenue by segmenting the market into ever smaller sub-markets) and thickness (wherein the size of the sub-market affects the utility experienced by an agent). An important example of this is in dynamic online marketplaces, where buyers and sellers, in addition to preferences for different matches, also have finite patience (or deadlines) for being matched.We formalize this trade-off via a novel optimization problem that we term as 'Two-sided Facility Location': we consider a market wherein agents arrive at nodes embedded in an underlying metric space, where the distance between a buyer and seller captures the quality of the corresponding match. The platform posts prices and wages at the nodes, and opens a set of virtual clearinghouses where agents are routed for matching. To ensure high match-quality, the platform imposes a distance constraint between an agent and its clearinghouse; to ensure thickness, the platform requires the flow to any clearinghouse be at least a pre-specified lower bound. Subject to these constraints, the goal of the platform is to maximize the social surplus subject to weak budget balance, i.e., profit being non-negative. Our work characterizes the complexity of this problem by providing both hardness results as well as algorithms for this setting; in particular, we present an algorithm that for any constant ε > 0 yields a (1 + ε) approximation for the gains from trade, while relaxing the match quality (i.e., maximum distance of any match) by a constant factor.
Retracted on December 2, 2020
: On the Value of Look-Ahead in Competitive Online Convex Optimization
Authors: Shi Ming , Lin Xiaojun , Jiao Lei
Published: December 2019

NOTICE OF RETRACTION: "On the Value of Look-Ahead in Competitive Online Convex Optimization," by Shi et al., ACM SIGMETRICS Performance Evaluation Review, Volume 47, Issue 1, Article No. 22, has been retracted at the request of the authors because they found a critical mistake in the main result Theorem 3.1.

https://dl.acm.org/doi/10.1145/3376930.3376952
A New Flexible Multi-flow LRU Cache Management Paradigm for Minimizing Misses
Authors: Quan Guocong , Tan Jian , Eryilmaz Atilla , Shroff Ness
Published: December 2019

The Least Recently Used (LRU) caching and its variants are used in large-scale data systems in order to provide high-speed data access for a wide class of applications. Nonetheless, a fundamental question still remains: in order to minimize the miss probabilities, how should the cache space be organized to serve multiple data flows? Commonly used strategies can be categorized into two designs: pooled LRU (PLRU) caching and separated LRU (SLRU) caching. However, neither of these designs can satisfactorily solve this problem. PLRU caching is easy to implement and self-adaptive, but does not often achieve optimal or even efficient performance because its set of feasible solutions are limited. SLRU caching can be statically configured to achieve optimal performance for stationary workload, which nevertheless could suffer in a dynamically changing environment and from a cold-start problem.

To this end, we propose a new insertion based pooled LRU paradigm, named I-PLRU, where the data flows can be inserted at different positions of a pooled cache. This new design can achieve the optimal performance of the static SLRU, but retains the adaptability of PLRU for resource sharing. Theoretically, we characterize the asymptotic miss probabilities of I-PLRU, and prove that, for any given SLRU design, there always exists an I-PLRU configuration that achieves the same asymptotic miss probability, and vice versa. We next design a policy to minimize the miss probabilities. However, the miss probability minimization problem turns out to be non-convex under the I-PLRU paradigm. Notably, we utilize an equivalence mapping between I-PLRU and SLRU to efficiently find the optimal I-PLRU configuration. We prove that I-PLRU outperforms PLRU and achieves the same miss probability as the optimal SLRU under a stationary request arrival process. From an engineering perspective, the flexibility of I-PLRU avoids separating the memory space, supports dynamic and refined configurations, and alleviates the cold-start problem, potentially yielding better performance than both SLRU and PLRU.
A Distributed Algorithm to Calculate Max-Min Fair Rates Without Per-Flow State
Authors: Jose Lavanya , Ibanez Stephen , Alizadeh Mohammad , McKeown Nick
Published: December 2019

Most congestion control algorithms, like TCP, rely on a reactive control system that detects congestion, then marches carefully towards a desired operating point (e.g. by modifying the window size or adjusting a rate). In an effort to balance stability and convergence speed, they often take hundreds of RTTs to converge; an increasing problem as networks get faster, with less time to react.

This paper is about an alternative class of congestion control algorithms based on proactive-scheduling: switches and NICs "proactively" exchange control messages to run a distributed algorithm to pick "explicit rates" for each flow.We call these Proactive Explicit Rate Control (PERC) algorithms. They take as input the routing matrix and link speeds, but not a congestion signal. By exploiting information such as the number of flows at a link, they can converge an order of magnitude faster than reactive algorithms.
Global Attraction of ODE-based Mean Field Models with Hyperexponential Job Sizes
Authors: Van Houdt Benny
Published: December 2019

Mean field modeling is a popular approach to assess the performance of large scale computer systems. The evolution of many mean field models is characterized by a set of ordinary differential equations that have a unique fixed point. In order to prove that this unique fixed point corresponds to the limit of the stationary measures of the finite systems, the unique fixed point must be a global attractor. While global attraction was established for various systems in case of exponential job sizes, it is often unclear whether these proof techniques can be generalized to non-exponential job sizes.

In this paper we show how simple monotonicity arguments can be used to prove global attraction for a broad class of ordinary differential equations that capture the evolution of mean field models with hyperexponential job sizes. This class includes both existing as well as previously unstudied load balancing schemes and can be used for systems with either finite or infinite buffers.

The main novelty of the approach exists in using a Coxian representation for the hyperexponential job sizes and a partial order that is stronger than the componentwise partial order used in the exponential case.
Hyper-Scalable JSQ with Sparse Feedback
Authors: van der Boor Mark , Borst Sem , van Leeuwaarden Johan
Published: December 2019

Load balancing algorithms play a vital role in enhancing performance in data centers and cloud networks. Due to the massive size of these systems, scalability challenges, and especially the communication overhead associated with load balancing mechanisms, have emerged as major concerns. Motivated by these issues, we introduce and analyze a novel class of load balancing schemes where the various servers provide occasional queue updates to guide the load assignment.

We show that the proposed schemes strongly outperform JSQ(d) strategies with comparable communication overhead per job, and can achieve a vanishing waiting time in the many-server limit with just one message per job, just like the popular JIQ scheme. The proposed schemes are particularly geared however towards the sparse feedback regime with less than one message per job, where they outperform corresponding sparsified JIQ versions.

We investigate fluid limits for synchronous updates as well as asynchronous exponential update intervals. The fixed point of the fluid limit is identified in the latter case, and used to derive the queue length distribution. We also demonstrate that in the ultralow feedback regime the mean stationary waiting time tends to a constant in the synchronous case, but grows without bound in the asynchronous case.
Two Extensions of Kingman's GI/G/1 Bound
Authors: Ciucu Florin , Poloczek Felix
Published: December 2019

A simple bound in GI/G/1 queues was obtained by Kingman using a discrete martingale transform [5]. We extend this technique to 1) multiclass (GI/G/1 queues and 2) Markov Additive Processes (MAPs) whose background processes can be time-inhomogeneous or have an uncountable state-space. Both extensions are facilitated by a necessary and sufficient ordinary differential equation (ODE) condition for MAPs to admit continuous martingale transforms. Simulations show that the bounds on waiting time distributions are almost exact in heavy-traffic, including the cases of 1) heterogeneous input, e.g., mixing Weibull and Erlang-k classes and 2) Generalized Markovian Arrival Processes, a new class extending the Batch Markovian Arrival Processes to continuous batch sizes.
The Bayesian Prophet
Authors: Vera Alberto , Banerjee Siddhartha
Published: December 2019

Motivated by the success of using black-box predictive algorithms as subroutines for online decision-making, we develop a new framework for designing online policies given access to an oracle providing statistical information about an offline benchmark. Having access to such prediction oracles enables simple and natural Bayesian selection policies, and raises the question as to how these policies perform in different settings. Our work makes two important contributions towards tackling this question: First, we develop a general technique we call compensated coupling which can be used to derive bounds on the expected regret (i.e., additive loss with respect to a benchmark) for any online policy and offline benchmark; Second, using this technique, we show that the Bayes Selector has constant expected regret (i.e., independent of the number of arrivals and resource levels) in any online packing and matching problem with a finite type-space. Our results generalize and simplify many existing results for online packing and matching problems, and suggest a promising pathway for obtaining oracle-driven policies for other online decision-making settings.
Model Agnostic Time Series Analysis via Matrix Estimation
Authors: Agarwal Anish , Jehangir Amjad Muhammad , Shah Devavrat , Shen Dennis
Published: December 2019

We propose an algorithm to impute and forecast a time series by transforming the observed time series into a matrix, utilizing matrix estimation to recover missing values and de-noise observed entries, and performing linear regression to make predictions. At the core of our analysis is a representation result, which states that for a large class of models, the transformed time series matrix is (approximately) low-rank. In effect, this generalizes the widely used Singular Spectrum Analysis (SSA) in the time series literature, and allows us to establish a rigorous link between time series analysis and matrix estimation. The key to establishing this link is constructing a Page matrix with non-overlapping entries rather than a Hankel matrix as is commonly done in the literature (e.g., SSA). This particular matrix structure allows us to provide finite sample analysis for imputation and prediction, and prove the asymptotic consistency of our method. Another salient feature of our algorithm is that it is model agnostic with respect to both the underlying time dynamics and the noise distribution in the observations. The noise agnostic property of our approach allows us to recover the latent states when only given access to noisy and partial observations a la a Hidden Markov Model; e.g., recovering the time-varying parameter of a Poisson process without knowing that the underlying process is Poisson. Furthermore, since our forecasting algorithm requires regression with noisy features, our approach suggests a matrix estimation based method-coupled with a novel, non-standard matrix estimation error metric-to solve the error-in-variable regression problem, which could be of interest in its own right. Through synthetic and real-world datasets, we demonstrate that our algorithm outperforms standard software packages (including R libraries) in the presence of missing data as well as high levels of noise.
Batman or the joker?
Authors: Fu Kaiqun , Alhamadani Abdulaziz , Ji Taoran , Lu Chang-Tien
Published: December 2019

The exponential growth of the urban data generated by urban sensors, government reports, and crowd-sourcing services endorses the rapid development of urban computing and spatial data mining technologies. Easier accessibility to such enormous urban data may be a double-bladed sword. On the one hand, urban data can be applied to solve a wide range of practical issues such as urban safety analysis and urban event detection. On the other hand, ethical issues such as biasedly polluted urban data, problematic algorithms, and unprotected privacy may cause moral disaster not only for the research fields but also for the society. This paper seeks to identify ethical vulnerabilities from three primary research directions of urban computing: urban safety analysis, urban transportation analysis, and social media analysis for urban events. Visions for future improvements in the perspective of ethics are addressed.
The GPGCD algorithm with the Bézout matrix
Authors: Chi Boming , Terui Akira
Published: December 2019

With the progress of algebraic computations on polynomials and matrices, we are paying more attention to approximate algebraic algorithms. Among approximate algebraic algorithms, those for calculating approximate greatest common divisor (GCD) consider a pair of given polynomials
f
and
g
that are relatively prime in general, and find f and g which are close to
f
and
g
, respectively, in the sense of polynomial norm, and have the GCD of certain degree. The algorithms can be classified into two categories: 1) for a given tolerance (magnitude) of ||
f
- f|| and ||
g
- g||, make the degree of approximate GCD as large as possible, and 2) for a given degree
d
, minimize the magnitude of ||
f
- f|| and ||
g
- g||.
A family of schemes for multiplying 3 × 3 matrices with 23 coefficient multiplications
Authors: Heule Marijn , Kauers Manuel , Seidl Martina
Published: December 2019

We present a 17-dimensional family of multiplication schemes for 3×3 matrices with 23 multiplications applicable to arbitrary coefficient rings.
Robust computation methods for sparse interpolation of multivariate polynomials
Authors: Kondo Kazuki , Sekigawa Hiroshi
Published: December 2019

For the problem of sparse interpolation of multivariate polynomials, we propose robust computation methods based on the modified numerical Ben-Or/Tiwari algorithm by M. Giesbrecht, G. Labahn, and W.-s. Lee.
Sequencing and Analyzing the Transcriptomes of a Thousand Species Across the Tree of Life for Green Plants
Authors: Wong Gane Ka-Shu , Soltis Douglas E. , Leebens-Mack Jim , Wickett Norman J. , Barker Michael S. , Van de Peer Yves , Graham Sean W. , Melkonian Michael
Published: December 2019

The 1,000 Plants (1KP) initiative was the first large-scale effort to collect next-generation sequencing (NGS) data across a phylogenetically representative sampling of species for a major clade of life, in this case the Viridiplantae, or green plants. As an international multidisciplinary consortium, we focused on plant evolution and its practical implications. Among the major outcomes were the inference of a reference species tree for green plants by phylotranscriptomic analysis of low-copy genes, a survey of paleopolyploidy (whole-genome duplications) across the Viridiplantae, the inferred evolutionary histories for many gene families and biological processes, the discovery of novel light-sensitive proteins for optogenetic studies in mammalian neuroscience, and elucidation of the genetic network for a complex trait (C4photosynthesis). Altogether, 1KP demonstrated how value can be extracted from a phylodiverse sequencing data set, providing a template for future projects that aim to generate even more data, including complete de novo genomes, across the tree of life.
TRPM4 channel inhibitors 9-phenanthrol and glibenclamide differentially decrease guinea pig detrusor smooth muscle whole-cell cation currents and phasic contractions
Authors: Malysz John , Maxwell Sarah E. , Yarotskyy Viktor , Petkov Georgi V.
Published: December 2019

Nonselective cation channels, consistent with transient receptor potential melastatin-4 (TRPM4), regulate detrusor smooth muscle (DSM) function. TRPM4 channels can exist as homomers or assemble with sulfonylurea receptors (SURs) as complexes. We evaluated contributions of TRPM4/SUR-TRPM4 channels to DSM excitability and contractility by examining the effects of TRPM4/SUR-TRPM4 channel modulators 9-phenanthrol, glibenclamide, and diazoxide on freshly-isolated guinea pig DSM cells (amphotericin-B perforated patch-clamp electrophysiology) and mucosa-free DSM strips (isometric tension recordings). In DSM cells, complete removal of extracellular Na+ decreased voltage-step-induced cation (non-K+ selective) currents. At high positive membrane potentials, 9-phenanthrol at 100 μM attenuated voltage step-induced currents more effectively than at 30 μM, revealing concentration-dependent, voltage-sensitive inhibition. In comparison to 9-phenanthrol, glibenclamide (100 μM) displayed lower inhibition of cation currents. In the presence of glibenclamide (100 μM), 9-phenanthrol (100 μM) further decreased the currents. The SUR-TRPM4 complex activator diazoxide (100–300 μM) weakly inhibited the currents. 9-Phenanthrol, but not glibenclamide or diazoxide, increased cell capacitance (a cell surface area indicator). In contractility studies, glibenclamide displayed lower potencies than 9-phenanthrol attenuating spontaneous and 20 mM KCl-induced DSM phasic contractions. While both compounds showed similar maximum inhibitions on DSM spontaneous phasic contractions, glibenclamide was generally less efficacious on 20 mM KCl-induced phasic contractions. In summary, the observed differential effects of 9-phenanthrol and glibenclamide on DSM excitability and contractility support unique mechanisms for the two compounds. The data suggest that SUR-TRPM4 complexes do not contribute to DSM function. This study advances our understanding of pharmacological effects of glibenclamide and 9-phenanthrol on DSM cell cation currents.
Serum amyloid A3 confers protection against acute lung injury inPseudomonas aeruginosa-infected mice
Authors: Fan Yu , Zhang Gufang , Vong Chi Teng , Ye Richard D.
Published: December 2019

Pseudomonas aeruginosa is a gram-negative bacterium associated with serious illnesses, including ventilator-associated pneumonia and various sepsis syndromes in humans. Understanding the host immune mechanisms against P. aeruginosa is, therefore, of clinical importance. The present study identified serum amyloid A3 (SAA3) as being highly inducible in mouse bronchial epithelium following P. aeruginosa infection. Genetic deletion of Saa3 rendered mice more susceptible to P. aeruginosa infection with decreased neutrophil superoxide anion production, and ex vivo treatment of mouse neutrophils with recombinant SAA3 restored the ability of neutrophils to produce superoxide anions. The SAA3-deficient mice showed exacerbated inflammatory responses, which was characterized by pronounced neutrophil infiltration, elevated expression of TNF-α, KC/CXCL1, and MIP-2/CXCL2 in bronchoalveolar lavage fluid (BALF), and increased lung microvascular permeability compared with their wild-type littermates. BALF neutrophils from Saa3 knockout mice exhibited reduced superoxide anion production compared with neutrophils from wild-type mice. Adoptive transfer of SAA3-treated neutrophils to Saa3 knockout mice ameliorated P. aeruginosa-induced acute lung injury. These findings demonstrate that SAA3 not only serves as a biomarker for infection and inflammation, but also plays a protective role against P. aeruginosa infection-induced lung injury in part through augmentation of neutrophil bactericidal functions.
Synergist ablation-induced hypertrophy occurs more rapidly in the plantaris than soleus muscle in rats due to different molecular mechanisms
Authors: Roberts Michael D. , Mobley Christopher B. , Vann Christopher G. , Haun Cody T. , Schoenfeld Brad J. , Young Kaelin C. , Kavazis Andreas N.
Published: December 2019

We examined molecular mechanisms that were altered during rapid soleus (type I fiber-dominant) and plantaris (type II fiber-dominant) hypertrophy in rats. Twelve Wistar rats (3.5 mo old; 6 female, 6 male) were subjected to surgical right-leg soleus and plantaris dual overload [synergist ablation (SA)], and sham surgeries were performed on left legs (CTL). At 14 days after surgery, the muscles were dissected. Plantaris mass was 27% greater in the SA than CTL leg ( P < 0.001), soleus mass was 13% greater in the SA than CTL leg ( P < 0.001), and plantaris mass was higher than soleus mass in the SA leg ( P = 0.001). Plantaris total RNA concentrations and estimated total RNA levels (suggestive of ribosome density) were 19% and 47% greater in the SA than CTL leg ( P < 0.05), protein synthesis levels were 64% greater in the SA than CTL leg ( P = 0.038), and satellite cell number per fiber was 60% greater in the SA than CTL leg ( P = 0.003); no differences in these metrics were observed between soleus SA and CTL legs. Plantaris, as well as soleus, 20S proteasome activity was lower in the SA than CTL leg ( P < 0.05), although the degree of downregulation was greater in the plantaris than soleus muscle (−63% vs. −20%, P = 0.001). These data suggest that early-phase plantaris hypertrophy occurs more rapidly than soleus hypertrophy, which coincided with greater increases in ribosome biogenesis, protein synthesis, and satellite cell density, as well as greater decrements in 20S proteasome activity, in the plantaris muscle.