OpenRaiser/Intern-Atlas huggingface dataset:
On the Feasibility of Wireless Interconnects for High-throughput Data Centers
Venue: arXiv cs.NI 2015
Year: 2015

Data Centers (DCs) are required to be scalable to large data sets so as to accommodate ever increasing demands of resource-limited embedded and mobile devices. Thanks to the availability of recent high data rate millimeter-wave frequency spectrum such as 60GHz and due to the favorable attributes of this technology, wireless DC (WDC) exhibits the potentials of being a promising solution especially for small to medium scale DCs. This paper investigates the problem of throughput scalability of WDCs using the established theory of the asymptotic throughput of wireless multi-hop networks that are primarily proposed for homogeneous traffic conditions. The rate-heterogeneous traffic distribution of a data center however, requires the asymptotic heterogeneous throughput knowledge of a wireless network in order to study the performance and feasibility of WDCs for practical purposes. To answer these questions this paper presents a lower bound for the throughput scalability of a multi-hop rate-heterogeneous network when traffic generation rates of all nodes are similar, except one node. We demonstrate that the throughput scalability of conventional multi-hopping and the spatial reuse of the above bi-rate network is inefficient and henceforth develop a speculative 2-partitioning scheme that improves the network throughput scaling potentials. A better lower bound of the throughput is then obtained. Finally, we obtain the throughput scaling of an i.i.d. rate-heterogeneous network and obtain its lower bound. Again we propose a speculative 2-partitioning scheme to achieve a network with higher throughput in terms of improved lower bound. All of the obtained results have been verified using simulation experiments.
Words with the Maximum Number of Abelian Squares
Venue: arXiv cs.DM 2015
Year: 2015

An abelian square is the concatenation of two words that are anagrams of one another. A word of length $n$ can contain $Θ(n^2)$ distinct factors that are abelian squares. We study infinite words such that the number of abelian square factors of length $n$ grows quadratically with $n$.
Channel Interaction and Current Level Affect Across-Electrode Integration of Interaural Time Differences in Bilateral Cochlear-Implant Listeners
Venue: arXiv cs.SD 2015
Year: 2015

Sensitivity to ITDs is important for sound localization. Normal-hearing listeners benefit from across-frequency processing, as seen with improved ITD thresholds when consistent ITD cues are presented over a range of frequency channels compared to when ITD information is only presented in a single frequency channel. This study aimed to clarify whether cochlear-implant (CI) listeners can make use of similar processing when being stimulated with multiple interaural electrode pairs transmitting consistent ITD information. ITD thresholds for unmodulated, 100-pulse-per-second pulse trains were measured in seven bilateral CI listeners using research interfaces. Consistent ITDs were presented at either one or two electrode pairs at different current levels, allowing for comparisons at either constant level per component electrode or equal overall loudness. Different tonotopic distances between the pairs were tested in order to clarify the potential influence of channel interaction. Comparison of ITD thresholds between double pairs and the respective single pairs revealed systematic effects of tonotopic separation and current level. At constant levels, performance with double-pair stimulation improved compared to single-pair stimulation, but only for large tonotopic separation. Comparisons at equal overall loudness revealed no benefit from presenting ITD information at two electrode pairs for any tonotopic spacing. Irrespective of electrode-pair configuration, ITD sensitivity improved with increasing current level. Hence, the improved ITD sensitivity for double pairs found for a large tonotopic separation and constant current levels seems to be due to increased loudness. The overall data suggest that CI listeners can benefit from combining consistent ITD information across multiple electrodes, provided sufficient stimulus levels and that stimulating electrode pairs are widely spaced.
Precoded GFDM System to Combat Inter Carrier Interference : Performance Analysis
Venue: arXiv cs.IT 2015
Year: 2015

