OpenRaiser/Intern-Atlas huggingface dataset:
A New Class of Nonlinear Precoders for Hardware Efficient Massive MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

A general class of nonlinear Least Square Error (LSE) precoders in multi-user multiple-input multiple-output systems is analyzed using the replica method from statistical mechanics. A single cell downlink channel with $N$ transmit antennas at the base station and $K$ single-antenna users is considered. The data symbols are assumed to be iid Gaussian and the precoded symbols on each transmit antenna are restricted to be chosen from a predefined set $\mathbb{X}$. The set $\mathbb{X}$ encloses several well-known constraints in wireless communications including signals with peak power, constant envelope signals and finite constellations such as Phase Shift Keying (PSK). We determine the asymptotic distortion of the LSE precoder under both the Replica Symmetry (RS) and the one step Replica Symmetry Breaking (1-RSB) assumptions. For the case of peak power constraint on each transmit antenna, our analyses under the RS assumption show that the LSE precoder can reduce the peak to average power ratio to 3dB without any significant performance loss. For PSK constellations, as $N/K$ grows, the RS assumption fails to predict the performance accurately and therefore, investigations under the 1-RSB assumption are further considered. The results show that the 1-RSB assumption is more accurate.
Extending Message Passing Interface Windows to Storage
Venue: arXiv cs.DC 2017
Year: 2017

This work presents an extension to MPI supporting the one-sided communication model and window allocations in storage. Our design transparently integrates with the current MPI implementations, enabling applications to target MPI windows in storage, memory or both simultaneously, without major modifications. Initial performance results demonstrate that the presented MPI window extension could potentially be helpful for a wide-range of use-cases and with low-overhead.
Rationale in Development Chat Messages: An Exploratory Study
Venue: arXiv cs.SE 2017
Year: 2017

Chat messages of development teams play an increasingly significant role in software development, having replaced emails in some cases. Chat messages contain information about discussed issues, considered alternatives and argumentation leading to the decisions made during software development. These elements, defined as rationale, are invaluable during software evolution for documenting and reusing development knowledge. Rationale is also essential for coping with changes and for effective maintenance of the software system. However, exploiting the rationale hidden in the chat messages is challenging due to the high volume of unstructured messages covering a wide range of topics. This work presents the results of an exploratory study examining the frequency of rationale in chat messages, the completeness of the available rationale and the potential of automatic techniques for rationale extraction. For this purpose, we apply content analysis and machine learning techniques on more than 8,700 chat messages from three software development projects. Our results show that chat messages are a rich source of rationale and that machine learning is a promising technique for detecting rationale and identifying different rationale elements.
Security Protection for Magnetic Tunnel Junction
Venue: arXiv cs.CR 2017
Year: 2017

Energy efficiency is one of the most important parameters for designing and building a computing system nowadays. Introduction of new transistor and memory technologies to the integrated circuits design have brought hope for low energy very large scale integration (VLSI) circuit design. This excellency is pleasant if the computing system is secure and the energy is not wasted through execution of malicious actions. In fact, it is required to make sure that the utilized transistor and memory devices function correctly and no error occurs in the system operation. In this regard, we propose a built-in-self-test architecture for security checking of the magnetic tunnel junction (MTJ) device under malicious process variations attack. Also, a general identification technique is presented to investigate the behaviour and activities of the employed circuitries within this MTJ testing architecture. The presented identification technique tries to find any abnormal behaviour using the circuit current signal.
The Parameterized Complexity of Positional Games
Venue: arXiv cs.CC 2017
Year: 2017

We study the parameterized complexity of several positional games. Our main result is that Short Generalized Hex is W[1]-complete parameterized by the number of moves. This solves an open problem from Downey and Fellows' influential list of open problems from 1999. Previously, the problem was thought of as a natural candidate for AW[*]-completeness. Our main tool is a new fragment of first-order logic where universally quantified variables only occur in inequalities. We show that model-checking on arbitrary relational structures for a formula in this fragment is W[1]-complete when parameterized by formula size. We also consider a general framework where a positional game is represented as a hypergraph and two players alternately pick vertices. In a Maker-Maker game, the first player to have picked all the vertices of some hyperedge wins the game. In a Maker-Breaker game, the first player wins if she picks all the vertices of some hyperedge, and the second player wins otherwise. In an Enforcer-Avoider game, the first player wins if the second player picks all the vertices of some hyperedge, and the second player wins otherwise. Short Maker-Maker is AW[*]-complete, whereas Short Maker-Breaker is W[1]-complete and Short Enforcer-Avoider co-W[1]-complete parameterized by the number of moves. This suggests a rough parameterized complexity categorization into positional games that are complete for the first level of the W-hierarchy when the winning configurations only depend on which vertices one player has been able to pick, but AW[*]-completeness when the winning condition depends on which vertices both players have picked. However, some positional games where the board and the winning configurations are highly structured are fixed-parameter tractable. We give another example of such a game, Short k-Connect, which is fixed-parameter tractable when parameterized by the number of moves.
The Web SSO Standard OpenID Connect: In-Depth Formal Security Analysis and Security Guidelines
Venue: arXiv cs.CR 2017
Year: 2017

