bluuebunny/crossref_metadata_2025 huggingface dataset:
Paradox of otolith shape indices: routine but overestimated use
Authors: Tuset Víctor Manuel , Otero-Ferrer José Luis , Siliprandi Carolina , Manjabacas Amalia , Marti-Puig Pere , Lombarte Antoni
Published: January 2021

The identification of fish species using otolith shape has been common in many fields of the marine science. Different analytical processes can be applied for the morphological discrimination, but reviewing the literature we have found conceptual and statistical limitations in the use of shape indices and wavelets (contour analysis), being specially worrying in the first case due to their widespread routine use. In the present study, 42 species were classified using otolith shape indices and wavelets and applying traditional and machine learning classifiers and performance measures (accuracy, Cohen’s kappa statistic, sensitivity, and precision). Our results were conclusive; wavelets were a more adequate option for the classification of species than shape indices, independently of classifiers and performance measures considered. The artificial neural network and support vector machine provided the highest values for all performance measures using wavelets. In all cases, the measures of sensitivity and precision pointed out a higher confusion between some otolith patterns using shape indices. Therefore, we strongly discourage the routine use of shape indices for the identification of species.
Super Ck and Sub-Ck Connectivity of k-Ary n-Cube Networks
Authors: Yang Yuxing
Published: January 2021

Let [Formula: see text] be an undirected graph. An [Formula: see text]-structure-cut (resp. [Formula: see text]-substructure-cut) of [Formula: see text] is a set of subgraphs of [Formula: see text], if any, whose deletion disconnects [Formula: see text], where the subgraphs deleted are isomorphic to a certain graph [Formula: see text] (resp. where for any [Formula: see text] of the subgraphs deleted, there is a subgraph [Formula: see text] of [Formula: see text], isomorphic to [Formula: see text], such that [Formula: see text] is a subgraph of [Formula: see text]). [Formula: see text] is super[Formula: see text]-connected (resp. super sub-[Formula: see text]-connected) if the deletion of an arbitrary minimum [Formula: see text]-structure-cut (resp. minimum [Formula: see text]-substructure-cut) isolates a component isomorphic to a certain graph [Formula: see text]. The [Formula: see text]-ary [Formula: see text]-cube [Formula: see text] is one of the most attractive interconnection networks for multiprocessor systems. In this paper, we prove that [Formula: see text] with [Formula: see text] is super sub-[Formula: see text]-connected if [Formula: see text] and [Formula: see text] is odd, and super [Formula: see text]-connected if [Formula: see text] and [Formula: see text] is odd.
A Risk Measurement Model of China’s Non-Ferrous Metal Futures Market
Authors: Shen Hong , Zhang Jinling , Li Xu , Ng Pin T.
Published: January 2021

With the impact of foreign exchange markets, risks in financial markets are becoming more complex and diversified, which underlines the importance of risk management in financial supervision. In this paper, China’s non-ferrous metal futures market is selected as the research object, and Shanghai Futures Exchange’s Industrial Metal Commodity Index (IMCI) data are used to measure risk using the conditional autoregressive value at risk (CAViaR) model. The US dollar index (USDX) is incorporated into the CAViaR model to study its impact on the risk. Through empirical analysis, we arrive at the following conclusions: First, the asymmetric slope CAViaR model (AS-CAViaR) is more suitable for measuring the risk in China’s non-ferrous metal futures market. Second, the risk is positively impacted by the lagged risk. Moreover, the impacts of positive and negative returns on the risk are asymmetric, with a negative return having a greater impact. Third, the positive and negative shock of USDX has significant and different impacts on the risk. These impacts can be caused by global capital flows. In addition, the impact of the vector of explanatory variables on the IMCI at different quantile levels is discussed based on the CAViaR-USDX model, which reflects the comprehensive advantages of the quantile regression method and the model’s applicability. The above conclusions verify the impact of USDX on China’s non-ferrous metal futures market and provide a theoretical basis and direction for risk monitoring.
General teleparallel modifications of Schwarzschild geometry
Authors: Bahamonde Sebastian , Pfeifer Christian
Published: January 2021

Teleparallel theories of gravity are described in terms of the tetrad of a metric and a flat connection with torsion. In this paper, we study spherical symmetry in a modified teleparallel theory of gravity which is based on an arbitrary function of the five possible scalars constructed from the irreducible parts of torsion. This theory is a generalization of the so-called New General Relativity theory. We find that only two scalars are different to zero in spherical symmetry and we solve the corresponding field equations analytically for conformal Teleparallel gravity, and then perturbatively around Schwarzschild geometry for the general perturbative theory around GR. Finally, we compute phenomenological effects from the perturbed solutions such as the photon sphere, perihelion shift, Shapiro delay, and the light deflection. We find their correspondent correction to the standard GR contribution and their dependence on the three model parameters.
Framework to Evaluate Seismic Fragility of Bridges Considering Component Damage Correlations
Authors: Kim Ji-Su , Park Woo-Seong , Han Tong-Seok
Published: January 2021

