OpenRaiser/Intern-Atlas huggingface dataset:
On Network Simplification for Gaussian Half-Duplex Diamond Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates the simplification problem in Gaussian Half-Duplex (HD) diamond networks. The goal is to answer the following question: what is the minimum (worst-case) fraction of the total HD capacity that one can always achieve by smartly selecting a subset of $k$ relays, out of the $N$ possible ones? We make progress on this problem for $k=1$ and $k=2$ and show that for $N=k+1, \ k \in \{1,2\}$ at least $\frac{k}{k+1}$ of the total HD capacity is always {approximately (i.e., up to a constant gap)} achieved. Interestingly, and differently from the Full-Duplex (FD) case, the ratio in HD depends on $N$, and decreases as $N$ increases. For all values of $N$ and $k$ for which we derive worst case fractions, we also show these to be {approximately} tight. This is accomplished by presenting $N$-relay Gaussian HD diamond networks for which the best $k$-relay subnetwork has {an approximate} HD capacity equal to the worst-case fraction of the total {approximate} HD capacity. Moreover, we provide additional comparisons between the performance of this simplification problem for HD and FD networks, which highlight their different natures.
Polynomial Time corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
Venue: arXiv cs.CC 2016
Year: 2016

We provide an implicit characterization of polynomial time computation in terms of ordinary differential equations: we characterize the class $\operatorname{PTIME}$ of languages computable in polynomial time in terms of differential equations with polynomial right-hand side. This result gives a purely continuous (time and space) elegant and simple characterization of $\operatorname{PTIME}$. This is the first time such classes are characterized using only ordinary differential equations. Our characterization extends to functions computable in polynomial time over the reals in the sense of computable analysis. This extends to deterministic complexity classes above polynomial time. This may provide a new perspective on classical complexity, by giving a way to define complexity classes, like $\operatorname{PTIME}$, in a very simple way, without any reference to a notion of (discrete) machine. This may also provide ways to state classical questions about computational complexity via ordinary differential equations, i.e.~by using the framework of analysis.
RepEx: A Flexible Framework for Scalable Replica Exchange Molecular Dynamics Simulations
Venue: arXiv cs.DC 2016
Year: 2016

Replica Exchange (RE) simulations have emerged as an important algorithmic tool for the molecular sciences. RE simulations involve the concurrent execution of independent simulations which infrequently interact and exchange information. The next set of simulation parameters are based upon the outcome of the exchanges. Typically RE functionality is integrated into the molecular simulation software package. A primary motivation of the tight integration of RE functionality with simulation codes has been performance. This is limiting at multiple levels. First, advances in the RE methodology are tied to the molecular simulation code. Consequently these advances remain confined to the molecular simulation code for which they were developed. Second, it is difficult to extend or experiment with novel RE algorithms, since expertise in the molecular simulation code is typically required. In this paper, we propose the RepEx framework which address these aforementioned shortcomings of existing approaches, while striking the balance between flexibility (any RE scheme) and scalability (tens of thousands of replicas) over a diverse range of platforms. RepEx is designed to use a pilot-job based runtime system and support diverse RE Patterns and Execution Modes. RE Patterns are concerned with synchronization mechanisms in RE simulation, and Execution Modes with spatial and temporal mapping of workload to the CPU cores. We discuss how the design and implementation yield the following primary contributions of the RepEx framework: (i) its ability to support different RE schemes independent of molecular simulation codes, (ii) provide the ability to execute different exchange schemes and replica counts independent of the specific availability of resources, (iii) provide a runtime system that has first-class support for task-level parallelism, and (iv) required scalability along multiple dimensions.
Detecting Temporally Consistent Objects in Videos through Object Class Label Propagation
Venue: arXiv cs.CV 2016
Year: 2016

Object proposals for detecting moving or static video objects need to address issues such as speed, memory complexity and temporal consistency. We propose an efficient Video Object Proposal (VOP) generation method and show its efficacy in learning a better video object detector. A deep-learning based video object detector learned using the proposed VOP achieves state-of-the-art detection performance on the Youtube-Objects dataset. We further propose a clustering of VOPs which can efficiently be used for detecting objects in video in a streaming fashion. As opposed to applying per-frame convolutional neural network (CNN) based object detection, our proposed method called Objects in Video Enabler thRough LAbel Propagation (OVERLAP) needs to classify only a small fraction of all candidate proposals in every video frame through streaming clustering of object proposals and class-label propagation. Source code will be made available soon.
RGB-D-based Action Recognition Datasets: A Survey
Venue: arXiv cs.CV 2016
Year: 2016

