OpenRaiser/Intern-Atlas huggingface dataset:
Linear Network Coding Capacity Region of The Smart Repeater with Broadcast Erasure Channels
Venue: arXiv cs.IT 2016
Year: 2016

This work considers the smart repeater network where a single source $s$ wants to send two independent packet streams to destinations $\{d_1,d_2\}$ with the help of relay $r$. The transmission from $s$ or $r$ is modeled by packet erasure channels: For each time slot, a packet transmitted by $s$ may be received, with some probabilities, by a random subset of $\{d_1,d_2,r\}$; and those transmitted by $r$ will be received by a random subset of $\{d_1,d_2\}$. Interference is avoided by allowing at most one of $\{s,r\}$ to transmit in each time slot. One example of this model is any cellular network that supports two cell-edge users when a relay in the middle uses the same downlink resources for throughput/safety enhancement. In this setting, we study the capacity region of $(R_1,R_2)$ when allowing linear network coding (LNC). The proposed LNC inner bound introduces more advanced packing-mixing operations other than the previously well-known butterfly-style XOR operation on overheard packets of two co-existing flows. A new LNC outer bound is derived by exploring the inherent algebraic structure of the LNC problem. Numerical results show that, with more than 85% of the experiments, the relative sum-rate gap between the proposed outer and inner bounds is smaller than 0.08% under the strong-relaying setting and 0.04% under arbitrary distributions, thus effectively bracketing the LNC capacity of the smart repeater problem.
Learning from the memory of Atari 2600
Venue: arXiv cs.LG 2016
Year: 2016

We train a number of neural networks to play games Bowling, Breakout and Seaquest using information stored in the memory of a video game console Atari 2600. We consider four models of neural networks which differ in size and architecture: two networks which use only information contained in the RAM and two mixed networks which use both information in the RAM and information from the screen. As the benchmark we used the convolutional model proposed in NIPS and received comparable results in all considered games. Quite surprisingly, in the case of Seaquest we were able to train RAM-only agents which behave better than the benchmark screen-only agent. Mixing screen and RAM did not lead to an improved performance comparing to screen-only and RAM-only agents.
A Linearization Technique for Self-Interference Cancellation in Full-Duplex Radios
Venue: arXiv cs.NI 2016
Year: 2016

The fundamental problem in the design of a full-duplex radio is the cancellation of the self-interference (SI) signal generated by the transmitter.Current techniques for suppressing SI rely on generating a copy of the SI signal and subtracting it partly in the RF (radio frequency) and digital domains. A critical step in replicating the self-interference is the estimation of the multi-path channel through which the transmitted signal propagates to the antenna. Since there is no prior model on the number of multipath reflections, current techniques assume a tap delay line filter (in the RF and digital domain) with a large number of taps, and estimate the taps in the analog and the digital domain. Assuming such a model leads to a large form-factor for the analog and RF circuits and increased complexity in the digital domain. In this paper, using a linearization technique, we show that the self-interference channel in an indoor environment can be effectively modelled as $H(f)=C_0 + C_1f$ in the frequency domain. Thus, the effective self-interference channel can be represented by two parameters $C_0$ and $C_1$, irrespective of the multipath environment. We also provide experimental evidence to verify the above channel model and propose novel low-complexity designs for self-interference cancellation. Linearization not only aids in the practicality of analog cancellation by reducing the form factor, but also results in a simpler SI filter model in the digital domain due to dimensionality reduction of the channel parameters. Therefore this method can enable the widespread adoption of full-duplex techniques to portable devices in addition to infrastructure base-stations.
Trace Typing: An Approach for Evaluating Retrofitted Type Systems (Extended Version)
Venue: arXiv cs.PL 2016
Year: 2016

Recent years have seen growing interest in the retrofitting of type systems onto dynamically-typed programming languages, in order to improve type safety, programmer productivity, or performance. In such cases, type system developers must strike a delicate balance between disallowing certain coding patterns to keep the type system simple, or including them at the expense of additional complexity and effort. Thus far, the process for designing retrofitted type systems has been largely ad hoc, because evaluating multiple variations of a type system on large bodies of existing code is a significant undertaking. We present trace typing: a framework for automatically and quantitatively evaluating variations of a retrofitted type system on large code bases. The trace typing approach involves gathering traces of program executions, inferring types for instances of variables and expressions occurring in a trace, and merging types according to merge strategies that reflect specific (combinations of) choices in the source-level type system design space. We evaluated trace typing through several experiments. We compared several variations of type systems retrofitted onto JavaScript, measuring the number of program locations with type errors in each case on a suite of over fifty thousand lines of JavaScript code. We also used trace typing to validate and guide the design of a new retrofitted type system that enforces fixed object layout for JavaScript objects. Finally, we leveraged the types computed by trace typing to automatically identify tag tests --- dynamic checks that refine a type --- and examined the variety of tests identified.
The Availability and Security Implications of Glue in the Domain Name System
Venue: arXiv cs.CR 2016
Year: 2016

