OpenRaiser/Intern-Atlas huggingface dataset:
Character-Aware Neural Language Models
Venue: arXiv cs.CL 2015
Year: 2015

We describe a simple neural language model that relies only on character-level inputs. Predictions are still made at the word-level. Our model employs a convolutional neural network (CNN) and a highway network over characters, whose output is given to a long short-term memory (LSTM) recurrent neural network language model (RNN-LM). On the English Penn Treebank the model is on par with the existing state-of-the-art despite having 60% fewer parameters. On languages with rich morphology (Arabic, Czech, French, German, Spanish, Russian), the model outperforms word-level/morpheme-level LSTM baselines, again with fewer parameters. The results suggest that on many languages, character inputs are sufficient for language modeling. Analysis of word representations obtained from the character composition part of the model reveals that the model is able to encode, from characters only, both semantic and orthographic information.
Network Coding for Video Distortion Reduction in Device-to-Device Communications
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we study the problem of distributing a real-time video sequence to a group of partially connected cooperative wireless devices using instantly decodable network coding (IDNC). In such a scenario, the coding conflicts occur to service multiple devices with an immediately decodable packet and the transmission conflicts occur from simultaneous transmissions of multiple devices. To avoid these conflicts, we introduce a novel IDNC graph that represents all feasible coding and transmission conflict-free decisions in one unified framework. Moreover, a real-time video sequence has a hard deadline and unequal importance of video packets. Using these video characteristics and the new IDNC graph, we formulate the problem of minimizing the mean video distortion before the deadline as a finite horizon Markov decision process (MDP) problem. However, the backward induction algorithm that finds the optimal policy of the MDP formulation has high modelling and computational complexities. To reduce these complexities, we further design a two-stage maximal independent set selection algorithm, which can efficiently reduce the mean video distortion before the deadline. Simulation results over a real video sequence show that our proposed IDNC algorithms improve the received video quality compared to the existing IDNC algorithms.
NETCS: A New Simulator of Population Protocols and Network Constructors
Venue: arXiv cs.DC 2015
Year: 2015

Network Constructors are an extension of the standard population protocol model in which finite-state agents interact in pairs under the control of an adversary scheduler. In this work we present NETCS, a simulator designed to evaluate the performance of various network constructors and population protocols under different schedulers and network configurations. Our simulator provides researchers with an intuitive user interface and a quick experimentation environment to evaluate their work. It also harnesses the power of the cloud, as experiments are executed remotely and scheduled through the web interface provided. To prove the validity and quality of our simulator we provide an extensive evaluation of multiple protocols with more than 100000 experiments for different network sizes and configurations that validate the correctness of the theoretical analysis of existing protocols and estimate the real values of the hidden asymptotic coefficients. We also show experimentally (with more than 40000 experiments) that a probabilistic algorithm is capable of counting the actual size of the network in bounded time given a unique leader.
A New Energy Efficient Beamforming Strategy for MISO Interfering Broadcast Channels based on Large Systems Analysis
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a new beamforming design to maximize energy efficiency (EE) for multiple input single output interfering broadcast channels (IFBC). Under this model, the EE problem is non-convex in general due to the coupled interference and its fractional form, and thus it is difficult to solve the problem. Conventional algorithms which address this problem have adopted an iterative method for each channel realization, which requires high computational complexity. In order to reduce the computational complexity, we parameterize the beamforming vector by scalar parameters related to beam direction and power. Then, by employing asymptotic results of random matrix theory with this parametrization, we identify the optimal parameters to maximize the EE in the large system limit assuming that the number of transmit antennas and users are large with a fixed ratio. In the asymptotic regime, our solutions depend only on the second order channel statistics, which yields significantly reduced computational complexity and system overhead compared to the conventional approaches. Hence, the beamforming vector to maximize the EE performance can be determined with local channel state information and the optimized parameters. Based on the asymptotic results, the proposed scheme can provide insights on the average EE performance, and a simple yet efficient beamforming strategy is introduced for the finite system case. Numerical results confirm that the proposed scheme shows a negligible performance loss compared to the best result achieved by the conventional approaches even with small system dimensions, with much reduced system complexity.
On Embeddability of Buses in Point Sets
Venue: arXiv cs.CG 2015
Year: 2015

Set membership of points in the plane can be visualized by connecting corresponding points via graphical features, like paths, trees, polygons, ellipses. In this paper we study the \emph{bus embeddability problem} (BEP): given a set of colored points we ask whether there exists a planar realization with one horizontal straight-line segment per color, called bus, such that all points with the same color are connected with vertical line segments to their bus. We present an ILP and an FPT algorithm for the general problem. For restricted versions of this problem, such as when the relative order of buses is predefined, or when a bus must be placed above all its points, we provide efficient algorithms. We show that another restricted version of the problem can be solved using 2-stack pushall sorting. On the negative side we prove the NP-completeness of a special case of BEP.
Sistem Informasi Eksekutif Berbasis Web pada Fakultas Pertanian Universitas Muhammadiyah Palembang
Venue: arXiv cs.CY 2015
Year: 2015