Human action recognition from RGB-D (Red, Green, Blue and Depth) data has attracted increasing attention since the first work reported in 2010. Over this period, many benchmark datasets have been created to facilitate the development and evaluation of new algorithms. This raises the question of which dataset to select and how to use it in providing a fair and objective comparative evaluation against state-of-the-art methods. To address this issue, this paper provides a comprehensive review of the most commonly used action recognition related RGB-D video datasets, including 27 single-view datasets, 10 multi-view datasets, and 7 multi-person datasets. The detailed information and analysis of these datasets is a useful resource in guiding insightful selection of datasets for future research. In addition, the issues with current algorithm evaluation vis-á-vis limitations of the available datasets and evaluation protocols are also highlighted; resulting in a number of recommendations for collection of new datasets and use of evaluation protocols.
Encoding Semiconstrained Systems
Venue: arXiv cs.IT 2016
Year: 2016

Semiconstrained systems were recently suggested as a generalization of constrained systems, commonly used in communication and data-storage applications that require certain offending subsequences be avoided. In an attempt to apply techniques from constrained systems, we study sequences of constrained systems that are contained in, or contain, a given semiconstrained system, while approaching its capacity. In the case of contained systems we describe to such sequences resulting in constant-to-constant bit-rate block encoders and sliding-block encoders. Surprisingly, in the case of containing systems we show that a "generic" semiconstrained system is never contained in a proper fully-constrained system.
Fluid Dynamics Modeling : The Numerical Solution Of 2D Navier Hyperbolic Equations
Venue: arXiv cs.NA 2016
Year: 2016

In the following paper we will consider Navier-Stokes problem and it's interpretation by hyperbolic waves, focusing on wave propagation. We will begin with solution for linear waves, then present problem for non-linear waves. Later we will derive for numerical solution using PDE's. Also we will design a Matlab program to solve and simulate wave propagation.
Sampling-Based Query Re-Optimization
Venue: arXiv cs.DB 2016
Year: 2016

Despite of decades of work, query optimizers still make mistakes on "difficult" queries because of bad cardinality estimates, often due to the interaction of multiple predicates and correlations in the data. In this paper, we propose a low-cost post-processing step that can take a plan produced by the optimizer, detect when it is likely to have made such a mistake, and take steps to fix it. Specifically, our solution is a sampling-based iterative procedure that requires almost no changes to the original query optimizer or query evaluation mechanism of the system. We show that this indeed imposes low overhead and catches cases where three widely used optimizers (PostgreSQL and two commercial systems) make large errors.
The Impact of Unlicensed Access on Small-Cell Resource Allocation
Venue: arXiv cs.IT 2016
Year: 2016

Small cells deployed in licensed spectrum and unlicensed access via WiFi provide different ways of expanding wireless services to low mobility users. That reduces the demand for conventional macro-cellular networks, which are better suited for wide-area mobile coverage. The mix of these technologies seen in practice depends in part on the decisions made by wireless service providers that seek to maximize revenue, and allocations of licensed and unlicensed spectrum by regulators. To understand these interactions we present a model in which a service provider allocates available licensed spectrum across two separate bands, one for macro- and one for small-cells, in order to serve two types of users: mobile and fixed. We assume a service model in which the providers can charge a (different) price per unit rate for each type of service (macro- or small-cell); unlicensed access is free. With this setup we study how the addition of unlicensed spectrum affects prices and the optimal allocation of bandwidth across macro-/small-cells. We also characterize the optimal fraction of unlicensed spectrum when new bandwidth becomes available.
HyBIS: Windows Guest Protection through Advanced Memory Introspection
Venue: arXiv cs.OS 2016
Year: 2016

Effectively protecting the Windows OS is a challenging task, since most implementation details are not publicly known. Windows has always been the main target of malwares that have exploited numerous bugs and vulnerabilities. Recent trusted boot and additional integrity checks have rendered the Windows OS less vulnerable to kernel-level rootkits. Nevertheless, guest Windows Virtual Machines are becoming an increasingly interesting attack target. In this work we introduce and analyze a novel Hypervisor-Based Introspection System (HyBIS) we developed for protecting Windows OSes from malware and rootkits. The HyBIS architecture is motivated and detailed, while targeted experimental results show its effectiveness. Comparison with related work highlights main HyBIS advantages such as: effective semantic introspection, support for 64-bit architectures and for latest Windows (8.x and 10), advanced malware disabling capabilities. We believe the research effort reported here will pave the way to further advances in the security of Windows OSes.
A Lattice Coding Scheme for Secret Key Generation from Gaussian Markov Tree Sources
Venue: arXiv cs.IT 2016
Year: 2016

