OpenRaiser/Intern-Atlas huggingface dataset:
Review of theory and implementation of hyper-dual numbers for first and second order automatic differentiation
Venue: arXiv cs.MS 2018
Year: 2018

In this review we present hyper-dual numbers as a tool for the automatic differentiation of computer programs via operator overloading. We start with a motivational introduction into the ideas of algorithmic differentiation. Then we illuminate the concepts behind operator overloading and dual numbers. Afterwards, we present hyper-dual numbers (and vectors) as an extension of dual numbers for the computation of the Jacobian and the Hessian matrices of a computer program. We review a mathematical theorem that proves the correctness of the derivative information that is obtained from hyper-dual numbers. Finally, we refer to a freely available implementation of a hyper-dual number class in Matlab. We explain an interface that can be called with a function as argument such that the Jacobian and Hessian of this function are returned.
Parity-Check Polar Coding for 5G and Beyond
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we propose a comprehensive Polar coding solution that integrates reliability calculation, rate matching and parity-check coding. Judging a channel coding design from the industry's viewpoint, there are two primary concerns: (i) low-complexity implementation in application-specific integrated circuit (ASIC), and (ii) superior \& stable performance under a wide range of code lengths and rates. The former provides cost- \& power-efficiency which are vital to any commercial system; the latter ensures flexible and robust services. Our design respects both criteria. It demonstrates better performance than existing schemes in literature, but requires only a fraction of implementation cost. With easily-reproducible code construction for arbitrary code rates and lengths, we are able to report "1-bit" fine-granularity simulation results for thousands of cases. The released results can serve as a baseline for future optimization of Polar codes.
Restless Bandits with Constrained Arms: Applications in Social and Information Networks
Venue: arXiv cs.SY 2018
Year: 2018

We study a problem of information gathering in a social network with dynamically available sources and time varying quality of information. We formulate this problem as a restless multi-armed bandit (RMAB). In this problem, information quality of a source corresponds to the state of an arm in RMAB. The decision making agent does not know the quality of information from sources a priori. But the agent maintains a belief about the quality of information from each source. This is a problem of RMAB with partially observable states. The objective of the agent is to gather relevant information efficiently from sources by contacting them. We formulate this as a infinite horizon discounted reward problem, where reward depends on quality of information. We study Whittle's index policy which determines the sequence of play of arms that maximizes long term cumulative reward. We illustrate the performance of index policy, myopic policy and compare with uniform random policy through numerical simulation.
Multidimensional Range Queries on Modern Hardware
Venue: arXiv cs.DB 2018
Year: 2018

Range queries over multidimensional data are an important part of database workloads in many applications. Their execution may be accelerated by using multidimensional index structures (MDIS), such as kd-trees or R-trees. As for most index structures, the usefulness of this approach depends on the selectivity of the queries, and common wisdom told that a simple scan beats MDIS for queries accessing more than 15%-20% of a dataset. However, this wisdom is largely based on evaluations that are almost two decades old, performed on data being held on disks, applying IO-optimized data structures, and using single-core systems. The question is whether this rule of thumb still holds when multidimensional range queries (MDRQ) are performed on modern architectures with large main memories holding all data, multi-core CPUs and data-parallel instruction sets. In this paper, we study the question whether and how much modern hardware influences the performance ratio between index structures and scans for MDRQ. To this end, we conservatively adapted three popular MDIS, namely the R*-tree, the kd-tree, and the VA-file, to exploit features of modern servers and compared their performance to different flavors of parallel scans using multiple (synthetic and real-world) analytical workloads over multiple (synthetic and real-world) datasets of varying size, dimensionality, and skew. We find that all approaches benefit considerably from using main memory and parallelization, yet to varying degrees. Our evaluation indicates that, on current machines, scanning should be favored over parallel versions of classical MDIS even for very selective queries.
Quantum Encryption and Generalized Quantum Shannon Impossibility
Venue: arXiv cs.IT 2018
Year: 2018

The famous Shannon impossibility result says that any encryption scheme with perfect secrecy requires a secret key at least as long as the message. In this paper we provide its quantum analogue with imperfect secrecy and imperfect correctness. We also give a systematic study of information-theoretically secure quantum encryption with two secrecy definitions. We show that the weaker one implies the stronger but with a security loss in $d$, where $d$ is the dimension of the encrypted quantum system. This is good enough if the target secrecy error is of $o(d^{-1})$.
Computing and Communications for the Software-Defined Metamaterial Paradigm: A Context Analysis
Venue: arXiv cs.ET 2018
Year: 2018