Information technology (IT) is able to fulfill one of the main needs of an organization, such as how the executive know and manage the performance of the organization he leads, including the human resources (HR). Faculty of Agriculture, University of Muhammadiyah Palembang (UMP) has had personnel information system which is used to manage HR data both employees and lecturers. However, the information system is to support the operational activities only. Therefore it is necessary to build an executive information system (SIE) in the faculty is the dean. By using the SIE, the dean can easily access summary data visualization, namely the appearance of information in the form of graphs making it easier for executives to make decisions.
Dependent Inductive and Coinductive Types are Fibrational Dialgebras
Venue: arXiv cs.LO 2015
Year: 2015

In this paper, I establish the categorical structure necessary to interpret dependent inductive and coinductive types. It is well-known that dependent type theories à la Martin-Löf can be interpreted using fibrations. Modern theorem provers, however, are based on more sophisticated type systems that allow the definition of powerful inductive dependent types (known as inductive families) and, somewhat limited, coinductive dependent types. I define a class of functors on fibrations and show how data type definitions correspond to initial and final dialgebras for these functors. This description is also a proposal of how coinductive types should be treated in type theories, as they appear here simply as dual of inductive types. Finally, I show how dependent data types correspond to algebras and coalgebras, and give the correspondence to dependent polynomial functors.
Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis
Venue: arXiv cs.DS 2015
Year: 2015

The Workflow Satisfiability Problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification, subject to certain constraints on the assignment. The problem is NP-hard even when restricted to just not equals constraints. Since the number of steps $k$ is relatively small in practice, Wang and Li (2010) introduced a parametrisation of WSP by $k$. Wang and Li (2010) showed that, in general, the WSP is W[1]-hard, i.e., it is unlikely that there exists a fixed-parameter tractable (FPT) algorithm for solving the WSP. Crampton et al. (2013) and Cohen et al. (2014) designed FPT algorithms of running time $O^*(2^{k})$ and $O^*(2^{k\log_2 k})$ for the WSP with so-called regular and user-independent constraints, respectively. In this note, we show that there are no algorithms of running time $O^*(2^{ck})$ and $O^*(2^{ck\log_2 k})$ for the two restrictions of WSP, respectively, with any $c<1$, unless the Strong Exponential Time Hypothesis fails.
The maximum time of 2-neighbour bootstrap percolation in grid graphs and some parameterized results
Venue: arXiv cs.CC 2015
Year: 2015

In 2-neighborhood bootstrap percolation on a graph $G$, an infection spreads according to the following deterministic rule: infected vertices of $G$ remain infected forever and in consecutive rounds healthy vertices with at least two already infected neighbors become infected. Percolation occurs if eventually every vertex is infected. The maximum time $t(G)$ is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved by Benevides et al \cite{eurocomb13} that $t(G)$ is NP-hard for planar graphs and that deciding whether $t(G)\geq k$ is polynomial time solvable for $k\leq 2$, but is NP-complete for $k\geq 4$. They left two open problems about the complexity for $k=3$ and for planar bipartite graphs. In 2014, we solved the first problem\cite{wg2014}. In this paper, we solve the second one by proving that $t(G)$ is NP-complete even in grid graphs with maximum degree 3. We also prove that $t(G)$ is polynomial time solvable for solid grid graphs with maximum degree 3. Moreover, we prove that the percolation time problem is W[1]-hard on the treewidth of the graph, but it is fixed parameter tractable with parameters treewidth$+k$ and maxdegree$+k$.
Classification of the Extremely Low Frequency Magnetic Field Radiation Measurement from the Laptop Computers
Venue: arXiv cs.CY 2015
Year: 2015

The paper considers the level of the extremely low-frequency magnetic field, which is produced by laptop computers. The magnetic field, which is characterized by extremely low frequencies up to 300 Hz is measured due to its hazardous effects to the laptop user's health. The experiment consists of testing 13 different laptop computers in normal operation conditions. The measuring of the magnetic field is performed in the adjacent neighborhood of the laptop computers. The measured data are presented and then classified. The classification is performed by the K-Medians method in order to determine the critical positions of the laptop. At the end, the measured magnetic field values are compared with the critical values suggested by different safety standards. It is shown that some of the laptop computers emit a very strong magnetic field. Hence, they must be used with extreme caution.
Low-complexity Non-coherent Signal Detection for Nano-Scale Molecular Communications
Venue: arXiv cs.ET 2015
Year: 2015