The objective of this study is to propose a framework for evaluating the seismic fragility of bridge systems analytically taking into account correlations between component behaviors. To include coupled effects of component behaviors on system behavior, the second-order reliability approach is adopted. The damage states of the combined fragility are proposed based on system behavior characteristics obtained by pushover analyses. The characteristics of the combined fragility information of two bridge models are illustrated using probabilistic seismic demand analysis based on the time history analysis results from several earthquake excitations. The fragility curves obtained from the second-order reliability model are compared with the first-order reliability model. It is shown that the proposed framework can provide more detailed fragility information rather than only providing bounds of system fragility as in the first-order reliability-based approach.
Welcome to AI Matters 6(1)
Authors: McGovern Amy , Leite Iolanda , Karpatne Anuj
Published: January 2021

This issue is smaller than usual as a reflection to the disruptions caused by the on-going COVID-19 pandemic on the scientific community. We open with a call for funding by SIGAI Executive Committe Chair, Sanmay Das, to support AI activities promoting outreach. In our regular articles, we provide an event report by Michael Albert and John P Dickerson on the AAAI/ACM SIGAI Job Fair. In the policy column, Larry Medsker and Farhana Faruqe cover a new series on AI and Bias on the Policy Matters Blog with a commentary on Bias, Fairness, and Discrimination in the context of AI, along with discussions on AI policy issues with respect to work and timeframe for AI impact. Another regular column is our AI crosswords from Adi Botea. We have one contributed article from Cameron Hughes and Tracey Hughes on what constitutes the essential ingredients for AI in a world where AI is increasingly pervading in every walk of life. Enjoy!
Towards AI ingredients
Authors: Hughes Cameron , Hughes Tracey
Published: January 2021

We have AI in our cars, in our mobile phones, and AI in our video games. We have AI in medicine, AI in the military applications, and AI in government agencies. It's getting harder to find an aspect of our daily lives that doesn't purport to have some kind of interaction with AI. We are relinquishing more of the personal and professional decision-making process to vestiges of evolving notions of AI. Not only are we starting to defer to AI for the decisionmaking process, we are subtly transferring the ultimate responsibility for the decisions and the consequences of those decisions to the AI. The public's acceptance and reliance on various aspects of AI is becoming normalized. One major problem with this scenario is that we as a society are unclear about what constitutes AI. Our social position on AI is: we may not be able to concisely or correctly define it, but we all know it when we see it, right? Clearly the integral part that AI has in our society makes this position untenable and we can and should do better with our definition.
Data-driven Distributionally Robust Optimization For Vehicle Balancing of Mobility-on-Demand Systems
Authors: Miao Fei , He Sihong , Pepin Lynn , Han Shuo , Hendawi Abdeltawab , Khalefa Mohamed E , Stankovic John A. , Pappas George
Published: January 2021

With the transformation to smarter cities and the development of technologies, a large amount of data is collected from sensors in real time. Services provided by ride-sharing systems such as taxis, mobility-on-demand autonomous vehicles, and bike sharing systems are popular. This paradigm provides opportunities for improving transportation systems’ performance by allocating ride-sharing vehicles toward predicted demand proactively. However, how to deal with uncertainties in the predicted demand probability distribution for improving the average system performance is still a challenging and unsolved task. Considering this problem, in this work, we develop a data-driven distributionally robust vehicle balancing method to minimize the worst-case expected cost. We design efficient algorithms for constructing uncertainty sets of demand probability distributions for different prediction methods and leverage a quad-tree dynamic region partition method for better capturing the dynamic spatial-temporal properties of the uncertain demand. We then derive an equivalent computationally tractable form for numerically solving the distributionally robust problem. We evaluate the performance of the data-driven vehicle balancing algorithm under different demand prediction and region partition methods based on four years of taxi trip data for New York City (NYC). We show that the average total idle driving distance is reduced by 30% with the distributionally robust vehicle balancing method using quad-tree dynamic region partitions, compared with vehicle balancing methods based on static region partitions without considering demand uncertainties. This is about a 60-million-mile or a 8-million-dollar cost reduction annually in NYC.
Highly Concurrent Latency-tolerant Register Files for GPUs
Authors: Sadrosadati Mohammad , Mirhosseini Amirhossein , Hajiabadi Ali , Ehsani Seyed Borna , Falahati Hajar , Sarbazi-Azad Hamid , Drumond Mario , Falsafi Babak , Ausavarungnirun Rachata , Mutlu Onur
Published: January 2021