Metamaterials are artificial structures which have recently enabled the realization of novel electromagnetic components with engineered and even unnatural functionalities. Existing metamaterials are specifically designed for a single application working under preset conditions (e.g. electromagnetic cloaking for a fixed angle of incidence) and cannot be reused. Software-Defined Metamaterials (SDMs) are a much sought-after paradigm shift, exhibiting electromagnetic properties that can be reconfigured at runtime using a set of software primitives. To enable this new technology, SDMs require the integration of a network of controllers within the structure of the metamaterial, where each controller interacts locally and communicates globally to obtain the programmed behavior. The design approach for such controllers and the interconnection network, however, remains unclear due to the unique combination of constraints and requirements of the scenario. To bridge this gap, this paper aims to provide a context analysis from the computation and communication perspectives. Then, analogies are drawn between the SDM scenario and other applications both at the micro and nano scales, identifying possible candidates for the implementation of the controllers and the intra-SDM network. Finally, the main challenges of SDMs related to computing and communications are outlined.
How to Split UL/DL Antennas in Full-Duplex Cellular Networks
Venue: arXiv cs.IT 2018
Year: 2018

To further improve the potential of full-duplex communications, networks may employ multiple antennas at the base station or user equipment. To this end, networks that employ current radios usually deal with self-interference and multi-user interference by beamforming techniques. Although previous works investigated beamforming design to improve spectral efficiency, the fundamental question of how to split the antennas at a base station between uplink and downlink in full-duplex networks has not been investigated rigorously. This paper addresses this question by posing antenna splitting as a binary nonlinear optimization problem to minimize the sum mean squared error of the received data symbols. It is shown that this is an NP-hard problem. This combinatorial problem is dealt with by equivalent formulations, iterative convex approximations, and a binary relaxation. The proposed algorithm is guaranteed to converge to a stationary solution of the relaxed problem with much smaller complexity than exhaustive search. Numerical results indicate that the proposed solution is close to the optimal in both high and low self-interference capable scenarios, while the usually assumed antenna splitting is far from optimal. For large number of antennas, a simple antenna splitting is close to the proposed solution. This reveals that the importance of antenna splitting is inversely proportional with the number of antennas.
Soft Locality Preserving Map (SLPM) for Facial Expression Recognition
Venue: arXiv cs.CV 2018
Year: 2018

For image recognition, an extensive number of methods have been proposed to overcome the high-dimensionality problem of feature vectors being used. These methods vary from unsupervised to supervised, and from statistics to graph-theory based. In this paper, the most popular and the state-of-the-art methods for dimensionality reduction are firstly reviewed, and then a new and more efficient manifold-learning method, named Soft Locality Preserving Map (SLPM), is presented. Furthermore, feature generation and sample selection are proposed to achieve better manifold learning. SLPM is a graph-based subspace-learning method, with the use of k-neighbourhood information and the class information. The key feature of SLPM is that it aims to control the level of spread of the different classes, because the spread of the classes in the underlying manifold is closely connected to the generalizability of the learned subspace. Our proposed manifold-learning method can be applied to various pattern recognition applications, and we evaluate its performances on facial expression recognition. Experiments on databases, such as the Bahcesehir University Multilingual Affective Face Database (BAUM-2), the Extended Cohn-Kanade (CK+) Database, the Japanese Female Facial Expression (JAFFE) Database, and the Taiwanese Facial Expression Image Database (TFEID), show that SLPM can effectively reduce the dimensionality of the feature vectors and enhance the discriminative power of the extracted features for expression recognition. Furthermore, the proposed feature-generation method can improve the generalizability of the underlying manifolds for facial expression recognition.
Experiments in Verification of Linear Model Predictive Control: Automatic Generation and Formal Verification of an Interior Point Method Algorithm
Venue: arXiv cs.LO 2018
Year: 2018

Classical control of cyber-physical systems used to rely on basic linear controllers. These controllers provided a safe and robust behavior but lack the ability to perform more complex controls such as aggressive maneuvering or performing fuel-efficient controls. Another approach called optimal control is capable of computing such difficult trajectories but lacks the ability to adapt to dynamic changes in the environment. In both cases, the control was designed offline, relying on more or less complex algorithms to find the appropriate parameters. More recent kinds of approaches such as Linear Model-Predictive Control (MPC) rely on the online use of convex optimization to compute the best control at each sample time. In these settings, optimization algorithms are specialized for the specific control problem and embed on the device. This paper proposes to revisit the code generation of an interior point method (IPM)algorithm, an efficient family of convex optimization, focusing on the proof of its implementation at code level. Our approach relies on the code specialization phase to produce additional annotations formalizing the intented specification of the algorithm. Deductive methods are then used to prove automatically the validity of these assertions. Since the algorithm is complex, additional lemmas are also produced, allowing the complete proofto be checked by SMT solvers only. This work is the first to address the effective formal proof of an IPM algorithm. Theapproach could also be generalized more systematically to code generation frameworks, producing proof certificate along the code, for numerical intensive software.
HoPP: Robust and Resilient Publish-Subscribe for an Information-Centric Internet of Things
Venue: arXiv cs.NI 2018
Year: 2018