Web-based single sign-on (SSO) services such as Google Sign-In and Log In with Paypal are based on the OpenID Connect protocol. This protocol enables so-called relying parties to delegate user authentication to so-called identity providers. OpenID Connect is one of the newest and most widely deployed single sign-on protocols on the web. Despite its importance, it has not received much attention from security researchers so far, and in particular, has not undergone any rigorous security analysis. In this paper, we carry out the first in-depth security analysis of OpenID Connect. To this end, we use a comprehensive generic model of the web to develop a detailed formal model of OpenID Connect. Based on this model, we then precisely formalize and prove central security properties for OpenID Connect, including authentication, authorization, and session integrity properties. In our modeling of OpenID Connect, we employ security measures in order to avoid attacks on OpenID Connect that have been discovered previously and new attack variants that we document for the first time in this paper. Based on these security measures, we propose security guidelines for implementors of OpenID Connect. Our formal analysis demonstrates that these guidelines are in fact effective and sufficient.
Locality via Partially Lifted Codes
Venue: arXiv cs.IT 2017
Year: 2017

In error-correcting codes, locality refers to several different ways of quantifying how easily a small amount of information can be recovered from encoded data. In this work, we study a notion of locality called the s-Disjoint-Repair-Group Property (s-DRGP). This notion can interpolate between two very different settings in coding theory: that of Locally Correctable Codes (LCCs) when s is large---a very strong guarantee---and Locally Recoverable Codes (LRCs) when s is small---a relatively weaker guarantee. This motivates the study of the s-DRGP for intermediate s, which is the focus of our paper. We construct codes in this parameter regime which have a higher rate than previously known codes. Our construction is based on a novel variant of the lifted codes of Guo, Kopparty and Sudan. Beyond the results on the s-DRGP, we hope that our construction is of independent interest, and will find uses elsewhere.
Accelerating Discrete Wavelet Transforms on Parallel Architectures
Venue: arXiv cs.PF 2017
Year: 2017

The 2-D discrete wavelet transform (DWT) can be found in the heart of many image-processing algorithms. Until recently, several studies have compared the performance of such transform on various shared-memory parallel architectures, especially on graphics processing units (GPUs). All these studies, however, considered only separable calculation schemes. We show that corresponding separable parts can be merged into non-separable units, which halves the number of steps. In addition, we introduce an optional optimization approach leading to a reduction in the number of arithmetic operations. The discussed schemes were adapted on the OpenCL framework and pixel shaders, and then evaluated using GPUs of two biggest vendors. We demonstrate the performance of the proposed non-separable methods by comparison with existing separable schemes. The non-separable schemes outperform their separable counterparts on numerous setups, especially considering the pixel shaders.
Artificial Intelligence Based Malware Analysis
Venue: arXiv cs.CR 2017
Year: 2017

Artificial intelligence methods have often been applied to perform specific functions or tasks in the cyber-defense realm. However, as adversary methods become more complex and difficult to divine, piecemeal efforts to understand cyber-attacks, and malware-based attacks in particular, are not providing sufficient means for malware analysts to understand the past, present and future characteristics of malware. In this paper, we present the Malware Analysis and Attributed using Genetic Information (MAAGI) system. The underlying idea behind the MAAGI system is that there are strong similarities between malware behavior and biological organism behavior, and applying biologically inspired methods to corpora of malware can help analysts better understand the ecosystem of malware attacks. Due to the sophistication of the malware and the analysis, the MAAGI system relies heavily on artificial intelligence techniques to provide this capability. It has already yielded promising results over its development life, and will hopefully inspire more integration between the artificial intelligence and cyber--defense communities.
Binary Prime Tableau Sequences
Venue: arXiv cs.CR 2017
Year: 2017

This paper proposes a new class of random sequences called binary primes tableau (PT) sequences that have potential applications in cryptography and communications. The PT sequence of rank p is obtained from numbers arranged in a tableau with p columns where primes are marked off until each column has at least one prime and where the column entries are added modulo 2. We also examine the dual to the PT sequences obtained by adding the rows of the tableau. It is shown that PT sequences have excellent autocorrelation properties.
Busy Beaver Scores and Alphabet Size
Venue: arXiv cs.FL 2017
Year: 2017

