OpenRaiser/Intern-Atlas huggingface dataset:
The Fast Heuristic Algorithms and Post-Processing Techniques to Design Large and Low-Cost Communication Networks
Venue: arXiv cs.NI 2019
Year: 2019

It is challenging to design large and low-cost communication networks. In this paper, we formulate this challenge as the prize-collecting Steiner Tree Problem (PCSTP). The objective is to minimize the costs of transmission routes and the disconnected monetary or informational profits. Initially, we note that the PCSTP is MAX SNP-hard. Then, we propose some post-processing techniques to improve suboptimal solutions to PCSTP. Based on these techniques, we propose two fast heuristic algorithms: the first one is a quasilinear time heuristic algorithm that is faster and consumes less memory than other algorithms; and the second one is an improvement of a stateof-the-art polynomial time heuristic algorithm that can find high-quality solutions at a speed that is only inferior to the first one. We demonstrate the competitiveness of our heuristic algorithms by comparing them with the state-of-the-art ones on the largest existing benchmark instances (169 800 vertices and 338 551 edges). Moreover, we generate new instances that are even larger (1 000 000 vertices and 10 000 000 edges) to further demonstrate their advantages in large networks. The state-ofthe-art algorithms are too slow to find high-quality solutions for instances of this size, whereas our new heuristic algorithms can do this in around 6 to 45s on a personal computer. Ultimately, we apply our post-processing techniques to update the bestknown solution for a notoriously difficult benchmark instance to show that they can improve near-optimal solutions to PCSTP. In conclusion, we demonstrate the usefulness of our heuristic algorithms and post-processing techniques for designing large and low-cost communication networks.
Multi-Channel Access Solutions for 5G New Radio
Venue: arXiv cs.NI 2019
Year: 2019

5G New Radio paves the way for introducing novel multi-service radio resource management solutions tailored for enhanced Mobile Broadband and Ultra-Reliable Low Latency Communication service classes. Multi-Channel Access is a family of such multi-service solutions that enable a user equipment to aggregate radio resources from multiple sources. The objective is multi-fold; throughput enhancement through access to a larger bandwidth, reliability improvement by increasing the diversity order and/or coordinated transmission/reception, as well as flexibility and load balancing improvement by decoupling the downlink and the uplink access points. This paper presents several multi-channel access solutions for 5G New Radio multi-service scenarios. In particular, throughput enhancement and latency reduction concepts like multi-connectivity, carrier aggregation, downlink-uplink decoupled access and coordinated multi-point connectivity are discussed. Moreover, novel design solutions exploiting these concepts are proposed. Numerical evaluation of the introduced solutions indicates significant performance gains over state-of-the-art schemes; for example, our proposed component carrier selection mechanism leads to a median throughput gain of up to 100% by means of an implicit load balance. Therefore, the proposed Multi-Channel Access solutions have the potential to be key multi-service enablers for 5G New Radio.
Meta-Amortized Variational Inference and Learning
Venue: arXiv cs.LG 2019
Year: 2019

Despite the recent success in probabilistic modeling and their applications, generative models trained using traditional inference techniques struggle to adapt to new distributions, even when the target distribution may be closely related to the ones seen during training. In this work, we present a doubly-amortized variational inference procedure as a way to address this challenge. By sharing computation across not only a set of query inputs, but also a set of different, related probabilistic models, we learn transferable latent representations that generalize across several related distributions. In particular, given a set of distributions over images, we find the learned representations to transfer to different data transformations. We empirically demonstrate the effectiveness of our method by introducing the MetaVAE, and show that it significantly outperforms baselines on downstream image classification tasks on MNIST (10-50%) and NORB (10-35%).
Integrating Amdahl-like Laws and Divisible Load Theory
Venue: arXiv cs.DC 2019
Year: 2019

Integrating Amdahl's and Amdahl-like laws with Divisible Load Theory promises mathematical design methodology that will make possible the efficient design of tomorrow's systems.
On the Hardness and Inapproximability of Recognizing Wheeler Graphs
Venue: arXiv cs.CC 2019
Year: 2019