This paper revisits NDN deployment in the IoT with a special focus on the interaction of sensors and actuators. Such scenarios require high responsiveness and limited control state at the constrained nodes. We argue that the NDN request-response pattern which prevents data push is vital for IoT networks. We contribute HoP-and-Pull (HoPP), a robust publish-subscribe scheme for typical IoT scenarios that targets IoT networks consisting of hundreds of resource constrained devices at intermittent connectivity. Our approach limits the FIB tables to a minimum and naturally supports mobility, temporary network partitioning, data aggregation and near real-time reactivity. We experimentally evaluate the protocol in a real-world deployment using the IoT-Lab testbed with varying numbers of constrained devices, each wirelessly interconnected via IEEE 802.15.4 LowPANs. Implementations are built on CCN-lite with RIOT and support experiments using various single- and multi-hop scenarios.
Timely Status Update in Massive IoT Systems: Decentralized Scheduling for Wireless Uplinks
Venue: arXiv cs.IT 2018
Year: 2018

In a typical Internet of Things (IoT) application where a central controller collects status updates from multiple terminals, e.g., sensors and monitors, through a wireless multiaccess uplink, an important problem is how to attain timely status updates autonomously. In this paper, the timeliness of the status is measured by the recently proposed age-of-information (AoI) metric; both the theoretical and practical aspects of the problem are investigated: we aim to obtain a scheduling policy with minimum AoI and, meanwhile, still suitable for decentralized implementation on account of signalling exchange overhead. Towards this end, we first consider the set of arrival-independent and renewal (AIR) policies; the optimal policy thereof to minimize the time-average AoI is proved to be a round-robin policy with one-packet (latest packet only and others are dropped) buffers (RR-ONE). The optimality is established based on a generalized Poisson-arrival-see-time-average (PASTA) theorem. It is further proved that RR-ONE is asymptotically optimal among all policies in the massive IoT regime. The AoI steady-state stationary distribution under RR-ONE is also derived. A fully decentralized implementation of RR-ONE is proposed which can accommodate dynamic terminal appearances. In addition, considering scenarios where packets cannot be dropped, the optimal AIR policy thereof is also found with parameters given by the solution to a convex problem.
A Simplified Coding Scheme for the Broadcast Channel With Complementary Receiver Side Information Under Individual Secrecy Constraints
Venue: arXiv cs.IT 2018
Year: 2018

This paper simplifies an existing coding scheme for the two-receiver discrete memoryless broadcast channel with complementary receiver side information where there is a passive eavesdropper and individual secrecy is required. The existing coding scheme is simplified in two steps by replacing Wyner secrecy coding with Carleial-Hellman secrecy coding. The resulting simplified scheme is free from redundant message splits and random components. Not least, the simplified scheme retains the existing achievable individual secrecy rate region. Finally, its construction simplicity helps us gain additional insight on the integration of secrecy techniques into error-correcting coding schemes.
EdgeChain: Blockchain-based Multi-vendor Mobile Edge Application Placement
Venue: arXiv cs.NI 2018
Year: 2018

The state-of-the-art mobile edge applications are generating intense traffic and posing rigorous latency requirements to service providers. While resource sharing across multiple service providers can be a way to maximize the utilization of limited resources at the network edge, it requires a centralized repository maintained by all parties for service providers to share status. Moreover, service providers have to trust each other for resource allocation fairness, which is difficult because of potential conflicts of interest. We propose EdgeChain, a blockchain-based architecture to make mobile edge application placement decisions for multiple service providers. We first formulate a stochastic programming problem minimizing the placement cost for mobile edge application placement scenarios. Based on our model, we present a heuristic mobile edge application placement algorithm. As a decentralized public ledger, the blockchain then takes the logic of our algorithm as the smart contract, with the consideration of resources from all mobile edge hosts participating in the system. The algorithm is agreed by all parties and the results will only be accepted by majority of the mining nodes on the blockchain. When a placement decision is made, an edge host meeting the consumer's latency and budget requirements will be selected at the lowest cost. All placement transactions are stored on the blockchain and are traceable by every mobile edge service provider and application vendor who consumes resources at the mobile edge.
Status Updates in a multi-stream M/G/1/1 preemptive queue
Venue: arXiv cs.IT 2018
Year: 2018

We consider a source that collects a multiplicity of streams of updates and sends them through a network to a monitor. However, only a single update can be in the system at a time. Therefore, the transmitter always preempts the packet being served when a new update is generated. We consider Poisson arrivals for each stream and a common general service time, and refer to this system as the multi-stream M/G/1/1 queue with preemption. Using the detour flow graph method, we compute a closed form expression for the average age and the average peak age of each stream. Moreover, we deduce that although all streams are treated equally from a transmission point of view (they all preempt each other), one can still prioritize a stream from an age point of view by simply increasing its generation rate. However, this will increase the sum of the ages which is minimized when all streams have the same update rate.
MSDNN: Multi-Scale Deep Neural Network for Salient Object Detection
Venue: arXiv cs.CV 2018
Year: 2018