Graphics Processing Units (GPUs) employ large register files to accommodate all active threads and accelerate context switching. Unfortunately, register files are a scalability bottleneck for future GPUs due to long access latency, high power consumption, and large silicon area provisioning. Prior work proposes hierarchical register file to reduce the register file power consumption by caching registers in a smaller register file cache. Unfortunately, this approach does not improve register access latency due to the low hit rate in the register file cache.

In this article, we propose the Latency-Tolerant Register File (LTRF) architecture to achieve low latency in a two-level hierarchical structure while keeping power consumption low. We observe that compile-time interval analysis enables us to divide GPU program execution into intervals with an accurate estimate of a warp’s aggregate register working-set within each interval. The key idea of LTRF is to prefetch the estimated register working-set from the main register file to the register file cache under software control, at the beginning of each interval, and overlap the prefetch latency with the execution of other warps. We observe that register bank conflicts while prefetching the registers could greatly reduce the effectiveness of LTRF. Therefore, we devise a compile-time register renumbering technique to reduce the likelihood of register bank conflicts. Our experimental results show that LTRF enables high-capacity yet long-latency main GPU register files, paving the way for various optimizations. As an example optimization, we implement the main register file with emerging high-density high-latency memory technologies, enabling 8× larger capacity and improving overall GPU performance by 34%.
Attention-Gated Graph Convolutions for Extracting Drug Interaction Information from Drug Labels
Authors: Tran Tung , Kavuluru Ramakanth , Kilicoglu Halil
Published: January 2021

Preventable adverse events as a result of medical errors present a growing concern in the healthcare system. As drug-drug interactions (DDIs) may lead to preventable adverse events, being able to extract DDIs from drug labels into a machine-processable form is an important step toward effective dissemination of drug safety information. Herein, we tackle the problem of jointly extracting mentions of drugs and their interactions, including interactionoutcome, from drug labels. Our deep learning approach entails composing various intermediate representations, including graph-based context derived using graph convolutions (GCs) with a novel attention-based gating mechanism (holistically called GCA), which are combined in meaningful ways to predict on all subtasks jointly. Our model is trained and evaluated on the 2018 TAC DDI corpus. Our GCA model in conjunction with transfer learning performs at 39.20% F1 and 26.09% F1 on entity recognition (ER) and relation extraction (RE), respectively, on the first official test set and at 45.30% F1 and 27.87% F1 on ER and RE, respectively, on the second official test set. These updated results lead to improvements over our prior best by up to 6 absolute F1 points. After controlling for available training data, the proposed model exhibits state-of-the-art performance for this task.
ForSyDe-Atom
Authors: Ungureanu George , Medeiros José Edil Guimarães De , sundström Timmy , Söderquist Ingemar , Åhlander Anders , Sander Ingo
Published: January 2021

We present ForSyDe-Atom, a formal framework intended as an entry point for disciplined design of complex cyber-physical systems. This framework provides a set of rules for combining several domain-specific languages as structured, enclosing
layers
to
orthogonalize
the many aspects of system behavior, yet study their interaction
in tandem
. We define four layers: one for capturing timed interactions in heterogeneous systems, one for structured parallelism, one for modeling uncertainty, and one for describing component properties. This framework enables a systematic exploitation of design properties in a design flow by facilitating the stepwise
projection
of certain layers of interest, the isolated analysis and
refinement
on projections, and the seamless
reconstruction
of a system model by virtue of orthogonalization. We demonstrate the capabilities of this approach by providing a compact yet expressive model of an active electronically scanned array antenna and signal processing chain, simulate it, validate its conformity with the design specifications, refine it, synthesize a sub-system to VHDL and sequential code, and co-simulate the generated artifacts.
HARP
Authors: Wang Yashen , Zhang Huanhuan
Published: January 2021

Recent years have witnessed great advancement of representation learning (RL)-based models for the knowledge graph relation prediction task. However, they generally rely on structure information embedded in the encyclopedic knowledge graph, while the beneficial semantic information provided by lexical knowledge graph is ignored, leading the problem of shallow understanding and coarse-grained analysis for knowledge acquisition. Therefore, this article introduces concept information derived from the lexical knowledge graph (e.g., Probase), and proposes a novel Hierarchical Attention model for Relation Prediction, which consists of entity-level attention mechanism and concept-level attention mechanism, to throughly integrate multiple semantic signals. Experimental results demonstrate the efficiency of the proposed method on two benchmark datasets.
An Exponential Factorization Machine with Percentage Error Minimization to Retail Sales Forecasting
Authors: Li Chongshou , Cheang Brenda , Luo Zhixing , Lim Andrew
Published: January 2021

