OpenRaiser/Intern-Atlas huggingface dataset:
On Entropy and Bit Patterns of Ring Oscillator Jitter
Venue: arXiv cs.CR 2021
Year: 2021

Thermal jitter (phase noise) from a free-running ring oscillator is a common, easily implementable physical randomness source in True Random Number Generators (TRNGs). We show how to evaluate entropy, autocorrelation, and bit pattern distributions of ring oscillator noise sources, even with low jitter levels or some bias. Entropy justification is required in NIST 800-90B and AIS-31 testing and for applications such as the RISC-V entropy source extension. Our numerical evaluation algorithms outperform Monte Carlo simulations in speed and accuracy. We also propose a new lower bound estimation formula for the entropy of ring oscillator sources which applies more generally than previous ones.
Low-cost attacks on Ethereum 2.0 by sub-1/3 stakeholders
Venue: arXiv cs.CR 2021
Year: 2021

We outline two dishonest strategies that can be cheaply executed on the Ethereum 2.0 beacon chain, even by validators holding less than one-third of the total stake: malicious chain reorganizations ("reorgs") and finality delays. In a malicious reorg, an attacker withholds their blocks and attestations before releasing them at an opportune time in order to force a chain reorganization, which they can take advantage of by double-spending or front-running transactions. To execute a finality delay an attacker uses delayed block releases and withholding of attestations to increase the mean and variance of the time it takes blocks to become finalized. This impacts the efficiency and predictability of the system. We provide a probabilistic and cost analysis for each of these attacks, considering a validator with 30% of the total stake.
Downbeat Tracking with Tempo-Invariant Convolutional Neural Networks
Venue: arXiv cs.SD 2021
Year: 2021

The human ability to track musical downbeats is robust to changes in tempo, and it extends to tempi never previously encountered. We propose a deterministic time-warping operation that enables this skill in a convolutional neural network (CNN) by allowing the network to learn rhythmic patterns independently of tempo. Unlike conventional deep learning approaches, which learn rhythmic patterns at the tempi present in the training dataset, the patterns learned in our model are tempo-invariant, leading to better tempo generalisation and more efficient usage of the network capacity. We test the generalisation property on a synthetic dataset created by rendering the Groove MIDI Dataset using FluidSynth, split into a training set containing the original performances and a test set containing tempo-scaled versions rendered with different SoundFonts (test-time augmentation). The proposed model generalises nearly perfectly to unseen tempi (F-measure of 0.89 on both training and test sets), whereas a comparable conventional CNN achieves similar accuracy only for the training set (0.89) and drops to 0.54 on the test set. The generalisation advantage of the proposed model extends to real music, as shown by results on the GTZAN and Ballroom datasets.
HiCOPS: High Performance Computing Framework for Tera-Scale Database Search of Mass Spectrometry based Omics Data
Venue: arXiv cs.DC 2021
Year: 2021

Database-search algorithms, that deduce peptides from Mass Spectrometry (MS) data, have tried to improve the computational efficiency to accomplish larger, and more complex systems biology studies. Existing serial, and high-performance computing (HPC) search engines, otherwise highly successful, are known to exhibit poor-scalability with increasing size of theoretical search-space needed for increased complexity of modern non-model, multi-species MS-based omics analysis. Consequently, the bottleneck for computational techniques is the communication costs of moving the data between hierarchy of memory, or processing units, and not the arithmetic operations. This post-Moore change in architecture, and demands of modern systems biology experiments have dampened the overall effectiveness of the existing HPC workflows. We present a novel efficient parallel computational method, and its implementation on memory-distributed architectures for peptide identification tool called HiCOPS, that enables more than 100-fold improvement in speed over most existing HPC proteome database search tools. HiCOPS empowers the supercomputing database search concept for comprehensive identification of peptides, and all their modified forms within a reasonable time-frame. We demonstrate this by searching Gigabytes of experimental MS data against Terabytes of databases where HiCOPS completes peptide identification in few minutes using 72 parallel nodes (1728 cores) compared to several weeks required by existing state-of-the-art tools using 1 node (24 cores); 100 minutes vs 5 weeks; 500x speedup. Finally, we formulate a theoretical framework for our overhead-avoiding strategy, and report superior performance evaluation results for key metrics including execution time, CPU utilization, speedups, and I/O efficiency. The software will be made available at: hicops.github.io
Predicting the probability distribution of bus travel time to move towards reliable planning of public transport services
Venue: arXiv cs.LG 2021
Year: 2021