Salient object detection is a fundamental problem and has been received a great deal of attentions in computer vision. Recently deep learning model became a powerful tool for image feature extraction. In this paper, we propose a multi-scale deep neural network (MSDNN) for salient object detection. The proposed model first extracts global high-level features and context information over the whole source image with recurrent convolutional neural network (RCNN). Then several stacked deconvolutional layers are adopted to get the multi-scale feature representation and obtain a series of saliency maps. Finally, we investigate a fusion convolution module (FCM) to build a final pixel level saliency map. The proposed model is extensively evaluated on four salient object detection benchmark datasets. Results show that our deep model significantly outperforms other 12 state-of-the-art approaches.
Effect of Meltdown and Spectre Patches on the Performance of HPC Applications
Venue: arXiv cs.PF 2018
Year: 2018

In this work we examine how the updates addressing Meltdown and Spectre vulnerabilities impact the performance of HPC applications. To study this we use the application kernel module of XDMoD to test the performance before and after the application of the vulnerability patches. We tested the performance difference for multiple application and benchmarks including: NWChem, NAMD, HPCC, IOR, MDTest and IMB. The results show that although some specific functions can have performance decreased by as much as 74%, the majority of individual metrics indicates little to no decrease in performance. The real-world applications show a 2-3% decrease in performance for single node jobs and a 5-11% decrease for parallel multi node jobs.
Estimation in the group action channel
Venue: arXiv cs.IT 2018
Year: 2018

We analyze the problem of estimating a signal from multiple measurements on a $\mbox{group action channel}$ that linearly transforms a signal by a random group action followed by a fixed projection and additive Gaussian noise. This channel is motivated by applications such as multi-reference alignment and cryo-electron microscopy. We focus on the large noise regime prevalent in these applications. We give a lower bound on the mean square error (MSE) of any asymptotically unbiased estimator of the signal's orbit in terms of the signal's moment tensors, which implies that the MSE is bounded away from 0 when $N/σ^{2d}$ is bounded from above, where $N$ is the number of observations, $σ$ is the noise standard deviation, and $d$ is the so-called $\mbox{moment order cutoff}$. In contrast, the maximum likelihood estimator is shown to be consistent if $N /σ^{2d}$ diverges.
MOF-BC: A Memory Optimized and Flexible BlockChain for Large Scale Networks
Venue: arXiv cs.CR 2018
Year: 2018

BlockChain (BC) immutability ensures BC resilience against modification or removal of the stored data. In large scale networks like the Internet of Things (IoT), however, this feature significantly increases BC storage size and raises privacy challenges. In this paper, we propose a Memory Optimized and Flexible BC (MOF-BC) that enables the IoT users and service providers to remove or summarize their transactions and age their data and to exercise the "right to be forgotten". To increase privacy, a user may employ multiple keys for different transactions. To allow for the removal of stored transactions, all keys would need to be stored which complicates key management and storage. MOF-BC introduces the notion of a Generator Verifier (GV) which is a signed hash of a Generator Verifier Secret (GVS). The GV changes for each transaction to provide privacy yet is signed by a unique key, thus minimizing the information that needs to be stored. A flexible transaction fee model and a reward mechanism is proposed to incentivize users to participate in optimizing memory consumption. Qualitative security and privacy analysis demonstrates that MOF-BC is resilient against several security attacks. Evaluation results show that MOF-BC decreases BC memory consumption by up to 25\% and the user cost by more than two orders of magnitude compared to conventional BC instantiations.
Detecting Offensive Language in Tweets Using Deep Learning
Venue: arXiv cs.CL 2018
Year: 2018

This paper addresses the important problem of discerning hateful content in social media. We propose a detection scheme that is an ensemble of Recurrent Neural Network (RNN) classifiers, and it incorporates various features associated with user-related information, such as the users' tendency towards racism or sexism. These data are fed as input to the above classifiers along with the word frequency vectors derived from the textual content. Our approach has been evaluated on a publicly available corpus of 16k tweets, and the results demonstrate its effectiveness in comparison to existing state of the art solutions. More specifically, our scheme can successfully distinguish racism and sexism messages from normal text, and achieve higher classification quality than current state-of-the-art algorithms.
Towards the social media studies of science: social media metrics, present and future
Venue: arXiv cs.DL 2018
Year: 2018

In this paper we aim at providing a general reflection around the present and future of social media metrics (or altmetrics) and how they could evolve into a new discipline focused on the study of the relationships and interactions between science and social media, in what could be seen as the social media studies of science.