Nano-scale molecular communication is a viable way of exchanging information between nano-machines. In this letter, a low-complexity and non-coherent signal detection technique is proposed to mitigate the inter-symbol-interference (ISI) and additive noise. In contrast to existing coherent detection methods of high complexity, the proposed non-coherent signal detector is more practical when the channel conditions are hard to acquire accurately or hidden from the receiver. The proposed scheme employs the concentration difference to detect the ISI corrupted signals and we demonstrate that it can suppress the ISI effectively. The concentration difference is a stable characteristic, irrespective of the diffusion channel conditions. In terms of complexity, by excluding matrix operations or likelihood calculations, the new detection scheme is particularly suitable for nano-scale molecular communication systems with a small energy budget or limited computation resource.
Performance monitoring for multicore embedded computing systems on FPGAs
Venue: arXiv cs.AR 2015
Year: 2015

When designing modern embedded computing systems, most software programmers choose to use multicore processors, possibly in combination with general-purpose graphics processing units (GPGPUs) and/or hardware accelerators. They also often use an embedded Linux O/S and run multi-application workloads that may even be multi-threaded. Modern FPGAs are large enough to combine multicore hard/soft processors with multiple hardware accelerators as custom compute units, enabling entire embedded compute systems to be implemented on a single FPGA. Furthermore, the large FPGA vendors also support embedded Linux kernels for both their soft and embedded processors. When combined with high-level synthesis to generate hardware accelerators using a C-to-gates flows, the necessary primitives for a framework that can enable software designers to use FPGAs as their custom compute platform now exist. However, in order to ensure that computing resources are integrated and shared effectively, software developers need to be able to monitor and debug the runtime performance of the applications in their workload. This paper describes ABACUS, a performance-monitoring framework that can be used to debug the execution behaviours and interactions of multi-application workloads on multicore systems. We also discuss how this framework is extensible for use with hardware accelerators in heterogeneous systems.
Virtualization Architecture for NoC-based Reconfigurable Systems
Venue: arXiv cs.AR 2015
Year: 2015

We propose a virtualization architecture for NoC-based reconfigurable systems. The motivation of this work is to develop a service-oriented architecture that includes Partial Reconfigurable Region as a Service (PRRaaS) and Processing Element as a Service (PEaaS) for software applications. According to the requirements of software applications, new PEs can be created on-demand by (re)configuring the logic resource of the PRRs in the FPGA, while the configured PEs can also be virtualized to support multiple application tasks at the same time. As a result, such a two-level virtualization mechanism, including the gate-level virtualization and the PE-level virtualization, enables an SoC to be dynamically adapted to changing application requirements. Therefore, more software applications can be performed, and system performance can be further enhanced.
Discrete Hashing with Deep Neural Network
Venue: arXiv cs.CV 2015
Year: 2015

This paper addresses the problem of learning binary hash codes for large scale image search by proposing a novel hashing method based on deep neural network. The advantage of our deep model over previous deep model used in hashing is that our model contains necessary criteria for producing good codes such as similarity preserving, balance and independence. Another advantage of our method is that instead of relaxing the binary constraint of codes during the learning process as most previous works, in this paper, by introducing the auxiliary variable, we reformulate the optimization into two sub-optimization steps allowing us to efficiently solve binary constraints without any relaxation. The proposed method is also extended to the supervised hashing by leveraging the label information such that the learned binary codes preserve the pairwise label of inputs. The experimental results on three benchmark datasets show the proposed methods outperform state-of-the-art hashing methods.
Unified System for Processing Real and Simulated Data in the ATLAS Experiment
Venue: arXiv cs.DC 2015
Year: 2015

The physics goals of the next Large Hadron Collider run include high precision tests of the Standard Model and searches for new physics. These goals require detailed comparison of data with computational models simulating the expected data behavior. To highlight the role which modeling and simulation plays in future scientific discovery, we report on use cases and experience with a unified system built to process both real and simulated data of growing volume and variety.
Varying-coefficient models with isotropic Gaussian process priors
Venue: arXiv cs.LG 2015
Year: 2015

