OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Scheme for Interference Mitigation of Coexisting WBANs Using Latin Rectangles
Venue: arXiv cs.NI 2016
Year: 2016

The performance of wireless body area networks (WBANs) may be degraded due to co-channel interference, i.e., when sensors of different coexisting WBANs transmit at the same time-slots using the same channel. In this paper, we exploit the 16 channels available in the 2.4 GHz unlicensed international band of ZIGBEE, and propose a distributed scheme that opts to avoid interference through channel to time-slot hopping based on Latin rectangles, DAIL. In DAIL, each WBAN's coordinator picks a Latin rectangle whose rows are ZIGBEE channels and columns are time-slots of its superframe. Subsequently, it assigns a unique symbol to each sensor; this latter forms a transmission pattern according to distinct positions of its symbol in the rectangle, such that collisions among different transmissions of coexisting WBANs are minimized. We further present an analytical model that derives bounds on the collision probability of each sensor's transmission in the network. In addition, the efficiency of DAIL in interference mitigation has been validated by simulations.
Online Exploration of Rectangular Grids
Venue: arXiv cs.CC 2016
Year: 2016

In this paper, we consider the problem of exploring unknown environments with autonomous agents. We model the environment as a graph with edge weights and analyze the task of visiting all vertices of the graph at least once. The hardness of this task heavily depends on the knowledge and the capabilities of the agent. In our model, the agent sees the whole graph in advance, but does not know the weights of the edges. As soon as it arrives in a vertex, it can see the weights of all the outgoing edges. We consider the special case of two different edge weights $1$ and $k$ and prove that the problem remains hard even in this case. We prove a lower bound of $11/9$ on the competitive ratio of any deterministic strategy for exploring a ladder graph and complement this result by a $4$-competitive algorithm. All of these results hold for undirected graphs. Exploring directed graphs, where the direction of the edges is not known beforehand, seems to be much harder. Here, we prove that a natural greedy strategy has a linear lower bound on the competitive ratio both in ladders and square grids.
Fast Eigenspace Approximation using Random Signals
Venue: arXiv cs.DS 2016
Year: 2016

We focus in this work on the estimation of the first $k$ eigenvectors of any graph Laplacian using filtering of Gaussian random signals. We prove that we only need $k$ such signals to be able to exactly recover as many of the smallest eigenvectors, regardless of the number of nodes in the graph. In addition, we address key issues in implementing the theoretical concepts in practice using accurate approximated methods. We also propose fast algorithms both for eigenspace approximation and for the determination of the $k$th smallest eigenvalue $λ_k$. The latter proves to be extremely efficient under the assumption of locally uniform distribution of the eigenvalue over the spectrum. Finally, we present experiments which show the validity of our method in practice and compare it to state-of-the-art methods for clustering and visualization both on synthetic small-scale datasets and larger real-world problems of millions of nodes. We show that our method allows a better scaling with the number of nodes than all previous methods while achieving an almost perfect reconstruction of the eigenspace formed by the first $k$ eigenvectors.
On the Sum of Linear Coefficients of a Boolean Valued Function
Venue: arXiv cs.CC 2016
Year: 2016

Let $f:\{-1,1\}^{n}\rightarrow \{-1,1\}$ be a Boolean valued function having total degree $d$. Then a conjecture due to Servedio and Gopalan asserts that $\sum_{i=1}^{n}\widehat{f}(i)\leq \sum_{j=1}^{d}\widehat{\text{Maj}}_{d}(j)$ where $\text{Maj}_{d}$ is the majority function on $d$ bits. Here we give some alternative formalisms of this conjecture involving the discrete derivative operators on $f$.
Multi-Way Massive MIMO with Maximum-Ratio Processing and Imperfect CSI
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers a multi-way massive multiple-input multiple-output relaying system, where single-antenna users exchange their information-bearing signals with the help of one relay station equipped with unconventionally many antennas. The relay first estimates the channels to all users through the pilot signals transmitted from them. Then, the relay uses maximum-ratio processing (i.e. maximum-ratio combining in the multiple-access phase and maximum-ratio transmission in the broadcast phase) to process the signals. A rigorous closed-form expression for the spectral efficiency is derived. The effects of the channel estimation error, the channel estimation overhead, the length of the training duration, and the randomness of the user locations are analyzed. We show that by deploying massive antenna arrays at the relay and simple maximum-ratio processing, we can serve many users in the same time-frequency resource, while maintaining a given quality-of-service for each user.
Learning Locomotion Skills Using DeepRL: Does the Choice of Action Space Matter?
Venue: arXiv cs.LG 2016
Year: 2016