In recent years several compressed indexes based on variants of the Burrows-Wheeler transformation have been introduced. Some of these index structures far more complex than a single string, as was originally done with the FM-index [Ferragina and Manzini, J. ACM 2005]. As such, there has been an effort to better understand under which conditions such an indexing scheme is possible. This led to the introduction of Wheeler graphs [Gagie it et al., Theor. Comput. Sci., 2017]. A Wheeler graph is a directed graph with edge labels which satisfies two simple axioms. Wheeler graphs can be indexed in a way which is space efficient and allows for fast traversal. Gagie et al. showed that de Bruijn graphs, generalized compressed suffix arrays, and several other BWT related structures can be represented as Wheeler graphs. Here we answer the open question of whether or not there exists an efficient algorithm for recognizing if a graph is a Wheeler graph. We demonstrate:(i) Recognizing if a graph is a Wheeler graph is NP-complete for any edge label alphabet of size $σ\geq 2$, even for DAGs. It can be solved in linear time for $σ=1$; (ii) An optimization variant called Wheeler Graph Violation (WGV) which aims to remove the minimum number of edges needed to obtain a Wheeler graph is APX-hard, even for DAGs. Hence, unless P = NP, there exists constant $C > 1$ such that there is no $C$-approximation algorithm. We show conditioned on the Unique Games Conjecture, for every constant $C \geq 1$, it is NP-hard to find a $C$-approximation to WGV; (iii) The Wheeler Subgraph problem (WS) which aims to find the largest Wheeler subgraph is in APX for $σ=O(1)$; (iv) For the above problems there exist efficient exponential time exact algorithms, relying on graph isomorphism being computed in strictly sub-exponential time; (v) A class of graphs where the recognition problem is polynomial time solvable.
Polyphonic Music Composition with LSTM Neural Networks and Reinforcement Learning
Venue: arXiv cs.SD 2019
Year: 2019

In the domain of algorithmic music composition, machine learning-driven systems eliminate the need for carefully hand-crafting rules for composition. In particular, the capability of recurrent neural networks to learn complex temporal patterns lends itself well to the musical domain. Promising results have been observed across a number of recent attempts at music composition using deep RNNs. These approaches generally aim at first training neural networks to reproduce subsequences drawn from existing songs. Subsequently, they are used to compose music either at the audio sample-level or at the note-level. We designed a representation that divides polyphonic music into a small number of monophonic streams. This representation greatly reduces the complexity of the problem and eliminates an exponential number of probably poor compositions. On top of our LSTM neural network that learnt musical sequences in this representation, we built an RL agent that learnt to find combinations of songs whose joint dominance produced pleasant compositions. We present Amadeus, an algorithmic music composition system that composes music that consists of intricate melodies, basic chords, and even occasional contrapuntal sequences.
On Quasi Ordinal Diagram Systems
Venue: arXiv cs.LO 2019
Year: 2019

The purposes of this note are the following two; we first generalize Okada-Takeuti's well quasi ordinal diagram theory, utilizing the recent result of Dershowitz-Tzameret's version of tree embedding theorem with gap conditions. Second, we discuss possible use of such strong ordinal notation systems for the purpose of a typical traditional termination proof method for term rewriting systems, especially for second-order (pattern-matching-based) rewriting systems including a rewrite-theoretic version of Buchholz's hydra game.
Finding the Transitive Closure of Functional Dependencies using Strategic Port Graph Rewriting
Venue: arXiv cs.DB 2019
Year: 2019

We present a new approach to the logical design of relational databases, based on strategic port graph rewriting. We show how to model relational schemata as attributed port graphs and provide port graph rewriting rules to perform computations on functional dependencies. Using these rules we present a strategic graph program to find the transitive closure of a set of functional dependencies. This program is sound, complete and terminating, assuming that there are no cyclical dependencies in the schema.
Motion Planning on an Asteroid Surface with Irregular Gravity Fields
Venue: arXiv cs.RO 2019
Year: 2019