The Domain Name System (DNS) is one of the most fundamental components of the Internet. While glue is widely used and heavily relied on in DNS operations, there is little thinking about the necessity, complexity, and venerability of such prevalent configuration. This work is the first to provide extensive and systematic analysis of DNS glue. It discusses the availability implications of glue and proposes the minimum glue records in terms of availability. It also identifies the security vulnerabilities of glue as well as the limitations of current countermeasures. Measurements show the wide occurrences of glue redundancies and glue vulnerabilities.
Squares that Look Round: Transforming Spherical Images
Venue: arXiv cs.GR 2016
Year: 2016

We propose Möbius transformations as the natural rotation and scaling tools for editing spherical images. As an application we produce spherical Droste images. We obtain other self-similar visual effects using rational functions, elliptic functions, and Schwarz-Christoffel maps.
Movement Coordination in Human-Robot Teams: A Dynamical Systems Approach
Venue: arXiv cs.RO 2016
Year: 2016

In order to be effective teammates, robots need to be able to understand high-level human behavior to recognize, anticipate, and adapt to human motion. We have designed a new approach to enable robots to perceive human group motion in real-time, anticipate future actions, and synthesize their own motion accordingly. We explore this within the context of joint action, where humans and robots move together synchronously. In this paper, we present an anticipation method which takes high-level group behavior into account. We validate the method within a human-robot interaction scenario, where an autonomous mobile robot observes a team of human dancers, and then successfully and contingently coordinates its movements to "join the dance". We compared the results of our anticipation method to move the robot with another method which did not rely on high-level group behavior, and found our method performed better both in terms of more closely synchronizing the robot's motion to the team, and also exhibiting more contingent and fluent motion. These findings suggest that the robot performs better when it has an understanding of high-level group behavior than when it does not. This work will help enable others in the robotics community to build more fluent and adaptable robots in the future.
Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
Venue: arXiv cs.DM 2016
Year: 2016

The celebrated Cheeger's Inequality establishes a bound on the edge expansion of a graph via its spectrum. This inequality is central to a rich spectral theory of graphs, based on studying the eigenvalues and eigenvectors of the adjacency matrix (and other related matrices) of graphs. It has remained open to define a suitable spectral model for hypergraphs whose spectra can be used to estimate various combinatorial properties of the hypergraph. In this paper we introduce a new hypergraph Laplacian operator generalizing the Laplacian matrix of graphs. In particular, the operator is induced by a diffusion process on the hypergraph, such that within each hyperedge, measure flows from vertices having maximum weighted measure to those having minimum. Since the operator is non-linear, we have to exploit other properties of the diffusion process to recover a spectral property concerning the "second eigenvalue" of the resulting Laplacian. Moreover, we show that higher order spectral properties cannot hold in general using the current framework. We consider a stochastic diffusion process, in which each vertex also experiences Brownian noise from outside the system. We show a relationship between the second eigenvalue and the convergence behavior of the process. We show that various hypergraph parameters like multi-way expansion and diameter can be bounded using this operator's spectral properties. Since higher order spectral properties do not hold for the Laplacian operator, we instead use the concept of procedural minimizers to consider higher order Cheeger-like inequalities. For any positive integer $k$, we give a polynomial time algorithm to compute an $O(\log r)$-approximation to the $k$-th procedural minimizer, where $r$ is the maximum cardinality of a hyperedge. We show that this approximation factor is optimal under the SSE hypothesis for constant values of $k$.
Improving abcdSAT by At-Least-One Recently Used Clause Management Strategy
Venue: arXiv cs.LO 2016
Year: 2016

We improve further the 2015 version of abcdSAT by various heuristics such as at-least-one recently used strategy, learnt clause database approximation reduction etc. Based on the requirement of different tracks at the SAT Competition 2016, we develop three versions of abcdSAT: drup, inc and lim, which participate in the competition of main (agile), incremental library and no-limit track, respectively.
Achievable Sum DoF of the K-User MIMO Interference Channel with Delayed CSIT
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers a $K$-user multiple-input-multiple-output (MIMO) interference channel (IC) where 1) the channel state information obtained by the transmitters (CSIT) is completely outdated, and 2) the number of transmit antennas at each transmitter, i.e., $M$, is greater than the number of receive antennas at each user, i.e., $N$. The usefulness of the delayed CSIT was firstly identified in a $K$-phase Retrospective Interference Alignment (RIA) scheme proposed by Maddah-Ali et al for the Multiple-Input-Single-Output Broadcast Channel, but the extension to the MIMO IC is a non-trivial step as each transmitter only has the message intended for the corresponding user. Recently, Abdoli et al focused on a Single-Input-Single-Output IC and solved such bottleneck by inventing a $K$-phase RIA with distributed overheard interference retransmission. In this paper, we propose two $K$-phase RIA schemes suitable for the MIMO IC by generalizing and integrating some key features of both Abdoli's and Maddah-Ali's works. The two schemes jointly yield the best known sum Degrees-of-Freedom (DoF) performance so far. For the case $\frac{M}{N}{\geq}K$, the achieved sum DoF is asymptotically given by $\frac{64}{15}N$ when $K{\to}\infty$.
LSTM-based Mixture-of-Experts for Knowledge-Aware Dialogues
Venue: arXiv cs.AI 2016
Year: 2016