The expected operating scenarios of 5G pose a great challenge to orthogonal frequency division multiplexing (OFDM) which has poor out of band (OoB) spectral properties, stringent synchronization requirements, and large symbol duration. Generalized frequency division multiplexing (GFDM) which is the focus of this work, has been suggested in the literature as one of the possible solutions to meet 5G requirements. In this work, the analytical performance evaluation of MMSE receiver for GFDM is presented. We also proposed precoding techniques to enhance the performance of GFDM. A simplified expression of SINR for MMSE receiver of GFDM is derived using special properties related to the modulation matrix of GFDM, which are described in this work. This SINR is used to evaluate the BER performance. Precoding schemes are proposed to reduce complexity of GFDM-MMSE receiver without compromising on the performance. Block Inverse Discrete Fourier Transform (BIDFT) and Discrete Fourier Transform (DFT) based precoding schemes are found to outperform GFDM-MMSE receiver due to frequency diversity gain while having complexity similar to zero-forcing receiver of GFDM. It is shown that both BIDFT and DFT-based precoding schemes reduce peak to average power ratio (PAPR) significantly. Computational complexity of different transmitters and receivers of precoded and uncoded GFDM is also presented.
Reversible Logic Synthesis with Minimal Usage of Ancilla Bits
Venue: arXiv cs.ET 2015
Year: 2015

Reversible logic has attracted much research interest over the last few decades, especially due to its application in quantum computing. In the construction of reversible gates from basic gates, ancilla bits are commonly used to remove restrictions on the type of gates that a certain set of basic gates generates. With unlimited ancilla bits, many gates (such as Toffoli and Fredkin) become universal reversible gates. However, ancilla bits can be expensive to implement, thus making the problem of minimizing necessary ancilla bits a practical topic. This thesis explores the problem of reversible logic synthesis using a single base gate and a few ancilla bits. Two base gates are discussed: a variation of the 3-bit Toffoli gate and the original 3-bit Fredkin gate. There are three main results associated with these two gates: i) the variated Toffoli gate can generate all n-bit reversible gates using 1 ancilla bit, ii) the variated Toffoli can generate all n-bit reversible gates that are even permutations using no ancilla bit, iii) the Fredkin gate can generate all n-bit conservative reversible gates using 1 ancilla bit. Prior to this paper, the best known result for general universality requires three basic gates, and the best known result for conservative universality needs 5 ancilla bits. The second result is trivially optimal. For the first and the third result, we explicitly prove their optimality: the variated Toffoli cannot generate all n-bit reversible gates without using any extra input lines, and the Fredkin gate cannot generate all n-bit conservative reversible gates without using extra input lines. We also explore a stronger version of the second converse by introducing a new concept called borrowed bits, and prove that the Fredkin gate cannot generate all n-bit conservative reversible gates without ancilla bits, even with an unlimited number of borrowed bits.
A Geometric Perspective on Sparse Filtrations
Venue: arXiv cs.CG 2015
Year: 2015

We present a geometric perspective on sparse filtrations used in topological data analysis. This new perspective leads to much simpler proofs, while also being more general, applying equally to Rips filtrations and Cech filtrations for any convex metric. We also give an algorithm for finding the simplices in such a filtration and prove that the vertex removal can be implemented as a sequence of elementary edge collapses.
Ciberseguridad Inteligente
Venue: arXiv cs.CR 2015
Year: 2015

The Internet Economy has a strong dependency on cyberspace. This raises security risk scenarios due to the increasing number of vulnerabilities and the increased frequency and sophistication of cyber attacks, especially with the advent of advanced threats of APT type. This paper presents a model of Intelligent Cybersecurity (ICS) for detect, deny, disrupt, degrade, deceive and destroy enemy capabilities in cyberspace. This is achieved through the conceptual and technical development of a Capacity for Cyber Intelligence (CCI) which aims to interfere destructively C2 capabilities of the adversary, penetrating its decision loops with the speed necessary to displace him to a reactive posture. Finally, unlike the security models raised classically, the concept of ICSI suggests that the advantage in the conflict can be obtained by defense and not always by the attacker. As theoretical support, the "Offensive System Reference Model" (OSRM) is presented, which is used to think cyber conflict at all levels, from a perspective coordinated and synchronized with the rest of the traditional forces under the present set; and a justification of the capacity from the modern perspective C2.
The one-dimensional Euclidean domain: Finitely many obstructions are not enough
Venue: arXiv cs.GT 2015
Year: 2015