There are thousands of asteroids in near-Earth space and millions in the Main Belt. They are diverse in physical properties and composition and are time capsules of the early solar system. This makes them strategic locations for planetary science, resource mining, planetary defense/security and as inter-planetary depots and communication relays. However, asteroids are a chal-lenging target for surface exploration due it its low but highly nonlinear gravity field. In such conditions, mobility through ballistic hopping possess multiple advantages over conventional mobility solutions and as such hop-ping robots have emerged as a promising platform for future exploration of asteroids and comets. They can traverse large distances over rough terrain with the expenditure of minimum energy. In this paper we present ballistic hopping dynamics and its motion planning on an asteroid surface with highly nonlinear gravity fields. We do it by solving Lambert's orbital boundary val-ue problem in irregular gravity fields by a shooting method to find the initial velocity required to intercept a target. We then present methods to localize the hopping robot using pose estimation by successive scan matching with a 3D laser scanner. Using the above results, we provide methods for motion planning on the asteroid surface over long distances. The robot will require to perform multiple hops to reach a desired goal from its initial position while avoiding obstacles. The study is then be extended to find optimal tra-jectories to reach a desired goal by visiting multiple waypoints.
Fast Strassen-based $A^t A$ Parallel Multiplication
Venue: arXiv cs.DC 2019
Year: 2019

Matrix multiplication $A^t A$ appears as intermediate operation during the solution of a wide set of problems. In this paper, we propose a new cache-oblivious algorithm for the $A^t A$ multiplication. Our algorithm, A$\scriptstyle \mathsf{T}$A, calls classical Strassen's algorithm as sub-routine, decreasing the computational cost %(expressed in number of performed products) of the conventional $A^t A$ multiplication to $\frac{2}{7}n^{\log_2 7}$. It works for generic rectangular matrices and exploits the peculiar symmetry of the resulting product matrix for sparing memory. We used the MPI paradigm to implement A$\scriptstyle \mathsf{T}$A in parallel, and we tested its performances on a small subset of nodes of the Galileo cluster. Experiments highlight good scalability and speed-up, also thanks to minimal number of exchanged messages in the designed communication system. Parallel overhead and inherently sequential time fraction are negligible in the tested configurations.
Balancing-Aware Charging Strategy For Series-Connected Lithium-Ion Cells: A Nonlinear Model Predictive Control Approach
Venue: arXiv cs.SY 2019
Year: 2019

Charge unbalance is one of the key issues for series-connected Lithium-ion cells. Within this context, model-based optimization strategies have proven to be the most effective. In the present paper, an ad-hoc electrochemical model, tailored to control purposes, is firstly presented. Relying on this latter, a general nonlinear MPC for balancing-aware optimal charging is then proposed. In view of the possibility of a practical implementation, the concepts are subsequently specialized for an easily implementable power supply scheme. Finally, the nonlinear MPC approach is validated on commercial cells using a detailed battery simulator, with sound evidence of its effectiveness.
Progressive Generative Adversarial Networks for Medical Image Super resolution
Venue: arXiv cs.CV 2019
Year: 2019

Anatomical landmark segmentation and pathology localization are important steps in automated analysis of medical images. They are particularly challenging when the anatomy or pathology is small, as in retinal images and cardiac MRI, or when the image is of low quality due to device acquisition parameters as in magnetic resonance (MR) scanners. We propose an image super-resolution method using progressive generative adversarial networks (P-GAN) that can take as input a low-resolution image and generate a high resolution image of desired scaling factor. The super resolved images can be used for more accurate detection of landmarks and pathology. Our primary contribution is in proposing a multistage model where the output image quality of one stage is progressively improved in the next stage by using a triplet loss function. The triplet loss enables stepwise image quality improvement by using the output of the previous stage as the baseline. This facilitates generation of super resolved images of high scaling factor while maintaining good image quality. Experimental results for image super-resolution show that our proposed multistage P-GAN outperforms competing methods and baseline GAN.
Etude de la Distribution de Calculs Creux sur une Grappe Multi-coeurs
Venue: arXiv cs.DC 2019
Year: 2019