We investigate the Busy Beaver Game introduced by Rado (1962) generalized to non-binary alphabets. Harland (2016) conjectured that activity (number of steps) and productivity (number of non-blank symbols) of candidate machines grow as the alphabet size increases. We prove this conjecture for any alphabet size under the condition that the number of states is sufficiently large. For the measure activity we show that increasing the alphabet size from two to three allows an increase. By a classical construction it is even possible to obtain a two-state machine increasing activity and productivity of any machine if we allow an alphabet size depending on the number of states of the original machine. We also show that an increase of the alphabet by a factor of three admits an increase of activity.
Obstacle Avoidance through Deep Networks based Intermediate Perception
Venue: arXiv cs.RO 2017
Year: 2017

Obstacle avoidance from monocular images is a challenging problem for robots. Though multi-view structure-from-motion could build 3D maps, it is not robust in textureless environments. Some learning based methods exploit human demonstration to predict a steering command directly from a single image. However, this method is usually biased towards certain tasks or demonstration scenarios and also biased by human understanding. In this paper, we propose a new method to predict a trajectory from images. We train our system on more diverse NYUv2 dataset. The ground truth trajectory is computed from the designed cost functions automatically. The Convolutional Neural Network perception is divided into two stages: first, predict depth map and surface normal from RGB images, which are two important geometric properties related to 3D obstacle representation. Second, predict the trajectory from the depth and normal. Results show that our intermediate perception increases the accuracy by 20% than the direct prediction. Our model generalizes well to other public indoor datasets and is also demonstrated for robot flights in simulation and experiments.
Co-projection-plane based 3-D padding for polyhedron projection for 360-degree video
Venue: arXiv cs.MM 2017
Year: 2017

The polyhedron projection for 360-degree video is becoming more and more popular since it can lead to much less geometry distortion compared with the equirectangular projection. However, in the polyhedron projection, we can observe very obvious texture discontinuity in the area near the face boundary. Such a texture discontinuity may lead to serious quality degradation when motion compensation crosses the discontinuous face boundary. To solve this problem, in this paper, we first propose to fill the corresponding neighboring faces in the suitable positions as the extension of the current face to keep approximated texture continuity. Then a co-projection-plane based 3-D padding method is proposed to project the reference pixels in the neighboring face to the current face to guarantee exact texture continuity. Under the proposed scheme, the reference pixel is always projected to the same plane with the current pixel when performing motion compensation so that the texture discontinuity problem can be solved. The proposed scheme is implemented in the reference software of High Efficiency Video Coding. Compared with the existing method, the proposed algorithm can significantly improve the rate-distortion performance. The experimental results obviously demonstrate that the texture discontinuity in the face boundary can be well handled by the proposed algorithm.
Stream Processing using Grammars and Regular Expressions
Venue: arXiv cs.FL 2017
Year: 2017

In this dissertation we study regular expression based parsing and the use of grammatical specifications for the synthesis of fast, streaming string-processing programs. In the first part we develop two linear-time algorithms for regular expression based parsing with Perl-style greedy disambiguation. The first algorithm operates in two passes in a semi-streaming fashion, using a constant amount of working memory and an auxiliary tape storage which is written in the first pass and consumed by the second. The second algorithm is a single-pass and optimally streaming algorithm which outputs as much of the parse tree as is semantically possible based on the input prefix read so far, and resorts to buffering as many symbols as is required to resolve the next choice. Optimality is obtained by performing a PSPACE-complete pre-analysis on the regular expression. In the second part we present Kleenex, a language for expressing high-performance streaming string processing programs as regular grammars with embedded semantic actions, and its compilation to streaming string transducers with worst-case linear-time performance. Its underlying theory is based on transducer decomposition into oracle and action machines, and a finite-state specialization of the streaming parsing algorithm presented in the first part. In the second part we also develop a new linear-time streaming parsing algorithm for parsing expression grammars (PEG) which generalizes the regular grammars of Kleenex. The algorithm is based on a bottom-up tabulation algorithm reformulated using least fixed points and evaluated using an instance of the chaotic iteration scheme by Cousot and Cousot.
Active Collaborative Ensemble Tracking
Venue: arXiv cs.CV 2017
Year: 2017