We show that one-dimensional Euclidean preference profiles can not be characterized in terms of finitely many forbidden substructures. This result is in strong contrast to the case of single-peaked and single-crossing preference profiles, for which such finite characterizations have been derived in the literature.
Counterexample for the 2-approximation of finding partitions of rectilinear polygons with minimum stabbing number
Venue: arXiv cs.CG 2015
Year: 2015

This paper presents a counterexample for the approximation algorithm proposed by Durocher and Mehrabi [1] for the general problem of finding a rectangular partition of a rectilinear polygon with minimum stabbing number.
Diamond Sampling for Approximate Maximum All-pairs Dot-product (MAD) Search
Venue: arXiv cs.SI 2015
Year: 2015

Given two sets of vectors, $A = \{{a_1}, \dots, {a_m}\}$ and $B=\{{b_1},\dots,{b_n}\}$, our problem is to find the top-$t$ dot products, i.e., the largest $|{a_i}\cdot{b_j}|$ among all possible pairs. This is a fundamental mathematical problem that appears in numerous data applications involving similarity search, link prediction, and collaborative filtering. We propose a sampling-based approach that avoids direct computation of all $mn$ dot products. We select diamonds (i.e., four-cycles) from the weighted tripartite representation of $A$ and $B$. The probability of selecting a diamond corresponding to pair $(i,j)$ is proportional to $({a_i}\cdot{b_j})^2$, amplifying the focus on the largest-magnitude entries. Experimental results indicate that diamond sampling is orders of magnitude faster than direct computation and requires far fewer samples than any competing approach. We also apply diamond sampling to the special case of maximum inner product search, and get significantly better results than the state-of-the-art hashing methods.
Leading Tree in DPCLUS and Its Impact on Building Hierarchies
Venue: arXiv cs.AI 2015
Year: 2015

This paper reveals the tree structure as an intermediate result of clustering by fast search and find of density peaks (DPCLUS), and explores the power of using this tree to perform hierarchical clustering. The array used to hold the index of the nearest higher-densitied object for each object can be transformed into a Leading Tree (LT), in which each parent node P leads its child nodes to join the same cluster as P itself, and the child nodes are sorted by their gamma values in descendant order to accelerate the disconnecting of root in each subtree. There are two major advantages with the LT: One is dramatically reducing the running time of assigning noncenter data points to their cluster ID, because the assigning process is turned into just disconnecting the links from each center to its parent. The other is that the tree model for representing clusters is more informative. Because we can check which objects are more likely to be selected as centers in finer grained clustering, or which objects reach to its center via less jumps. Experiment results and analysis show the effectiveness and efficiency of the assigning process with an LT.
Place classification with a graph regularized deep neural network model
Venue: arXiv cs.RO 2015
Year: 2015

Place classification is a fundamental ability that a robot should possess to carry out effective human-robot interactions. It is a nontrivial classification problem which has attracted many research. In recent years, there is a high exploitation of Artificial Intelligent algorithms in robotics applications. Inspired by the recent successes of deep learning methods, we propose an end-to-end learning approach for the place classification problem. With the deep architectures, this methodology automatically discovers features and contributes in general to higher classification accuracies. The pipeline of our approach is composed of three parts. Firstly, we construct multiple layers of laser range data to represent the environment information in different levels of granularity. Secondly, each layer of data is fed into a deep neural network model for classification, where a graph regularization is imposed to the deep architecture for keeping local consistency between adjacent samples. Finally, the predicted labels obtained from all the layers are fused based on confidence trees to maximize the overall confidence. Experimental results validate the effective- ness of our end-to-end place classification framework in which both the multi-layer structure and the graph regularization promote the classification performance. Furthermore, results show that the features automatically learned from the raw input range data can achieve competitive results to the features constructed based on statistical and geometrical information.
Scalable RAN Virtualization in Multi-Tenant LTE-A Heterogeneous Networks (Extended version)
Venue: arXiv cs.NI 2015
Year: 2015