This article proposes a new approach to sales forecasting for new products (stock-keeping units [SKUs]) with long lead time but short product life cycle. These SKUs are usually sold for one season only, without any replenishments. An exponential factorization machine (EFM) sales forecast model is developed to solve this problem which not only takes into account SKU attributes, but also pairwise interactions. The EFM model is significantly different from the original Factorization Machines (FM) from two fold: (1) the attribute-level formulation for explanatory/input variables; and (2) exponential formulation for the positive response/output/target variable. The attribute-level formation excludes infeasible intra-attribute interactions and results in more efficient feature engineering comparing with the conventional one-hot encoding, while the exponential formulation is demonstrated more effective than the log-transformation for the positive but not skewed distributed responses. In order to estimate the parameters, percentage error squares (PES) and error squares (ES) are minimized by a proposed adaptive batch gradient descent method over the training set. To overcome the over-fitting problem, a greedy forward stepwise feature selection method is proposed to select the most useful attributes and interactions. Real-world data provided by a footwear retailer in Singapore are used for testing the proposed approach. The forecasting performance in terms of both mean absolute percentage error (MAPE) and mean absolute error (MAE) compares favorably with not only off-the-shelf models but also results reported by extant sales and demand forecasting studies. The effectiveness of the proposed approach is also demonstrated by two external public datasets. Moreover, we prove the theoretical relationships between PES and ES minimization, and present an important property of the PES minimization for regression models; that it trains models to underestimate data. This property fits the situation of sales forecasting where unit-holding cost is much greater than the unit-shortage cost (e.g., perishable products).
Heuristic Computation Offloading Algorithms for Mobile Users in Fog Computing
Authors: Li Keqin
Published: January 2021

The investigation in this article makes the following important contributions to combinatorial optimization of computation offloading in fog computing. First, we rigorously define the two problems of optimal computation offloading with energy constraint and optimal computation offloading with time constraint. We do this in such a way that between execution time and energy consumption, we can fix one and minimize the other. We prove that our optimization problems are NP-hard, even for very special cases. Second, we develop a unique and effective approach for solving the proposed combinatorial optimization problems, namely, a two-stage method. In the first stage, we generate a computation offloading strategy. In the second stage, we decide the computation speed and the communication speeds. This method is applicable to both optimization problems. Third, we use a simple yet efficient greedy method to produce a computation offloading strategy by taking all aspects into consideration, including the properties of the communication channels, the power consumption models of computation and communication, the tasks already assigned and allocated, and the characteristics of the current task being considered. Fourth, we experimentally evaluate the performance of our heuristic algorithms. We observe that while various heuristics do exhibit noticeably different performance, there can be a single and simple heuristic that can perform very well. Furthermore, the method of compound algorithm can be applied to obtain slightly improved performance. Fifth, we emphasize that our problems and algorithms can be easily extended to study combined performance and cost optimization (such as cost–performance ratio and weighted cost-performance sum optimization) and to accommodate more realistic and complicated fog computing environments (such as preloaded mobile edge servers and multiple users) with little extra effort. To the best of our knowledge, there has been no similar study in the existing fog computing literature.
Reducing Energy in GPGPUs through Approximate Trivial Bypassing
Authors: Atoofian Ehsan , Shaikh Zayan , Jannesari Ali
Published: January 2021

General-purpose computing using graphics processing units (GPGPUs) is an attractive option for acceleration of applications with massively data-parallel tasks. While performance of modern GPGPUs is increasing rapidly, the power consumption of these devices is becoming a major concern. In particular, execution units and register file are among the top three most power-hungry components in GPGPUs. In this work, we exploit trivial instructions to reduce power consumption in GPGPUs.

Trivial instructions are those instructions that do not need computations, i.e., multiplication by one. We found that, during the course of a program's execution, a GPGPU executes many trivial instructions. Execution of these instructions wastes power unnecessarily. In this work, we propose trivial bypassing which skips execution of trivial instructions and avoids unnecessary allocation of resources for trivial instructions. By power gating execution units and skipping trivial computing, trivial bypassing reduces both static and dynamic power. Also, trivial bypassing reduces dynamic energy of register file by avoiding access to register file for source and/or destination operands of trivial instructions. While trivial bypassing reduces energy of GPGPUs, it has detrimental impact on performance as a power-gated execution unit requires several cycles to resume its normal operation. Conventional warp schedulers are oblivious to the status of execution units. We propose a new warp scheduler that prioritizes warps based on availability of execution units. We also propose a set of new power management techniques to reduce performance penalty of power gating, further. To increase energy saving of trivial bypassing, we also propose approximating operands of instructions. We offer a set of new techniques to approximate both integer and floating-point instructions and increase the pool of trivial instructions. Our evaluations using a diverse set of benchmarks reveal that our proposed techniques are able to reduce energy of execution units by 11.2% and dynamic energy of register file by 12.2% with minimal performance and quality degradation.
Probabilistic Estimation of Threat Intrusion in Embedded Systems for Runtime Detection
Authors: Carreon Nadir A. , Lu Sixing , Lysecky Roman
Published: January 2021