The use of deep reinforcement learning allows for high-dimensional state descriptors, but little is known about how the choice of action representation impacts the learning difficulty and the resulting performance. We compare the impact of four different action parameterizations (torques, muscle-activations, target joint angles, and target joint-angle velocities) in terms of learning time, policy robustness, motion quality, and policy query rates. Our results are evaluated on a gait-cycle imitation task for multiple planar articulated figures and multiple gaits. We demonstrate that the local feedback provided by higher-level action parameterizations can significantly impact the learning, robustness, and quality of the resulting policies.
Stochastic Invariants for Probabilistic Termination
Venue: arXiv cs.PL 2016
Year: 2016

Termination is one of the basic liveness properties, and we study the termination problem for probabilistic programs with real-valued variables. Previous works focused on the qualitative problem that asks whether an input program terminates with probability~1 (almost-sure termination). A powerful approach for this qualitative problem is the notion of ranking supermartingales with respect to a given set of invariants. The quantitative problem (probabilistic termination) asks for bounds on the termination probability. A fundamental and conceptual drawback of the existing approaches to address probabilistic termination is that even though the supermartingales consider the probabilistic behavior of the programs, the invariants are obtained completely ignoring the probabilistic aspect. In this work we address the probabilistic termination problem for linear-arithmetic probabilistic programs with nondeterminism. We define the notion of {\em stochastic invariants}, which are constraints along with a probability bound that the constraints hold. We introduce a concept of {\em repulsing supermartingales}. First, we show that repulsing supermartingales can be used to obtain bounds on the probability of the stochastic invariants. Second, we show the effectiveness of repulsing supermartingales in the following three ways: (1)~With a combination of ranking and repulsing supermartingales we can compute lower bounds on the probability of termination; (2)~repulsing supermartingales provide witnesses for refutation of almost-sure termination; and (3)~with a combination of ranking and repulsing supermartingales we can establish persistence properties of probabilistic programs. We also present results on related computational problems and an experimental evaluation of our approach on academic examples.
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness
Venue: arXiv cs.CC 2016
Year: 2016

We prove several results giving new and stronger connections between learning, circuit lower bounds and pseudorandomness. Among other results, we show a generic learning speedup lemma, equivalences between various learning models in the exponential time and subexponential time regimes, a dichotomy between learning and pseudorandomness, consequences of non-trivial learning for circuit lower bounds, Karp-Lipton theorems for probabilistic exponential time, and NC$^1$-hardness for the Minimum Circuit Size Problem.
Black Lives Matter in Wikipedia: Collaboration and Collective Memory around Online Social Movements
Venue: arXiv cs.SI 2016
Year: 2016

Social movements use social computing systems to complement offline mobilizations, but prior literature has focused almost exclusively on movement actors' use of social media. In this paper, we analyze participation and attention to topics connected with the Black Lives Matter movement in the English language version of Wikipedia between 2014 and 2016. Our results point to the use of Wikipedia to (1) intensively document and connect historical and contemporary events, (2) collaboratively migrate activity to support coverage of new events, and (3) dynamically re-appraise pre-existing knowledge in the aftermath of new events. These findings reveal patterns of behavior that complement theories of collective memory and collective action and help explain how social computing systems can encode and retrieve knowledge about social movements as they unfold.
Could freely available articles reduce faculty reliance on library for access? An analysis of items cited by faculty from Singapore Management University
Venue: arXiv cs.DL 2016
Year: 2016