Cellular communications are evolving to facilitate the current and expected increasing needs of Quality of Service (QoS), high data rates and diversity of offered services. Towards this direction, Radio Access Network (RAN) virtualization aims at providing solutions of mapping virtual network elements onto radio resources of the existing physical network. This paper proposes the Resources nEgotiation for NEtwork Virtualization (RENEV) algorithm, suitable for application in Heterogeneous Networks (HetNets) in Long Term Evolution-Advanced (LTE-A) environments, consisting of a macro evolved NodeB (eNB) overlaid with small cells. By exploiting Radio Resource Management (RRM) principles, RENEV achieves slicing and on demand delivery of resources. Leveraging the multi-tenancy approach, radio resources are transferred in terms of physical radio Resource Blocks (RBs) among multiple heterogeneous base stations, interconnected via the X2 interface. The main target is to deal with traffic variations in geographical dimension. All signaling design considerations under the current Third Generation Partnership Project (3GPP) LTE-A architecture are also investigated. Analytical studies and simulation experiments are conducted to evaluate RENEV in terms of network's throughput as well as its additional signaling overhead. Moreover we show that RENEV can be applied independently on top of already proposed schemes for RAN virtualization to improve their performance. The results indicate that significant merits are achieved both from network's and users' perspective as well as that it is a scalable solution for different number of small cells.
The computability path ordering
Venue: arXiv cs.LO 2015
Year: 2015

This paper aims at carrying out termination proofs for simply typed higher-order calculi automatically by using ordering comparisons. To this end, we introduce the computability path ordering (CPO), a recursive relation on terms obtained by lifting a precedence on function symbols. A first version, core CPO, is essentially obtained from the higher-order recursive path ordering (HORPO) by eliminating type checks from some recursive calls and by incorporating the treatment of bound variables as in the com-putability closure. The well-foundedness proof shows that core CPO captures the essence of computability arguments á la Tait and Girard, therefore explaining its name. We further show that no further type check can be eliminated from its recursive calls without loosing well-foundedness, but for one for which we found no counterexample yet. Two extensions of core CPO are then introduced which allow one to consider: the first, higher-order inductive types; the second, a precedence in which some function symbols are smaller than application and abstraction.
Sparse Multi-layer Image Approximation: Facial Image Compression
Venue: arXiv cs.CV 2015
Year: 2015

We propose a scheme for multi-layer representation of images. The problem is first treated from an information-theoretic viewpoint where we analyze the behavior of different sources of information under a multi-layer data compression framework and compare it with a single-stage (shallow) structure. We then consider the image data as the source of information and link the proposed representation scheme to the problem of multi-layer dictionary learning for visual data. For the current work we focus on the problem of image compression for a special class of images where we report a considerable performance boost in terms of PSNR at high compression ratios in comparison with the JPEG2000 codec.
Variations in Tracking in Relation to Geographic Location
Venue: arXiv cs.CR 2015
Year: 2015

Different countries have different privacy regulatory models. These models impact the perspectives and laws surrounding internet privacy. However, little is known about how effective the regulatory models are when it comes to limiting online tracking and advertising activity. In this paper, we propose a method for investigating tracking behavior by analyzing cookies and HTTP requests from browsing sessions originating in different countries. We collect browsing data from visits to top websites in various countries that utilize different regulatory models. We found that there are significant differences in tracking activity between different countries using several metrics. We also suggest various ways to extend this study which may yield a more complete representation of tracking from a global perspective.
A case study in almost-perfect security for unconditionally secure communication
Venue: arXiv cs.CR 2015
Year: 2015

In the Russian cards problem, Alice, Bob and Cath draw $a$, $b$ and $c$ cards, respectively, from a publicly known deck. Alice and Bob must then communicate their cards to each other without Cath learning who holds a single card. Solutions in the literature provide weak security, where Cath does not know with certainty who holds each card that is not hers, or perfect security, where Cath learns no probabilistic information about who holds any given card from Alice and Bob's exchange. We propose an intermediate notion, which we call $\varepsilon$-strong security, where the probabilities perceived by Cath may only change by a factor of $\varepsilon$. We then show that a mild variant of the so-called geometric strategy gives $\varepsilon$-strong safety for arbitrarily small $\varepsilon$ and appropriately chosen values of $a,b,c$.
Improved Greedy Algorithm for Set Covering Problem
Venue: arXiv cs.DS 2015
Year: 2015