With billions of networked connected embedded systems, the security historically provided by the isolation of embedded systems is no longer sufficient. Millions of new malware are created every month and zero-day attacks are becoming an increasing concern. Therefore, proactive security measures are no longer enough to provide protection to embedded systems. Instead, reactive approaches that detect attacks that can circumvent the proactive defenses and react upon them are needed. Anomaly-based detection is a common reactive approach employed to detect malware by monitoring anomalous deviations in the system execution. Timing-based anomaly detection detects malware by monitoring the system's internal timing, which offers unique protection against mimicry malware compared to sequence-based anomaly detection. However, previous timing-based anomaly detection methods focus on each operation independently at the granularity of tasks, function calls, system calls, or basic blocks. These approaches neither consider the entire software execution path nor provide a quantitative estimate of the presence of malware. This article presents a novel model for specifying the normal timing for execution paths in software applications using cumulative distribution functions of timing data in sliding execution windows. A probabilistic formulation is used to estimate the presence of malware for individual operations and sequences of operations within the paths. Operation and path-based thresholds are determined during the training process to minimize false positives. Finally, the article presents an optimization method to assist system developers in selecting which operations to monitor based on different optimization goals and constraints. Experimental results with a smart connected pacemaker, an unmanned aerial vehicle, and seven sophisticated mimicry malware implemented at different levels demonstrate the effectiveness of the proposed approach.
User Placement and Optimal Cooling Energy for Co-working Building Spaces
Authors: Nagarathinam Srinarayana , Vasan Arunchandar , Sarangan Venkatesh , Jayaprakash Rajesh , Sivasubramaniam Anand
Published: January 2021

Increasing real estate and other infrastructure costs have resulted in the trend of co-working offices where users pay as they use for individual desks. Co-working offices that provide personalized comfort need to address users with potentially widely varying thermal comfort preferences. Providing personalized comfort in cabins separated by physical partitions with neighboring thermal zones or open-plan offices with a single actuator has received attention in the literature. In this article, the problem of minimizing user discomfort in open-plan co-working offices with multiple actuators while being cognizant of the energy consumed is considered. Specifically, the decision problems of assigning users to desks based on their thermal preferences and jointly controlling the multiple actuators are addressed. The non-linearities in the underlying thermodynamic constraints and the seating decision together make the problem computationally hard. A two-step heuristic that addresses these issues is presented. First, using a model that accounts for spatio-temporal thermodynamics, a one-time assignment of users to desks is performed that reduces the thermal resistance faced by the HVAC systems to provide the preferred comfort levels. Next, the setpoints are decided for all actuators to jointly minimize user discomfort by optimization and model-predictive control. Further, scalability is addressed by clustering user preferences and the associated HVAC actuators’ setpoints for the cases where a large number of actuators may be present in the room.
Mechanized logical relations for termination-insensitive noninterference
Authors: Gregersen Simon Oddershede , Bay Johan , Timany Amin , Birkedal Lars
Published: January 2021

We present an expressive information-flow control type system with recursive types, existential types, label polymorphism, and impredicative type polymorphism for a higher-order programming language with higher-order state. We give a novel semantic model of this type system and show that well-typed programs satisfy termination-insensitive noninterference. Our semantic approach supports compositional integration of syntactically well-typed and syntactically ill-typed---but semantically sound---components, which we demonstrate through several interesting examples. We define our model using logical relations on top of the Iris program logic framework; to capture termination-insensitivity, we develop a novel language-agnostic theory of Modal Weakest Preconditions. We formalize all of our theory and examples in the Coq proof assistant.
Probabilistic programming semantics for name generation
Authors: Sabok Marcin , Staton Sam , Stein Dario , Wolman Michael
Published: January 2021

We make a formal analogy between random sampling and fresh name generation. We show that quasi-Borel spaces, a model for probabilistic programming, can soundly interpret the ν-calculus, a calculus for name generation. Moreover, we prove that this semantics is fully abstract up to first-order types. This is surprising for an ‘off-the-shelf’ model, and requires a novel analysis of probability distributions on function spaces. Our tools are diverse and include descriptive set theory and normal forms for the ν-calculus.
Internalizing representation independence with univalence
Authors: Angiuli Carlo , Cavallo Evan , Mörtberg Anders , Zeuner Max
Published: January 2021