We study learning problems in which the conditional distribution of the output given the input varies as a function of additional task variables. In varying-coefficient models with Gaussian process priors, a Gaussian process generates the functional relationship between the task variables and the parameters of this conditional. Varying-coefficient models subsume hierarchical Bayesian multitask models, but also generalizations in which the conditional varies continuously, for instance, in time or space. However, Bayesian inference in varying-coefficient models is generally intractable. We show that inference for varying-coefficient models with isotropic Gaussian process priors resolves to standard inference for a Gaussian process that can be solved efficiently. MAP inference in this model resolves to multitask learning using task and instance kernels, and inference for hierarchical Bayesian multitask models can be carried out efficiently using graph-Laplacian kernels. We report on experiments for geospatial prediction.
Graphulo: Linear Algebra Graph Kernels for NoSQL Databases
Venue: arXiv cs.DS 2015
Year: 2015

Big data and the Internet of Things era continue to challenge computational systems. Several technology solutions such as NoSQL databases have been developed to deal with this challenge. In order to generate meaningful results from large datasets, analysts often use a graph representation which provides an intuitive way to work with the data. Graph vertices can represent users and events, and edges can represent the relationship between vertices. Graph algorithms are used to extract meaningful information from these very large graphs. At MIT, the Graphulo initiative is an effort to perform graph algorithms directly in NoSQL databases such as Apache Accumulo or SciDB, which have an inherently sparse data storage scheme. Sparse matrix operations have a history of efficient implementations and the Graph Basic Linear Algebra Subprogram (GraphBLAS) community has developed a set of key kernels that can be used to develop efficient linear algebra operations. However, in order to use the GraphBLAS kernels, it is important that common graph algorithms be recast using the linear algebra building blocks. In this article, we look at common classes of graph algorithms and recast them into linear algebra operations using the GraphBLAS building blocks.
Analysis and Practice of Uniquely Decodable One-to-One Code
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the so-called uniquely decodable one-to-one code (UDOOC) that is formed by inserting a "comma" indicator, termed the unique word (UW), between consecutive one-to-one codewords for separation. Along this research direction, we first investigate several general combinatorial properties of UDOOCs, in particular the enumeration of the number of UDOOC codewords for any (finite) codeword length. Based on the obtained formula on the number of length-n codewords for a given UW, the per-letter average codeword length of UDOOC for the optimal compression of a given source statistics can be computed. Several upper bounds on the average codeword length of such UDOOCs are next established. The analysis on the bounds of average codeword length then leads to two asymptotic bounds for sources having infinitely many alphabets, one of which is achievable and hence tight for a certain source statistics and UW, and the other of which proves the achievability of source entropy rate of UDOOCs when both the block size of source letters for UDOOC compression and UW length go to infinity. Efficient encoding and decoding algorithms for UDOOCs are also given in this paper. Numerical results show that the proposed UDOOCs can potentially result in comparable compression rate to the Huffman code under similar decoding complexity and yield a smaller average codeword length than that of the Lempel-Ziv code, thereby confirming the practicability of UDOOCs.
New Classes of Permutation Binomials and Permutation Trinomials over Finite Fields
Venue: arXiv cs.IT 2015
Year: 2015

Permutation polynomials over finite fields play important roles in finite fields theory. They also have wide applications in many areas of science and engineering such as coding theory, cryptography, combinatorial design, communication theory and so on. Permutation binomials and trinomials attract people's interest due to their simple algebraic form and additional extraordinary properties. In this paper, several new classes of permutation binomials and permutation trinomials are constructed. Some of these permutation polynomials are generalizations of known ones.
Rate-Compatible Polar Codes for Wireless Channels
Venue: arXiv cs.IT 2015
Year: 2015

A design of rate-compatible polar codes suitable for HARQ communications is proposed in this paper. An important feature of the proposed design is that the puncturing order is chosen with low complexity on a base code of short length, which is then further polarized to the desired length. A practical rate-matching system that has the flexibility to choose any desired rate through puncturing or repetition while preserving the polarization is suggested. The proposed rate-matching system is combined with channel interleaving and a bit-mapping procedure that preserves the polarization of the rate-compatible polar code family over bit-interleaved coded modulation systems. Simulation results on AWGN and fast fading channels with different modulation orders show the robustness of the proposed rate-compatible polar code in both Chase combining and incremental redundancy HARQ communications.
Optimal Power Allocation for A Massive MIMO Relay Aided Secure Communication
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we address the problem of optimal power allocation at the relay in two-hop secure communications under practical conditions. To guarantee secure communication during the long-distance transmission, the massive MIMO (M-MIMO) relaying techniques are explored to significantly enhance wireless security. The focus of this paper is on the analysis and design of optimal power assignment for a decode-and-forward (DF) M-MIMO relay, so as to maximize the secrecy outage capacity and minimize the interception probability, respectively. Our study reveals the condition for a nonnegative the secrecy outage capacity, obtains closed-form expressions for optimal power, and presents the asymptotic characteristics of secrecy performance. Finally, simulation results validate the effectiveness of the proposed schemes.