An important aspect of the quality of a public transport service is its reliability, which is defined as the invariability of the service attributes. Preventive measures taken during planning can reduce risks of unreliability throughout operations. In order to tackle reliability during the service planning phase, a key piece of information is the long-term prediction of the density of the travel time, which conveys the uncertainty of travel times. We introduce a reliable approach to one of the problems of service planning in public transport, namely the Multiple Depot Vehicle Scheduling Problem (MDVSP), which takes as input a set of trips and the probability density function (p.d.f.) of the travel time of each trip in order to output delay-tolerant vehicle schedules. This work empirically compares probabilistic models for the prediction of the conditional p.d.f. of the travel time, as a first step towards reliable MDVSP solutions. Two types of probabilistic models, namely similarity-based density estimation models and a smoothed Logistic Regression for probabilistic classification model, are compared on a dataset of more than 41,000 trips and 50 bus routes of the city of Montréal. The result of a vast majority of probabilistic models outperforms that of a Random Forests model, which is not inherently probabilistic, thus highlighting the added value of modeling the conditional p.d.f. of the travel time with probabilistic models. A similarity-based density estimation model using a $k$ Nearest Neighbors method and a Kernel Density Estimation predicted the best estimate of the true conditional p.d.f. on this dataset.
Function Delivery Network: Extending Serverless Computing for Heterogeneous Platforms
Venue: arXiv cs.DC 2021
Year: 2021

Serverless computing has rapidly grown following the launch of Amazon's Lambda platform. Function-as-a-Service (FaaS) a key enabler of serverless computing allows an application to be decomposed into simple, standalone functions that are executed on a FaaS platform. The FaaS platform is responsible for deploying and facilitating resources to the functions. Several of today's cloud applications spread over heterogeneous connected computing resources and are highly dynamic in their structure and resource requirements. However, FaaS platforms are limited to homogeneous clusters and homogeneous functions and do not account for the data access behavior of functions before scheduling. We introduce an extension of FaaS to heterogeneous clusters and to support heterogeneous functions through a network of distributed heterogeneous target platforms called Function Delivery Network (FDN). A target platform is a combination of a cluster of homogeneous nodes and a FaaS platform on top of it. FDN provides Function-Delivery-as-a-Service (FDaaS), delivering the function to the right target platform. We showcase the opportunities such as varied target platform's characteristics, possibility of collaborative execution between multiple target platforms, and localization of data that the FDN offers in fulfilling two objectives: Service Level Objective (SLO) requirements and energy efficiency when scheduling functions by evaluating over five distributed target platforms using the FDNInspector, a tool developed by us for benchmarking distributed target platforms. Scheduling functions on an edge target platform in our evaluation reduced the overall energy consumption by 17x without violating the SLO requirements in comparison to scheduling on a high-end target platform.
The Enigma of Complexity
Venue: arXiv cs.NE 2021
Year: 2021

In this paper we examine the concept of complexity as it applies to generative art and design. Complexity has many different, discipline specific definitions, such as complexity in physical systems (entropy), algorithmic measures of information complexity and the field of "complex systems". We apply a series of different complexity measures to three different generative art datasets and look at the correlations between complexity and individual aesthetic judgement by the artist (in the case of two datasets) or the physically measured complexity of 3D forms. Our results show that the degree of correlation is different for each set and measure, indicating that there is no overall "better" measure. However, specific measures do perform well on individual datasets, indicating that careful choice can increase the value of using such measures. We conclude by discussing the value of direct measures in generative and evolutionary art, reinforcing recent findings from neuroimaging and psychology which suggest human aesthetic judgement is informed by many extrinsic factors beyond the measurable properties of the object being judged.
On the Approximation Power of Two-Layer Networks of Random ReLUs
Venue: arXiv cs.LG 2021
Year: 2021

This paper considers the following question: how well can depth-two ReLU networks with randomly initialized bottom-level weights represent smooth functions? We give near-matching upper- and lower-bounds for $L_2$-approximation in terms of the Lipschitz constant, the desired accuracy, and the dimension of the problem, as well as similar results in terms of Sobolev norms. Our positive results employ tools from harmonic analysis and ridgelet representation theory, while our lower-bounds are based on (robust versions of) dimensionality arguments.
On Multi-Human Multi-Robot Remote Interaction: A Study of Transparency, Inter-Human Communication, and Information Loss in Remote Interaction
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, we investigate how to design an effective interface for remote multi-human multi-robot interaction. While significant research exists on interfaces for individual human operators, little research exists for the multi-human case. Yet, this is a critical problem to solve to make complex, large-scale missions achievable in which direct human involvement is impossible or undesirable, and robot swarms act as a semi-autonomous agents. This paper's contribution is twofold. The first contribution is an exploration of the design space of computer-based interfaces for multi-human multi-robot operations. In particular, we focus on information transparency and on the factors that affect inter-human communication in ideal conditions, i.e., without communication issues. Our second contribution concerns the same problem, but considering increasing degrees of information loss, defined as intermittent reception of data with noticeable gaps between individual receipts. We derived a set of design recommendations based on two user studies involving 48 participants.
Coevolution of theoretical and applied research: a case study of graphene research by temporal and geographic analysis
Venue: arXiv cs.DL 2021
Year: 2021