In their usual form, representation independence metatheorems provide an external guarantee that two implementations of an abstract interface are interchangeable when they are related by an operation-preserving correspondence. If our programming language is dependently-typed, however, we would like to appeal to such invariance results within the language itself, in order to obtain correctness theorems for complex implementations by transferring them from simpler, related implementations. Recent work in proof assistants has shown that Voevodsky's univalence principle allows transferring theorems between isomorphic types, but many instances of representation independence in programming involve non-isomorphic representations.

In this paper, we develop techniques for establishing internal relational representation independence results in dependent type theory, by using higher inductive types to simultaneously quotient two related implementation types by a heterogeneous correspondence between them. The correspondence becomes an isomorphism between the quotiented types, thereby allowing us to obtain an equality of implementations by univalence. We illustrate our techniques by considering applications to matrices, queues, and finite multisets. Our results are all formalized in Cubical Agda, a recent extension of Agda which supports univalence and higher inductive types in a computationally well-behaved way.
Data flow refinement type inference
Authors: Pavlinovic Zvonimir , Su Yusen , Wies Thomas
Published: January 2021

Refinement types enable lightweight verification of functional programs. Algorithms for statically inferring refinement types typically work by reduction to solving systems of constrained Horn clauses extracted from typing derivations. An example is Liquid type inference, which solves the extracted constraints using predicate abstraction. However, the reduction to constraint solving in itself already signifies an abstraction of the program semantics that affects the precision of the overall static analysis. To better understand this issue, we study the type inference problem in its entirety through the lens of abstract interpretation. We propose a new refinement type system that is parametric with the choice of the abstract domain of type refinements as well as the degree to which it tracks context-sensitive control flow information. We then derive an accompanying parametric inference algorithm as an abstract interpretation of a novel data flow semantics of functional programs. We further show that the type system is sound and complete with respect to the constructed abstract semantics. Our theoretical development reveals the key abstraction steps inherent in refinement type inference algorithms. The trade-off between precision and efficiency of these abstraction steps is controlled by the parameters of the type system. Existing refinement type systems and their respective inference algorithms, such as Liquid types, are captured by concrete parameter instantiations. We have implemented our framework in a prototype tool and evaluated it for a range of new parameter instantiations (e.g., using octagons and polyhedra for expressing type refinements). The tool compares favorably against other existing tools. Our evaluation indicates that our approach can be used to systematically construct new refinement type inference algorithms that are both robust and precise.
Simplifying dependent reductions in the polyhedral model
Authors: Yang Cambridge , Atkinson Eric , Carbin Michael
Published: January 2021

A Reduction – an accumulation over a set of values, using an associative and commutative operator – is a common computation in many numerical computations, including scientific computations, machine learning, computer vision, and financial analytics. Contemporary polyhedral-based compilation techniques make it possible to optimize reductions, such as prefix sums, in which each component of the reduction’s output potentially shares computation with another component in the reduction. Therefore an optimizing compiler can identify the computation shared between multiple components and generate code that computes the shared computation only once.

These techniques, however, do not support reductions that – when phrased in the language of the polyhedral model – span multiple dependent statements. In such cases, existing approaches can generate incorrect code that violates the data dependences of the original, unoptimized program.

In this work, we identify and formalize the optimization of dependent reductions as an integer bilinear program. We present a heuristic optimization algorithm that uses an affine sequential schedule of the program to determine how to simplfy reductions yet still preserve the program’s dependences.

We demonstrate that the algorithm provides optimal complexity for a set of benchmark programs from the literature on probabilistic inference algorithms, whose performance critically relies on simplifying these reductions. The complexities for 10 of the 11 programs improve siginifcantly by factors at least of the sizes of the input data, which are in the range of 10
4
to 10
6
for typical real application inputs. We also confirm the significance of the improvement by showing speedups in wall-clock time that range from 1.1x to over 10
6
x.
Intrinsically typed compilation with nameless labels
Authors: Rouvoet Arjen , Krebbers Robbert , Visser Eelco
Published: January 2021

To avoid compilation errors it is desirable to verify that a compiler is
type correct
—i.e., given well-typed source code, it always outputs well-typed target code. This can be done
intrinsically
by implementing it as a function in a dependently typed programming language, such as Agda. This function manipulates data types of well-typed source and target programs, and is therefore type correct by construction. A key challenge in implementing an intrinsically typed compiler is the representation of labels in bytecode. Because label names are global, bytecode typing appears to be inherently a non-compositional, whole-program property. The individual operations of the compiler do not preserve this property, which requires the programmer to reason about labels, which spoils the compiler definition with proof terms.