Various studies have attempted to assess the amount of free full text available on the web and recent work have suggested that we are close to the 50% mark for freely available articles (Archambault et al. 2013; Bjork et al. 2010; Jamali and Nabavi 2015). It is natural to wonder if this might reduce researchers' reliance on library subscriptions for access. To do so, we need to determine not just what papers researchers are citing to that are free today, but to estimate if the papers they were citing were freely available at the time they were citing it. We attempt to do so for a sample of citations made by researchers in the Singapore Management University in the field of Economics.
Tighter Hard Instances for PPSZ
Venue: arXiv cs.CC 2016
Year: 2016

We construct uniquely satisfiable $k$-CNF formulas that are hard for the algorithm PPSZ. Firstly, we construct graph-instances on which "weak PPSZ" has savings of at most $(2 + ε) / k$; the saving of an algorithm on an input formula with $n$ variables is the largest $γ$ such that the algorithm succeeds (i.e. finds a satisfying assignment) with probability at least $2^{ - (1 - γ) n}$. Since PPSZ (both weak and strong) is known to have savings of at least $\frac{π^2 + o(1)}{6k}$, this is optimal up to the constant factor. In particular, for $k=3$, our upper bound is $2^{0.333\dots n}$, which is fairly close to the lower bound $2^{0.386\dots n}$ of Hertli [SIAM J. Comput.'14]. We also construct instances based on linear systems over $\mathbb{F}_2$ for which strong PPSZ has savings of at most $O\left(\frac{\log(k)}{k}\right)$. This is only a $\log(k)$ factor away from the optimal bound. Our constructions improve previous savings upper bound of $O\left(\frac{\log^2(k)}{k}\right)$ due to Chen et al. [SODA'13].
Regularized Pel-Recursive Motion Estimation Using Generalized Cross-Validation and Spatial Adaptation
Venue: arXiv cs.CV 2016
Year: 2016

The computation of 2-D optical flow by means of regularized pel-recursive algorithms raises a host of issues, which include the treatment of outliers, motion discontinuities and occlusion among other problems. We propose a new approach which allows us to deal with these issues within a common framework. Our approach is based on the use of a technique called Generalized Cross-Validation to estimate the best regularization scheme for a given pixel. In our model, the regularization parameter is a matrix whose entries can account for diverse sources of error. The estimation of the motion vectors takes into consideration local properties of the image following a spatially adaptive approach where each moving pixel is supposed to have its own regularization matrix. Preliminary experiments indicate that this approach provides robust estimates of the optical flow.
Data Poisoning: Lightweight Soft Fault Injection for Python
Venue: arXiv cs.SE 2016
Year: 2016

This paper introduces and explores the idea of data poisoning, a light-weight peer-architecture technique to inject faults into Python programs. This method requires very small modification to the original program, which facilitates evaluation of sensitivity of systems that are prototyped or modeled in Python. We propose different fault scenarios that can be injected to programs using data poisoning. We use Dijkstra's Self Stabilizing Ring Algorithm to illustrate the approach.
Finite generating sets for reversible gate sets under general conservation laws
Venue: arXiv cs.DM 2016
Year: 2016

It is well-known that the Toffoli gate and the negation gate together yield a universal gate set, in the sense that every permutation of $\{0,1\}^n$ can be implemented as a composition of these gates. Since every bit operation that does not use all of the bits performs an even permutation, we need to use at least one auxiliary bit to perform every permutation, and it is known that one bit is indeed enough. Without auxiliary bits, all even permutations can be implemented. We generalize these results to non-binary logic: For any finite set $A$, a finite gate set can generate all even permutations of $A^n$ for all $n$, without any auxiliary symbols. This directly implies the previously published result that a finite gate set can generate all permutations of $A^n$ when the cardinality of $A$ is odd, and that one auxiliary symbol is necessary and sufficient to obtain all permutations when the cardinality of $A$ is even. We also consider the conservative case, that is, those permutations of $A^n$ that preserve the weight of the input word. The weight is the vector that records how many times each symbol occurs in the word or, more generally, the image of the word under a fixed monoid homomorphism from $A^*$ to a commutative monoid. It turns out that no finite conservative gate set can, for all $n$, implement all conservative even permutations of $A^n$ without auxiliary bits. But we provide a finite gate set that can implement all those conservative permutations that are even within each weight class of $A^n$.
GFA: Exploratory Analysis of Multiple Data Sources with Group Factor Analysis
Venue: arXiv cs.MS 2016
Year: 2016