In this article, we study the problem of secret key generation in the multiterminal source model, where the terminals have access to correlated Gaussian sources. We assume that the sources form a Markov chain on a tree. We give a nested lattice-based key generation scheme whose computational complexity is polynomial in the number, N , of independent and identically distributed samples observed by each source. We also compute the achievable secret key rate and give a class of examples where our scheme is optimal in the fine quantization limit. However, we also give examples that show that our scheme is not always optimal in the limit of fine quantization.
Asymptotic Optimality of Massive MIMO Systems Using Densely Spaced Transmit Antennas
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates the performance of a massive multiple-input multiple-output (MIMO) system that uses a large transmit antenna array with antenna elements spaced densely. Under the assumption of idealized uniform linear antenna arrays without mutual coupling, precoded quadrature phase-shift keying (QPSK) transmission is proved to achieve the channel capacity of the massive MIMO system when the transmit antenna separation tends to zero. This asymptotic optimality is analogous to that of QPSK faster-than-Nyquist signaling.
Modulation Format Independent Joint Polarization and Phase Tracking for Coherent Receivers
Venue: arXiv cs.IT 2016
Year: 2016

The state of polarization and the carrier phase drift dynamically during transmission in a random fashion in coherent optical fiber communications. The typical digital signal processing solution to mitigate these impairments consists of two separate blocks that track each phenomenon independently. Such algorithms have been developed without taking into account mathematical models describing the impairments. We study a blind, model-based tracking algorithm to compensate for these impairments. The algorithm dynamically recovers the carrier phase and state of polarization jointly for an arbitrary modulation format. Simulation results show the effectiveness of the proposed algorithm, having a fast convergence rate and an excellent tolerance to phase noise and dynamic drift of the polarization. The computational complexity of the algorithm is lower compared to state-of-the-art algorithms at similar or better performance, which makes it a strong candidate for future optical systems.
The Singularity Controversy, Part I: Lessons Learned and Open Questions: Conclusions from the Battle on the Legitimacy of the Debate
Venue: arXiv cs.AI 2016
Year: 2016

This report seeks to inform policy makers on the nature and the merit of the arguments for and against the concerns associated with a potential technological singularity. Part I describes the lessons learned from our investigation of the subject, separating the argu-ments of merit from the fallacies and misconceptions that confuse the debate and undermine its rational resolution.
Depth and Reflection Total Variation for Single Image Dehazing
Venue: arXiv cs.CV 2016
Year: 2016

Haze removal has been a very challenging problem due to its ill-posedness, which is more ill-posed if the input data is only a single hazy image. In this paper, we present a new approach for removing haze from a single input image. The proposed method combines the model widely used to describe the formation of a haze image with the assumption in Retinex that an image is the product of the illumination and the reflection. We assume that the depth and reflection functions are spatially piecewise smooth in the model, where the total variation is used for the regularization. The proposed model is defined as a constrained optimization problem, which is solved by an alternating minimization scheme and the fast gradient projection algorithm. Some theoretic analyses are given for the proposed model and algorithm. Finally, numerical examples are presented to demonstrate that our method can restore vivid and contrastive hazy images effectively.
Multi-Library Coded Caching
Venue: arXiv cs.IT 2016
Year: 2016

We study the problem of coded caching when the server has access to several libraries and each user makes independent requests from every library. The single-library scenario has been well studied and it has been proved that coded caching can significantly improve the delivery rate compared to uncoded caching. In this work we show that when all the libraries have the same number of files, memory-sharing is optimal and the delivery rate cannot be improved via coding across files from different libraries. In this setting, the optimal memory-sharing strategy is one that divides the cache of each user proportional to the size of the files in different libraries. As for the general case, when the number of files in different libraries are arbitrary, we propose an inner-bound based on memory-sharing and an outer-bound based on concatenation of files from different libraries.
The International Postal Network and Other Global Flows As Proxies for National Wellbeing
Venue: arXiv cs.CY 2016
Year: 2016