In this paper, we address this problem using a new
nameless
and
co-contextual
representation of typed global label binding, which
is
compositional. Our key idea is to use
linearity
to ensure that all labels are defined exactly once. To write concise compilers that manipulate programs in our representation, we develop a linear, dependently typed, shallowly embedded language in Agda, based on separation logic. We show that this language enables the concise specification and implementation of intrinsically typed operations on bytecode, culminating in an intrinsically typed compiler for a language with structured control-flow.
A unifying type-theory for higher-order (amortized) cost analysis
Authors: Rajani Vineet , Gaboardi Marco , Garg Deepak , Hoffmann Jan
Published: January 2021

This paper presents λ-amor, a new type-theoretic framework for amortized cost analysis of higher-order functional programs and shows that existing type systems for cost analysis can be embedded in it. λ-amor introduces a new modal type for representing potentials – costs that have been accounted for, but not yet incurred, which are central to amortized analysis. Additionally, λ-amor relies on standard type-theoretic concepts like affineness, refinement types and an indexed cost monad. λ-amor is proved sound using a rather simple logical relation. We embed two existing type systems for cost analysis in λ-amor showing that, despite its simplicity, λ-amor can simulate cost analysis for different evaluation strategies (call-by-name and call-by-value), in different styles (effect-based and coeffect-based), and with or without amortization. One of the embeddings also implies that λ-amor is relatively complete for all terminating PCF programs.
An abstract interpretation for SPMD divergence on reducible control flow graphs
Authors: Rosemann Julian , Moll Simon , Hack Sebastian
Published: January 2021

Vectorizing compilers employ divergence analysis to detect at which program point a specific variable is uniform, i.e. has the same value on all SPMD threads that execute this program point. They exploit uniformity to retain branching to counter branch divergence and defer computations to scalar processor units. Divergence is a hyper-property and is closely related to non-interference and binding time. There exist several divergence, binding time, and non-interference analyses already but they either sacrifice precision or make significant restrictions to the syntactical structure of the program in order to achieve soundness.

In this paper, we present the first abstract interpretation for uniformity that is general enough to be applicable to reducible CFGs and, at the same time, more precise than other analyses that achieve at least the same generality.

Our analysis comes with a correctness proof that is to a large part mechanized in Coq. Our experimental evaluation shows that the compile time and the precision of our analysis is on par with LLVM's default divergence analysis that is only sound on more restricted CFGs. At the same time, our analysis is faster and achieves better precision than a state-of-the-art non-interference analysis that is sound and at least as general as our analysis.
Automata and fixpoints for asynchronous hyperproperties
Authors: Gutsfeld Jens Oliver , Müller-Olm Markus , Ohrem Christoph
Published: January 2021

Hyperproperties have received increasing attention in the last decade due to their importance e.g. for security analyses. Past approaches have focussed on synchronous analyses, i.e. techniques in which different paths are compared lockstepwise. In this paper, we systematically study asynchronous analyses for hyperproperties by introducing both a novel automata model (Alternating Asynchronous Parity Automata) and the temporal fixpoint calculus
H
µ
, the first fixpoint calculus that can systematically express hyperproperties in an asynchronous manner and at the same time subsumes the existing logic HyperLTL. We show that the expressive power of both models coincides over fixed path assignments. The high expressive power of both models is evidenced by the fact that decision problems of interest are highly undecidable, i.e. not even arithmetical. As a remedy, we propose approximative analyses for both models that also induce natural decidable fragments.
Context-bounded verification of liveness properties for multithreaded shared-memory programs
Authors: Baumann Pascal , Majumdar Rupak , Thinniyam Ramanathan S. , Zetzsche Georg
Published: January 2021

We study context-bounded verification of liveness properties of multi-threaded, shared-memory programs, where each thread can spawn additional threads. Our main result shows that context-bounded fair termination is decidable for the model; context-bounded implies that each spawned thread can be context switched a fixed constant number of times. Our proof is technical, since fair termination requires reasoning about the composition of unboundedly many threads each with unboundedly large stacks. In fact, techniques for related problems, which depend crucially on replacing the pushdown threads with finite-state threads, are not applicable. Instead, we introduce an extension of vector addition systems with states (VASS), called VASS with balloons (VASSB), as an intermediate model; it is an infinite-state model of independent interest. A VASSB allows tokens that are themselves markings (balloons). We show that context bounded fair termination reduces to fair termination for VASSB. We show the latter problem is decidable by showing a series of reductions: from fair termination to configuration reachability for VASSB and thence to the reachability problem for VASS. For a lower bound, fair termination is known to be non-elementary already in the special case where threads run to completion (no context switches).

We also show that the simpler problem of context-bounded termination is 2EXPSPACE-complete, matching the complexity bound---and indeed the techniques---for safety verification. Additionally, we show the related problem of fair starvation, which checks if some thread can be starved along a fair run, is also decidable in the context-bounded case. The decidability employs an intricate reduction from fair starvation to fair termination. Like fair termination, this problem is also non-elementary.
A practical mode system for recursive definitions
Authors: Reynaud Alban , Scherer Gabriel , Yallop Jeremy
Published: January 2021