This paper proposes a greedy algorithm named as Big step greedy set cover algorithm to compute approximate minimum set cover. The Big step greedy algorithm, in each step selects p sets such that the union of selected p sets contains greatest number of uncovered elements and adds the selected p sets to partial set cover. The process of adding p sets is repeated until all the elements are covered. When p=1 it behaves like the classical greedy algorithm.
Reading Scene Text in Deep Convolutional Sequences
Venue: arXiv cs.CV 2015
Year: 2015

We develop a Deep-Text Recurrent Network (DTRN) that regards scene text reading as a sequence labelling problem. We leverage recent advances of deep convolutional neural networks to generate an ordered high-level sequence from a whole word image, avoiding the difficult character segmentation problem. Then a deep recurrent model, building on long short-term memory (LSTM), is developed to robustly recognize the generated CNN sequences, departing from most existing approaches recognising each character independently. Our model has a number of appealing properties in comparison to existing scene text recognition methods: (i) It can recognise highly ambiguous words by leveraging meaningful context information, allowing it to work reliably without either pre- or post-processing; (ii) the deep CNN feature is robust to various image distortions; (iii) it retains the explicit order information in word image, which is essential to discriminate word strings; (iv) the model does not depend on pre-defined dictionary, and it can process unknown words and arbitrary strings. Codes for the DTRN will be available.
Tree Compression with Top Trees Revisited
Venue: arXiv cs.DS 2015
Year: 2015

We revisit tree compression with top trees (Bille et al, ICALP'13) and present several improvements to the compressor and its analysis. By significantly reducing the amount of information stored and guiding the compression step using a RePair-inspired heuristic, we obtain a fast compressor achieving good compression ratios, addressing an open problem posed by Bille et al. We show how, with relatively small overhead, the compressed file can be converted into an in-memory representation that supports basic navigation operations in worst-case logarithmic time without decompression. We also show a much improved worst-case bound on the size of the output of top-tree compression (answering an open question posed in a talk on this algorithm by Weimann in 2012).
Applications of Uniform Sampling: Densest Subgraph and Beyond
Venue: arXiv cs.DS 2015
Year: 2015

Recently [Bhattacharya et al., STOC 2015] provide the first non-trivial algorithm for the densest subgraph problem in the streaming model with additions and deletions to its edges, i.e., for dynamic graph streams. They present a $(0.5-ε)$-approximation algorithm using $\tilde{O}(n)$ space, where factors of $ε$ and $\log(n)$ are suppressed in the $\tilde{O}$ notation. However, the update time of this algorithm is large. To remedy this, they also provide a $(0.25-ε)$-approximation algorithm using $\tilde{O}(n)$ space with update time $\tilde{O}(1)$. In this paper we improve the algorithms by Bhattacharya et al. by providing a $(1-ε)$-approximation algorithm using $\tilde{O}(n)$ space. Our algorithm is conceptually simple - it samples $\tilde{O}(n)$ edges uniformly at random, and finds the densest subgraph on the sampled graph. We also show how to perform this sampling with update time $\tilde{O}(1)$. In addition to this, we show that given oracle access to the edge set, we can implement our algorithm in time $\tilde{O}(n)$ on a graph in the standard RAM model. To the best of our knowledge this is the fastest $(0.5-ε)$-approximation algorithm for the densest subgraph problem in the RAM model given such oracle access. Further, we extend our results to a general class of graph optimization problems that we call heavy subgraph problems. This class contains many interesting problems such as densest subgraph, directed densest subgraph, densest bipartite subgraph, $d$-cut and $d$-heavy connected component. Our result, by characterizing heavy subgraph problems, partially addresses open problem 13 at the IITK Workshop on Algorithms for Data Streams in 2006 regarding the effects of subsampling in this context.