Nowadays, high performance computing is becoming more and more important in different fields research and industry, such as medical imaging and diagnostics, mathematics as well as oil exploration. It refers to intensive computing in some applications where one needs to use a large number of computing resources (computing power, memory rate, storage space, etc.). Thus, it is necessary in this case to run these applications on architectures parallel making multiple computers work together and running over 10 operations at floating point per second (or a petaflops). 15 Parallel computation consists of executing one or more programs, simultaneously, by multiple processors. In general, we have two ways to perform a parallel calculation. The first is to cut the program into several calculation tasks then, run all these parallel spots by different processors. The second requires partitioning the data, so that each part of the data is assigned to a different processor. Then, all the processors run the instructions of the same program in parallel but by operating on different data . This last method, called parallelism of data, is that retained in this memory. Digital analysis is one of the areas where the use of platforms is essential parallel, in particular, in the case where numerical methods treat hollow matrices. This last method, called parallelism of data, is that retained in this memory. Digital analysis is one of the areas where the use of platforms is essential parallel, in particular, in the case where numerical methods treat hollow matrices. A hollow matrix is a very large matrix that contains a small proportion non-zero elements. These matrices can come from different domains such as simulation structural mechanics, image / signal processing, the study of the dynamics of fluids etc.
Adaptive Artificial Intelligent Q&A Platform
Venue: arXiv cs.CL 2019
Year: 2019

The paper presents an approach to build a question and answer system that is capable of processing the information in a large dataset and allows the user to gain knowledge from this dataset by asking questions in natural language form. Key content of this research covers four dimensions which are; Corpus Preprocessing, Question Preprocessing, Deep Neural Network for Answer Extraction and Answer Generation. The system is capable of understanding the question, responds to the user's query in natural language form as well. The goal is to make the user feel as if they were interacting with a person than a machine.
The Dagstuhl Beginners Guide to Reproducibility for Experimental Networking Research
Venue: arXiv cs.NI 2019
Year: 2019

Reproducibility is one of the key characteristics of good science, but hard to achieve for experimental disciplines like Internet measurements and networked systems. This guide provides advice to researchers, particularly those new to the field, on designing experiments so that their work is more likely to be reproducible and to serve as a foundation for follow-on work by others.
SDN On BLE: Controlling Resource Constrained Mesh Networks
Venue: arXiv cs.NI 2019
Year: 2019

Wireless connectivity for the Internet of Things (IoT) requires combining low latency and high reliability with power and cost constraints. On top of that, diverse applications and end-to-end services with very different performance requirements should ideally share the same network infrastructure. Software defined networks (SDN) were defined to allow this coexistence, but they have seen very limited adoption in IoT systems due to the inherent resource constrained nature of the wireless devices. Additionally, the low-power nature of IoT communication standards does not usually allow for physically separated control and data channels, which is a basic requirement for real-time network slicing. In this work, we propose a SDN implementation for Bluetooth Low Energy (BLE), which has become the de-facto technology for IoT applications. The proposed BLE mesh structure is able to use different protocols for different services, ensuring a clear separation between control and data channels while still being sent over the wireless medium. A proof-of-concept for the proposed SDN implementation is given in a real BLE mesh testbed, where measurements show how the system is able to automatically detect and recover from network congestion by identifying the nodes responsible of such situation and reconfiguring their parameters over the air.
Decentralized Flood Forecasting Using Deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Predicting flood for any location at times of extreme storms is a longstanding problem that has utmost importance in emergency management. Conventional methods that aim to predict water levels in streams use advanced hydrological models still lack of giving accurate forecasts everywhere. This study aims to explore artificial deep neural networks' performance on flood prediction. While providing models that can be used in forecasting stream stage, this paper presents a dataset that focuses on the connectivity of data points on river networks. It also shows that neural networks can be very helpful in time-series forecasting as in flood events, and support improving existing models through data assimilation.
Semi-Supervised Learning by Label Gradient Alignment
Venue: arXiv cs.LG 2019
Year: 2019