As a part of science of science (SciSci) research, the evolution of scientific disciplines has been attracting a great deal of attention recently. This kind of discipline level analysis not only give insights of one particular field but also shed light on general principles of scientific enterprise. In this paper we focus on graphene research, a fast growing field covers both theoretical and applied study. Using co-clustering method, we split graphene literature into two groups and confirm that one group is about theoretical research (T) and another corresponds to applied research (A). We analyze the proportion of T/A and found applied research becomes more and more popular after 2007. Geographical analysis demonstrated that countries have different preference in terms of T/A and they reacted differently to research trend. The interaction between two groups has been analyzed and shows that T extremely relies on T and A heavily relies on A, however the situation is very stable for T but changed markedly for A. No geographic difference is found for the interaction dynamics. Our results give a comprehensive picture of graphene research evolution and also provide a general framework which is able to analyze other disciplines.
A review of motion planning algorithms for intelligent robotics
Venue: arXiv cs.RO 2021
Year: 2021

We investigate and analyze principles of typical motion planning algorithms. These include traditional planning algorithms, supervised learning, optimal value reinforcement learning, policy gradient reinforcement learning. Traditional planning algorithms we investigated include graph search algorithms, sampling-based algorithms, and interpolating curve algorithms. Supervised learning algorithms include MSVM, LSTM, MCTS and CNN. Optimal value reinforcement learning algorithms include Q learning, DQN, double DQN, dueling DQN. Policy gradient algorithms include policy gradient method, actor-critic algorithm, A3C, A2C, DPG, DDPG, TRPO and PPO. New general criteria are also introduced to evaluate performance and application of motion planning algorithms by analytical comparisons. Convergence speed and stability of optimal value and policy gradient algorithms are specially analyzed. Future directions are presented analytically according to principles and analytical comparisons of motion planning algorithms. This paper provides researchers with a clear and comprehensive understanding about advantages, disadvantages, relationships, and future of motion planning algorithms in robotics, and paves ways for better motion planning algorithms.
Privacy Preserving and Resilient RPKI
Venue: arXiv cs.CR 2021
Year: 2021

Resource Public Key Infrastructure (RPKI) is vital to the security of inter-domain routing. However, RPKI enables Regional Internet Registries (RIRs) to unilaterally takedown IP prefixes - indeed, such attacks have been launched by nation-state adversaries. The threat of IP prefix takedowns is one of the factors hindering RPKI adoption. In this work, we propose the first distributed RPKI system, based on threshold signatures, that requires the coordination of a number of RIRs to make changes to RPKI objects; hence, preventing unilateral prefix takedown. We perform extensive evaluations using our implementation demonstrating the practicality of our solution. Furthermore, we show that our system is scalable and remains efficient even when RPKI is widely deployed.
FedAUX: Leveraging Unlabeled Auxiliary Data in Federated Learning
Venue: arXiv cs.LG 2021
Year: 2021

Federated Distillation (FD) is a popular novel algorithmic paradigm for Federated Learning, which achieves training performance competitive to prior parameter averaging based methods, while additionally allowing the clients to train different model architectures, by distilling the client predictions on an unlabeled auxiliary set of data into a student model. In this work we propose FedAUX, an extension to FD, which, under the same set of assumptions, drastically improves performance by deriving maximum utility from the unlabeled auxiliary data. FedAUX modifies the FD training procedure in two ways: First, unsupervised pre-training on the auxiliary data is performed to find a model initialization for the distributed training. Second, $(\varepsilon, δ)$-differentially private certainty scoring is used to weight the ensemble predictions on the auxiliary data according to the certainty of each client model. Experiments on large-scale convolutional neural networks and transformer models demonstrate, that the training performance of FedAUX exceeds SOTA FL baseline methods by a substantial margin in both the iid and non-iid regime, further closing the gap to centralized training performance. Code is available at github.com/fedl-repo/fedaux.
On Fading Channel Dependency Structures with a Positive Zero-Outage Capacity
Venue: arXiv cs.IT 2021
Year: 2021