The R package GFA provides a full pipeline for factor analysis of multiple data sources that are represented as matrices with co-occurring samples. It allows learning dependencies between subsets of the data sources, decomposed into latent factors. The package also implements sparse priors for the factorization, providing interpretable biclusters of the multi-source data
GPU-based Pedestrian Detection for Autonomous Driving
Venue: arXiv cs.CV 2016
Year: 2016

We propose a real-time pedestrian detection system for the embedded Nvidia Tegra X1 GPU-CPU hybrid platform. The pipeline is composed by the following state-of-the-art algorithms: Histogram of Local Binary Patterns (LBP) and Histograms of Oriented Gradients (HOG) features extracted from the input image; Pyramidal Sliding Window technique for candidate generation; and Support Vector Machine (SVM) for classification. Results show a 8x speedup in the target Tegra X1 platform and a better performance/watt ratio than desktop CUDA platforms in study.
A Traversable Fixed Size Small Object Allocator in C++
Venue: arXiv cs.PL 2016
Year: 2016

At the allocation and deallocation of small objects with fixed size, the standard allocator of the runtime system has commonly a worse time performance compared to allocators adapted for a special application field. We propose a memory allocator, originally developed for mesh primitives but also usable for any other small equally sized objects. For a large amount of objects it leads to better results than allocating data with the C ++new instruction and behaves nowhere worse. The proposed synchronization approach for this allocator behaves lock-free in practical scenarios without using machine instructions, such as compare-and-swap. A traversal structure is integrated requiring less memory than using containers such as STL-vectors or lists, but with comparable time performance.
Semantic Information Encoding in One Dimensional Time Domain Signals
Venue: arXiv cs.IT 2016
Year: 2016

A one dimensional time domain analog signal s(t) can be visualized as a trajectory of a moving particle in a force field with one degree of freedom. Then the power of the particle at point t is P(s(t)) = s"(t)s'(t), which is the rate at which kinetic energy is dissipated (assuming the mass of the particle is unit) by the particle in order to create the trajectory or give shape to the signal. Assuming meaning of the signal or the semantic information is in its shape, we can say that P(s(t)) is the rate at which kinetic energy of the particle is dissipated to encode semantic information in s(t) at t. After s(t) is digitized (to make it s[n]) the discrete form P(s[n]) is valid. Considering the sign changes of P(s[n]) it has been shown that in the smallest neighborhood of n, in which n is the middle point, semantic information in s[n] can be encoded in 13 distinct ways. This list is exhaustive. A deterministic finite automaton (DFA) has been designed which can accept any finite length digital signal and therefore collection of all finite length digital signals forms a regular language. The DFA has been generalized to a weighted finite state transducer (WFST), which has been used to identify action potentials in a spike train and also to distinguish two speakers when uttering the same phoneme. It has been shown that in any analog signal semantic information can be encoded at a point in the form of the shape of its infinitesimal neighborhood in 17 distinct ways. The list is exhaustive. A new entropy measure called semantic entropy has been introduced. It has been shown that a signal s(t) is traceable on a piece of paper or in an oscilloscope, only if s"(t) exists on all but at most a finite number of points within any finite interval. This is an essential condition for a signal to be the trajectory of a moving particle.
Self-reducible with easy decision version counting problems admit additive error approximation. Connections to counting complexity, exponential time complexity, and circuit lower bounds
Venue: arXiv cs.CC 2016
Year: 2016