We introduce an LSTM-based method for dynamically integrating several word-prediction experts to obtain a conditional language model which can be good simultaneously at several subtasks. We illustrate this general approach with an application to dialogue where we integrate a neural chat model, good at conversational aspects, with a neural question-answering model, good at retrieving precise information from a knowledge-base, and show how the integration combines the strengths of the independent components. We hope that this focused contribution will attract attention on the benefits of using such mixtures of experts in NLP.
Minimum Power Range Assignment for Symmetric Connectivity in Sensor Networks with two Power Levels
Venue: arXiv cs.DS 2016
Year: 2016

This paper examines the problem of assigning a transmission power to every node of a wireless sensor network. The goal is to minimize the total power consumption while ensuring that the resulting communication graph is connected. We focus on a restricted version of this Range Assignment (RA) problem in which there are two different power levels. We only consider symmetrical transmission links to allow easy integration with low level wireless protocols that typically require bidirectional communication between two neighboring nodes. We introduce a parameterized polynomial time approximation algorithm with a performance ratio arbitrarily close to $π^2/6$. Additionally, we give an almost linear time approximation algorithm with a tight quality bound of $7/4$.
Multiple K Means++ Clustering of Satellite Image Using Hadoop MapReduce and Spark
Venue: arXiv cs.DC 2016
Year: 2016

Clustering of image is one of the important steps of mining satellite images. In our experiment we have simultaneously run multiple K-means algorithms with different initial centroids and values of k in the same iteration of MapReduce jobs. For initialization of initial centroids we have implemented Scalable K-Means++ MapReduce (MR) job [1]. We have also run a validation algorithm of Simplified Silhouette Index [2] for multiple clustering outputs, again in the same iteration of MR jobs. This paper explored the behavior of above mentioned clustering algorithms when run on big data platforms like MapReduce and Spark jobs. Spark has been chosen as it is popular for fast processing particularly where iterations are involved.
ScientoBASE: A Framework and Model for Computing Scholastic Indicators of non-local influence of Journals via Native Data Acquisition algorithms
Venue: arXiv cs.DL 2016
Year: 2016

Defining and measuring internationality as a function of influence diffusion of scientific journals is an open problem. There exists no metric to rank journals based on the extent or scale of internationality. Measuring internationality is qualitative, vague, open to interpretation and is limited by vested interests. With the tremendous increase in the number of journals in various fields and the unflinching desire of academics across the globe to publish in "international" journals, it has become an absolute necessity to evaluate, rank and categorize journals based on internationality. Authors, in the current work have defined internationality as a measure of influence that transcends across geographic boundaries. There are concerns raised by the authors about unethical practices reflected in the process of journal publication whereby scholarly influence of a select few are artificially boosted, primarily by resorting to editorial maneuvres. To counter the impact of such tactics, authors have come up with a new method that defines and measures internationality by eliminating such local effects when computing the influence of journals. A new metric, Non-Local Influence Quotient(NLIQ) is proposed as one such parameter for internationality computation along with another novel metric, Other-Citation Quotient as the complement of the ratio of self-citation and total citation. In addition, SNIP and International Collaboration Ratio are used as two other parameters.
Resource allocation using metaheuristic search
Venue: arXiv cs.NE 2016
Year: 2016

This research is focused on solving problems in the area of software project management using metaheuristic search algorithms and as such is research in the field of search based software engineering. The main aim of this research is to evaluate the performance of different metaheuristic search techniques in resource allocation and scheduling problems that would be typical of software development projects. This paper reports a set of experiments which evaluate the performance of three algorithms, namely simulated annealing, tabu search and genetic algorithms. The experimental results indicate that all of the metaheuristics search techniques can be used to solve problems in resource allocation and scheduling within a software project. Finally, a comparative analysis suggests that overall the genetic algorithm had performed better than simulated annealing and tabu search.
Incremental and Decremental Secret Key Agreement
Venue: arXiv cs.IT 2016
Year: 2016