With emerging wireless technologies like 6G, many new applications like autonomous systems evolve which have strict demands on the reliability and latency of data communications. In the scenario of the commonly investigated independent slow fading links, the zero-outage capacity (ZOC) is zero and retransmissions are therefore inevitable. In this work, we show that a positive ZOC can be achieved under the same setting of slow fading with constant transmit power and without perfect channel state information at the transmitter, if the joint distribution of the channel gains follows certain structures. This allows reliable reception without any outages, thus not requiring retransmissions. Based on a systematic copula approach, we show that there exists a set of dependency structures for which positive ZOCs can be achieved for both maximum ratio combining (MRC) and selection combining (SC). We characterize the maximum ZOC within a finite number of bits. The results are evaluated explicitly for the special cases of Rayleigh fading and Nakagami-$m$ fading in order to quantify the ZOCs for common fading models.
Evolutionary Multitask Optimization: a Methodological Overview, Challenges and Future Research Directions
Venue: arXiv cs.NE 2021
Year: 2021

In this work we consider multitasking in the context of solving multiple optimization problems simultaneously by conducting a single search process. The principal goal when dealing with this scenario is to dynamically exploit the existing complementarities among the problems (tasks) being optimized, helping each other through the exchange of valuable knowledge. Additionally, the emerging paradigm of Evolutionary Multitasking tackles multitask optimization scenarios by using as inspiration concepts drawn from Evolutionary Computation. The main purpose of this survey is to collect, organize and critically examine the abundant literature published so far in Evolutionary Multitasking, with an emphasis on the methodological patterns followed when designing new algorithmic proposals in this area (namely, multifactorial optimization and multipopulation-based multitasking). We complement our critical analysis with an identification of challenges that remain open to date, along with promising research directions that can stimulate future efforts in this topic. Our discussions held throughout this manuscript are offered to the audience as a reference of the general trajectory followed by the community working in this field in recent times, as well as a self-contained entry point for newcomers and researchers interested to join this exciting research avenue.
Multimodal-Aware Weakly Supervised Metric Learning with Self-weighting Triplet Loss
Venue: arXiv cs.LG 2021
Year: 2021

In recent years, we have witnessed a surge of interests in learning a suitable distance metric from weakly supervised data. Most existing methods aim to pull all the similar samples closer while push the dissimilar ones as far as possible. However, when some classes of the dataset exhibit multimodal distribution, these goals conflict and thus can hardly be concurrently satisfied. Additionally, to ensure a valid metric, many methods require a repeated eigenvalue decomposition process, which is expensive and numerically unstable. Therefore, how to learn an appropriate distance metric from weakly supervised data remains an open but challenging problem. To address this issue, in this paper, we propose a novel weakly supervised metric learning algorithm, named MultimoDal Aware weakly supervised Metric Learning (MDaML). MDaML partitions the data space into several clusters and allocates the local cluster centers and weight for each sample. Then, combining it with the weighted triplet loss can further enhance the local separability, which encourages the local dissimilar samples to keep a large distance from the local similar samples. Meanwhile, MDaML casts the metric learning problem into an unconstrained optimization on the SPD manifold, which can be efficiently solved by Riemannian Conjugate Gradient Descent (RCGD). Extensive experiments conducted on 13 datasets validate the superiority of the proposed MDaML.
Continuous Random Variable Estimation is not Optimal for the Witsenhausen Counterexample
Venue: arXiv cs.IT 2021
Year: 2021

Optimal design of distributed decision policies can be a difficult task, illustrated by the famous Witsenhausen counterexample. In this paper we characterize the optimal control designs for the vector-valued setting assuming that it results in an internal state that can be described by a continuous random variable which has a probability density function. More specifically, we provide a genie-aided outer bound that relies on our previous results for empirical coordination problems. This solution turns out to be not optimal in general, since it consists of a time-sharing strategy between two linear schemes of specific power. It follows that the optimal decision strategy for the original scalar Witsenhausen problem must lead to an internal state that cannot be described by a continuous random variable which has a probability density function.
Computational identification of significant actors in paintings through symbols and attributes
Venue: arXiv cs.CV 2021
Year: 2021

The automatic analysis of fine art paintings presents a number of novel technical challenges to artificial intelligence, computer vision, machine learning, and knowledge representation quite distinct from those arising in the analysis of traditional photographs. The most important difference is that many realist paintings depict stories or episodes in order to convey a lesson, moral, or meaning. One early step in automatic interpretation and extraction of meaning in artworks is the identifications of figures (actors). In Christian art, specifically, one must identify the actors in order to identify the Biblical episode or story depicted, an important step in understanding the artwork. We designed an automatic system based on deep convolutional neural networks and simple knowledge database to identify saints throughout six centuries of Christian art based in large part upon saints symbols or attributes. Our work represents initial steps in the broad task of automatic semantic interpretation of messages and meaning in fine art.