In call-by-value languages, some mutually-recursive definitions can be safely evaluated to build recursive functions or cyclic data structures, but some definitions (let rec x = x + 1) contain vicious circles and their evaluation fails at runtime. We propose a new static analysis to check the absence of such runtime failures.

We present a set of declarative inference rules, prove its soundness with respect to the reference source-level semantics of Nordlander, Carlsson, and Gill [2008], and show that it can be directed into an algorithmic backwards analysis check in a surprisingly simple way.

Our implementation of this new check replaced the existing check used by the OCaml programming language, a fragile syntactic criterion which let several subtle bugs slip through as the language kept evolving. We document some issues that arise when advanced features of a real-world functional language (exceptions in first-class modules, GADTs, etc.) interact with safety checking for recursive definitions.
Dynamic Representations of Sparse Distributed Networks
Authors: Kaplan Haim , Solomon Shay
Published: January 2021

In 1999, Brodal and Fagerberg (BF) gave an algorithm for maintaining a low outdegree orientation of a dynamic uniformly sparse graph. Specifically, for a dynamic graph on
n
-vertices, with arboricity bounded by
ɑ
at all times, the BF algorithm supports edge updates in
O
(log
n
) amortized update time, while keeping the maximum outdegree in the graph bounded by
O
(
ɑ
). Such an orientation provides a basic data structure for uniformly sparse graphs, which found applications to several dynamic graph algorithms, including adjacency queries and labeling schemes, maximal and approximate matching, approximate vertex cover, forest decomposition, and distance oracles.

A significant weakness of the BF algorithm is the possible
temporary
blowup of the maximum outdegree, following edge insertions. Although BF eventually reduces all outdegrees to
O
(
ɑ
), some vertices may reach an outdegree of Ω(
n
) during the process, and hence local memory usage at the vertices, which is an important quality measure in distributed systems, cannot be bounded. We show how to modify the BF algorithm to guarantee that the outdegrees of all vertices are bounded by
O
(
ɑ
) at all times, without hurting any of its other properties and present an efficient distributed implementation of the modified algorithm. This provides the
first
representation of distributed networks in which the local memory usage at all vertices is bounded by the arboricity (which is essentially the average degree of the densest subgraph) rather than the maximum degree.

For settings where there is no strict limitation on the local memory, one may take the temporary outdegree blowup to the extreme and allow a permanent outdegree blowup. This allows us to address the second significant weakness of the BF algorithm—its inherently
global
nature: An insertion of an edge (
u,v
) may trigger changes in the orientations of edges that are arbitrarily far away from
u
and
v
. Such a non-local scheme may be prohibitively expensive in various practical applications. We suggest an alternative
local
scheme, which does not guarantee any outdegree bound on the vertices, yet is just as efficient as the BF scheme for some of the aforementioned applications. For example, we obtain a local dynamic algorithm for maintaining a maximal matching with sub-logarithmic update time in uniformly sparse networks, providing an exponential improvement over the state of the art in this context. We also present a distributed implementation of this scheme and some of its applications.
Measuring the Influence of Web Features in the Online Gamification Environment: A Multimediation Approach
Authors: Naqvi Mishal Hasnain , Guoyan Sun , Naqvi Muhammad Hasnain Abbas
Published: January 2021

Considering the increasing importance of user experience and the influence of gamification techniques in the online business environment. This research explores the antecedents and outcomes of user experience in the context of website features. We proposed a multimediation conceptual framework integrating several constructs to test the user response about online gamification. This study used PLS‐SEM to measure the direct and mediating relationship among hedonic features and utilitarian features user experience, monetary value, experiential value, satisfaction, and behavioral consequences in the online gamification environment. The findings indicate that hedonic features and utilitarian features directly affect user experience, further influencing user satisfaction, intention to use, and recommendation. Moreover, experiential value and monetary value also have a significant effect on user experience and user satisfaction. The study also confirmed the mediating effect of user experience, monetary value, experiential, and user satisfaction. Hence, this study’s results can help web managers provide users’ memorable experiences of using such gamification websites, which in turn increase their satisfaction and arouse expected behavioral intentions.
Convergence Rate Analysis of the Proximal Difference of the Convex Algorithm
Authors: Wang Xueyong , Zhang Ying , Chen Haibin , Kou Xipeng
Published: January 2021

In this paper, we study the convergence rate of the proximal difference of the convex algorithm for the problem with a strong convex function and two convex functions. By making full use of the special structure of the difference of convex decomposition, we prove that the convergence rate of the proximal difference of the convex algorithm is linear, which is measured by the objective function value.