We study the rate of change of the multivariate mutual information among a set of random variables when some common randomness is added to or removed from a subset. This is formulated more precisely as two new multiterminal secret key agreement problems which ask how one can increase the secrecy capacity efficiently by adding common randomness to a small subset of users, and how one can simplify the source model by removing redundant common randomness that does not contribute to the secrecy capacity. The combinatorial structure has been clarified along with some meaningful open problems.
Statistical mechanics analysis of thresholding 1-bit compressed sensing
Venue: arXiv cs.IT 2016
Year: 2016

The one-bit compressed sensing framework aims to reconstruct a sparse signal by only using the sign information of its linear measurements. To compensate for the loss of scale information, past studies in the area have proposed recovering the signal by imposing an additional constraint on the L2-norm of the signal. Recently, an alternative strategy that captures scale information by introducing a threshold parameter to the quantization process was advanced. In this paper, we analyze the typical behavior of the thresholding 1-bit compressed sensing utilizing the replica method of statistical mechanics, so as to gain an insight for properly setting the threshold value. Our result shows that, fixing the threshold at a constant value yields better performance than varying it randomly when the constant is optimally tuned, statistically. Unfortunately, the optimal threshold value depends on the statistical properties of the target signal, which may not be known in advance. In order to handle this inconvenience, we develop a heuristic that adaptively tunes the threshold parameter based on the frequency of positive (or negative) values in the binary outputs. Numerical experiments show that the heuristic exhibits satisfactory performance while incurring low computational cost.
From Sazonov's Non-Dcpo Natural Domains to Closed Directed-Lub Partial Orders
Venue: arXiv cs.LO 2016
Year: 2016

Normann proved that the domains of the game model of PCF (the domains of sequential functionals) need not be dcpos. Sazonov has defined natural domains for a theory of such incomplete domains. This paper further develops that theory. It defines lub-rules that infer natural lubs from existing natural lubs, and lub-rule classes that describe axiom systems like that of natural domains. There is a canonical proper subcategory of the natural domains, the closed directed lub partial orders (cdlubpo), that corresponds to the complete lub-rule class of all valid lub-rules. Cdlubpos can be completed to restricted dcpos, which are dcpos that retain the data of the incomplete cdlubpo as a subset.
Resource allocation in OFDMA networks with half-duplex and imperfect full-duplex users
Venue: arXiv cs.NI 2016
Year: 2016

Recent studies indicate the feasibility of in-band fullduplex (FD) wireless communications, where a wireless radio transmits and receives simultaneously in the same band. Due to its potential to increase the capacity, analyzing the performance of a cellular network that contains full-duplex devices is crucial. In this paper, we consider maximizing the weighted sum-rate of downlink and uplink of a single cell OFDMA network which consists of an imperfect FD base-station (BS) and a mixture of half-duplex and imperfect full-duplex mobile users. To this end, the joint problem of sub-channel assignment and power allocation is investigated and a two-step solution is proposed. A heuristic algorithm to allocate each sub-channel to a pair of downlink and uplink users with polynomial complexity is presented. The power allocation problem is convexified based on the difference of two concave functions approach, for which an iterative solution is obtained. Simulation results demonstrate that when all the users and the BS are perfect FD nodes the network throughput could be doubled, Otherwise, the performance improvement is limited by the inter-node interference and the self-interference. We also investigate the effect of the self-interference cancellation capability and the percentage of FD users on the network performance in both indoor and outdoor scenarios.
Open Packet Processor: a programmable architecture for wire speed platform-independent stateful in-network processing
Venue: arXiv cs.NI 2016
Year: 2016

This paper aims at contributing to the ongoing debate on how to bring programmability of stateful packet processing tasks inside the network switches, while retaining platform independency. Our proposed approach, named "Open Packet Processor" (OPP), shows the viability (via an hardware prototype relying on commodity HW technologies and operating in a strictly bounded number of clock cycles) of eXtended Finite State Machines (XFSM) as low-level data plane programming abstraction. With the help of examples, including a token bucket and a C4.5 traffic classifier based on a binary tree, we show the ability of OPP to support stateful operation and flow-level feature tracking. Platform independence is accomplished by decoupling the implementation of hardware primitives (registries, conditions, update instructions, forwarding actions, matching facilities) from their usage by an application formally described via an abstract XFSM. We finally discuss limitations and extensions.
Shaping the Future through Innovations: From Medical Imaging to Precision Medicine
Venue: arXiv cs.CV 2016
Year: 2016

Medical images constitute a source of information essential for disease diagnosis, treatment and follow-up. In addition, due to its patient-specific nature, imaging information represents a critical component required for advancing precision medicine into clinical practice. This manuscript describes recently developed technologies for better handling of image information: photorealistic visualization of medical images with Cinematic Rendering, artificial agents for in-depth image understanding, support for minimally invasive procedures, and patient-specific computational models with enhanced predictive power. Throughout the manuscript we will analyze the capabilities of such technologies and extrapolate on their potential impact to advance the quality of medical care, while reducing its cost.