We present label gradient alignment, a novel algorithm for semi-supervised learning which imputes labels for the unlabeled data and trains on the imputed labels. We define a semantically meaningful distance metric on the input space by mapping a point (x, y) to the gradient of the model at (x, y). We then formulate an optimization problem whose objective is to minimize the distance between the labeled and the unlabeled data in this space, and we solve it by gradient descent on the imputed labels. We evaluate label gradient alignment using the standardized architecture introduced by Oliver et al. (2018) and demonstrate state-of-the-art accuracy in semi-supervised CIFAR-10 classification.
$\mathsf{QMA}$ Lower Bounds for Approximate Counting
Venue: arXiv cs.CC 2019
Year: 2019

We prove a query complexity lower bound for $\mathsf{QMA}$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $\mathsf{SBP}^A \not\subset \mathsf{QMA}^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to derive a lower bound for the $\mathsf{SBQP}$ query complexity of the $\mathsf{AND}$ of two approximate counting instances. We use Laurent polynomials as a tool in our proof, showing that the "Laurent polynomial method" can be useful even for problems involving ordinary polynomials.
Principal Model Analysis Based on Partial Least Squares
Venue: arXiv cs.LG 2019
Year: 2019

Motivated by the Bagging Partial Least Squares (PLS) and Principal Component Analysis (PCA) algorithms, we propose a Principal Model Analysis (PMA) method in this paper. In the proposed PMA algorithm, the PCA and the PLS are combined. In the method, multiple PLS models are trained on sub-training sets, derived from the original training set based on the random sampling with replacement method. The regression coefficients of all the sub-PLS models are fused in a joint regression coefficient matrix. The final projection direction is then estimated by performing the PCA on the joint regression coefficient matrix. The proposed PMA method is compared with other traditional dimension reduction methods, such as PLS, Bagging PLS, Linear discriminant analysis (LDA) and PLS-LDA. Experimental results on six public datasets show that our proposed method can achieve better classification performance and is usually more stable.
On Mean Estimation for General Norms with Statistical Queries
Venue: arXiv cs.DS 2019
Year: 2019

We study the problem of mean estimation for high-dimensional distributions, assuming access to a statistical query oracle for the distribution. For a normed space $X = (\mathbb{R}^d, \|\cdot\|_X)$ and a distribution supported on vectors $x \in \mathbb{R}^d$ with $\|x\|_{X} \leq 1$, the task is to output an estimate $\hatμ \in \mathbb{R}^d$ which is $ε$-close in the distance induced by $\|\cdot\|_X$ to the true mean of the distribution. We obtain sharp upper and lower bounds for the statistical query complexity of this problem when the the underlying norm is symmetric as well as for Schatten-$p$ norms, answering two questions raised by Feldman, Guzmán, and Vempala (SODA 2017).
Prospective Hybrid Consensus for Project PAI
Venue: arXiv cs.DC 2019
Year: 2019

PAI Coin's Proof-of-Work (PoW) consensus mechanism utilizes the double SHA-256 hashing protocol-- the same mechanism used by Bitcoin Core. This compatibility with classic Bitcoin-style mining provides low barrier to entry for PAI Coin mining, consequently rendering the PAI Coin network vulnerable to so-called 51% attacks, among others. To mitigate such risks, this paper proposes a hybrid Proof-of-Work, Proof-of-Stake (PoS) consensus mechanism and provides a detailed technical analysis of how such a mechanism would counter some of the PAI Coin network's inherent vulnerabilities, if successfully implemented. A detailed technical outline of blockchain-based PoW & PoS consensus, including their advantages and disadvantages, when used both independently and in the context of the hybrid model, is provided. An economic analysis of attacking a hybrid-powered PAI Coin network is presented, and a final recommendation for future development of PAI Coin consensus is made.