A discriminative ensemble tracker employs multiple classifiers, each of which casts a vote on all of the obtained samples. The votes are then aggregated in an attempt to localize the target object. Such method relies on collective competence and the diversity of the ensemble to approach the target/non-target classification task from different views. However, by updating all of the ensemble using a shared set of samples and their final labels, such diversity is lost or reduced to the diversity provided by the underlying features or internal classifiers' dynamics. Additionally, the classifiers do not exchange information with each other while striving to serve the collective goal, i.e., better classification. In this study, we propose an active collaborative information exchange scheme for ensemble tracking. This, not only orchestrates different classifier towards a common goal but also provides an intelligent update mechanism to keep the diversity of classifiers and to mitigate the shortcomings of one with the others. The data exchange is optimized with regard to an ensemble uncertainty utility function, and the ensemble is updated via co-training. The evaluations demonstrate promising results realized by the proposed algorithm for the real-world online tracking.
Generalized Spatial Modulation Aided MmWave MIMO with Sub-Connected Hybrid Precoding Scheme
Venue: arXiv cs.IT 2017
Year: 2017

Due to the high cost and low energy efficiency of the dedicated radio frequency (RF) chains, the number of RF chains in a millimeter wave (mmWave) multiple-input multiple-output (MIMO) system is usually limited from a practical point of view. In this case, the maximum number of independent data streams is also restricted by the number of RF chains, which consequently leads to limiting the potentially attainable spatial multiplexing gain. In order to address this issue, in this paper, a novel generalized spatial modulation (GenSM) aided mmWave MIMO system is proposed, which enables the transmission of an extra data stream via the index of the active antennas group and requires no extra RF chain. Moreover, a two-step algorithm is also proposed to optimize the hybrid precoder design with respect to spectral efficiency (SE) maximization. Finally, numerical simulation results demonstrate the superior SE performance achieved by the proposed scheme.
Relaxing the Irrevocability Requirement for Online Graph Algorithms
Venue: arXiv cs.DS 2017
Year: 2017

Online graph problems are considered in models where the irrevocability requirement is relaxed. Motivated by practical examples where, for example, there is a cost associated with building a facility and no extra cost associated with doing it later, we consider the Late Accept model, where a request can be accepted at a later point, but any acceptance is irrevocable. Similarly, we also consider a Late Reject model, where an accepted request can later be rejected, but any rejection is irrevocable (this is sometimes called preemption). Finally, we consider the Late Accept/Reject model, where late accepts and rejects are both allowed, but any late reject is irrevocable. For Independent Set, the Late Accept/Reject model is necessary to obtain a constant competitive ratio, but for Vertex Cover the Late Accept model is sufficient and for Minimum Spanning Forest the Late Reject model is sufficient. The Matching problem has a competitive ratio of 2, but in the Late Accept/Reject model, its competitive ratio is 3/2.
Image reconstruction by domain transform manifold learning
Venue: arXiv cs.CV 2017
Year: 2017

Image reconstruction plays a critical role in the implementation of all contemporary imaging modalities across the physical and life sciences including optical, MRI, CT, PET, and radio astronomy. During an image acquisition, the sensor encodes an intermediate representation of an object in the sensor domain, which is subsequently reconstructed into an image by an inversion of the encoding function. Image reconstruction is challenging because analytic knowledge of the inverse transform may not exist a priori, especially in the presence of sensor non-idealities and noise. Thus, the standard reconstruction approach involves approximating the inverse function with multiple ad hoc stages in a signal processing chain whose composition depends on the details of each acquisition strategy, and often requires expert parameter tuning to optimize reconstruction performance. We present here a unified framework for image reconstruction, AUtomated TransfOrm by Manifold APproximation (AUTOMAP), which recasts image reconstruction as a data-driven, supervised learning task that allows a mapping between sensor and image domain to emerge from an appropriate corpus of training data. We implement AUTOMAP with a deep neural network and exhibit its flexibility in learning reconstruction transforms for a variety of MRI acquisition strategies, using the same network architecture and hyperparameters. We further demonstrate its efficiency in sparsely representing transforms along low-dimensional manifolds, resulting in superior immunity to noise and reconstruction artifacts compared with conventional handcrafted reconstruction methods. In addition to improving the reconstruction performance of existing acquisition methodologies, we anticipate accelerating the discovery of new acquisition strategies across modalities as the burden of reconstruction becomes lifted by AUTOMAP and learned-reconstruction approaches.
OSPF extension for the support of multi-area networks with arbitrary topologies
Venue: arXiv cs.NI 2017
Year: 2017

OSPF currently supports multi-area networking with two severe limitations, due to the distance vector approach taken in the inter-area routing protocol: (i) the multi-area topology is restricted to a two-level hierarchy, and (ii) globally optimal routing may not be achieved. In this letter, we propose an OSPF extension that overcomes these limitations by adopting a link state inter-area routing protocol. The extension applies to both OSPFv2 (IPv4) and OSPFv3 (IPv6), and is fully transparent to area-internal routers. Despite its simplicity, this extension may have a large impact in the operation of the current Internet.