The digital exhaust left by flows of physical and digital commodities provides a rich measure of the nature, strength and significance of relationships between countries in the global network. With this work, we examine how these traces and the network structure can reveal the socioeconomic profile of different countries. We take into account multiple international networks of physical and digital flows, including the previously unexplored international postal network. By measuring the position of each country in the Trade, Postal, Migration, International Flights, IP and Digital Communications networks, we are able to build proxies for a number of crucial socioeconomic indicators such as GDP per capita and the Human Development Index ranking along with twelve other indicators used as benchmarks of national wellbeing by the United Nations and other international organisations. In this context, we have also proposed and evaluated a global connectivity degree measure applying multiplex theory across the six networks that accounts for the strength of relationships between countries. We conclude with a multiplex community analysis of the global flow networks, showing how countries with shared community membership over multiple networks have similar socioeconomic profiles. Combining multiple flow data sources into global multiplex networks can help understand the forces which drive economic activity on a global level. Such an ability to infer proxy indicators in a context of incomplete information is extremely timely in light of recent discussions on measurement of indicators relevant to the Sustainable Development Goals.
Comparing the Bit-MAP and Block-MAP Decoding Thresholds of Reed-Muller Codes on BMS Channels
Venue: arXiv cs.IT 2016
Year: 2016

The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as $N^{-δ}$, for some $δ>0$. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.
Bitwise Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

Based on the assumption that there exists a neural network that efficiently represents a set of Boolean functions between all binary inputs and outputs, we propose a process for developing and deploying neural networks whose weight parameters, bias terms, input, and intermediate hidden layer output signals, are all binary-valued, and require only basic bit logic for the feedforward pass. The proposed Bitwise Neural Network (BNN) is especially suitable for resource-constrained environments, since it replaces either floating or fixed-point arithmetic with significantly more efficient bitwise operations. Hence, the BNN requires for less spatial complexity, less memory bandwidth, and less power consumption in hardware. In order to design such networks, we propose to add a few training schemes, such as weight compression and noisy backpropagation, which result in a bitwise network that performs almost as well as its corresponding real-valued network. We test the proposed network on the MNIST dataset, represented using binary features, and show that BNNs result in competitive performance while offering dramatic computational savings.
Why Do Urban Legends Go Viral?
Venue: arXiv cs.CL 2016
Year: 2016

Urban legends are a genre of modern folklore, consisting of stories about rare and exceptional events, just plausible enough to be believed, which tend to propagate inexorably across communities. In our view, while urban legends represent a form of "sticky" deceptive text, they are marked by a tension between the credible and incredible. They should be credible like a news article and incredible like a fairy tale to go viral. In particular we will focus on the idea that urban legends should mimic the details of news (who, where, when) to be credible, while they should be emotional and readable like a fairy tale to be catchy and memorable. Using NLP tools we will provide a quantitative analysis of these prototypical characteristics. We also lay out some machine learning experiments showing that it is possible to recognize an urban legend using just these simple features.
An Iterative Algorithm for Computing the Optimal Exponent of Correct Decoding Probability for Rates below the Rate Distortion Function
Venue: arXiv cs.IT 2016
Year: 2016

The form of Dueck and Körner's exponent function for correct decoding probability for discrete memoryless channels at rates above the capacity is similar to the form of Csiszár and Körner's exponent function for correct decoding probability in lossy source coding for discrete memoryless sources at rates below the rate distortion function. We recently gave a new algorithm for computing Dueck and Körner's exponent. In this paper, we give an algorithm for computing Csiszár and Körner's exponent. The proposed algorithm can be also used to compute cutoff rate and the rate distortion function.
A bifibrational reconstruction of Lawvere's presheaf hyperdoctrine
Venue: arXiv cs.LO 2016
Year: 2016

Combining insights from the study of type refinement systems and of monoidal closed chiralities, we show how to reconstruct Lawvere's hyperdoctrine of presheaves using a full and faithful embedding into a monoidal closed bifibration living now over the compact closed category of small categories and distributors. Besides revealing dualities which are not immediately apparent in the traditional presentation of the presheaf hyperdoctrine, this reconstruction leads us to an axiomatic treatment of directed equality predicates (modelled by hom presheaves), realizing a vision initially set out by Lawvere (1970). It also leads to a simple calculus of string diagrams (representing presheaves) that is highly reminiscent of C. S. Peirce's existential graphs for predicate logic, refining an earlier interpretation of existential graphs in terms of Boolean hyperdoctrines by Brady and Trimble. Finally, we illustrate how this work extends to a bifibrational setting a number of fundamental ideas of linear logic.