We consider the class of counting problems,i.e. functions in $\#$P, which are self reducible, and have easy decision version, i.e. for every input it is easy to decide if the value of the function $f(x)$ is zero. For example, $\#$independent-sets of all sizes, is such a problem, and one of the hardest of this class, since it is equivalent to $\#$SAT under multiplicative approximation preserving reductions. Using these two powerful properties, self reducibility and easy decision, we prove that all problems/ functions $f$ in this class can be approximated in probabilistic polynomial time within an absolute exponential error $ε\cdot 2^{n'}, \forallε>0$, which for many of those problems (when $n'=n+$constant) implies additive approximation to the fraction $f(x)/2^n$. (Where $n'$ is the amount of non-determinism of some associated NPTM). Moreover we show that for all these problems we can have multiplicative error to the value $f(x)$, of any desired accuracy (i.e. a RAS), in time of order $2^{2n'/3}poly(n)$, which is strictly smaller than exhaustive search. We also show that $f(x)<g(x)$ can be decided deterministically in time $g(x)poly(n), \forall g$. Finally we show that the Circuit Acceptance Probability Problem, which is related to derandomization and circuit lower bounds, can be solved with high probability and in polynomial time, for the family of all circuits for which the problems of counting either satisfying or unsatisfying assignments belong to TotP (which is the Karp-closure of self reducible problems with easy decision version).
Beyond Fine Tuning: A Modular Approach to Learning on Small Data
Venue: arXiv cs.LG 2016
Year: 2016

In this paper we present a technique to train neural network models on small amounts of data. Current methods for training neural networks on small amounts of rich data typically rely on strategies such as fine-tuning a pre-trained neural network or the use of domain-specific hand-engineered features. Here we take the approach of treating network layers, or entire networks, as modules and combine pre-trained modules with untrained modules, to learn the shift in distributions between data sets. The central impact of using a modular approach comes from adding new representations to a network, as opposed to replacing representations via fine-tuning. Using this technique, we are able surpass results using standard fine-tuning transfer learning approaches, and we are also able to significantly increase performance over such approaches when using smaller amounts of data.
Neuro-Symbolic Program Synthesis
Venue: arXiv cs.AI 2016
Year: 2016

Recent years have seen the proposal of a number of neural architectures for the problem of Program Induction. Given a set of input-output examples, these architectures are able to learn mappings that generalize to new test inputs. While achieving impressive results, these approaches have a number of important limitations: (a) they are computationally expensive and hard to train, (b) a model has to be trained for each task (program) separately, and (c) it is hard to interpret or verify the correctness of the learnt mapping (as it is defined by a neural network). In this paper, we propose a novel technique, Neuro-Symbolic Program Synthesis, to overcome the above-mentioned problems. Once trained, our approach can automatically construct computer programs in a domain-specific language that are consistent with a set of input-output examples provided at test time. Our method is based on two novel neural modules. The first module, called the cross correlation I/O network, given a set of input-output examples, produces a continuous representation of the set of I/O examples. The second module, the Recursive-Reverse-Recursive Neural Network (R3NN), given the continuous representation of the examples, synthesizes a program by incrementally expanding partial programs. We demonstrate the effectiveness of our approach by applying it to the rich and complex domain of regular expression based string transformations. Experiments show that the R3NN model is not only able to construct programs from new input-output examples, but it is also able to construct new programs for tasks that it had never observed before during training.
Privacy Preserving PageRank Algorithm By Using Secure Multi-Party Computation
Venue: arXiv cs.CR 2016
Year: 2016

In this work, we study the problem of privacy preserving computation on PageRank algorithm. The idea is to enforce the secure multi party computation of the algorithm iteratively using homomorphic encryption based on Paillier scheme. In the proposed PageRank computation, a user encrypt its own graph data using asymmetric encryption method, sends the data set into different parties in a privacy-preserving manner. Each party computes its own encrypted entity, but learns nothing about the data at other parties.