OpenRaiser/Intern-Atlas huggingface dataset:
Channel Equalization Using Multilayer Perceptron Networks
Venue: arXiv cs.NE 2016
Year: 2016

In most digital communication systems, bandwidth limited channel along with multipath propagation causes ISI (Inter Symbol Interference) to occur. This phenomenon causes distortion of the given transmitted symbol due to other transmitted symbols. With the help of equalization ISI can be reduced. This paper presents a solution to the ISI problem by performing blind equalization using ANN (Artificial Neural Networks). The simulated network is a multilayer feedforward Perceptron ANN, which has been trained by utilizing the error back-propagation algorithm. The weights of the network are updated in accordance with training of the network. This paper presents a very effective method for blind channel equalization, being more efficient than the pre-existing algorithms. The obtained results show a visible reduction in the noise content.
A Direct Elliptic Solver Based on Hierarchically Low-rank Schur Complements
Venue: arXiv cs.NA 2016
Year: 2016

A parallel fast direct solver for rank-compressible block tridiagonal linear systems is presented. Algorithmic synergies between Cyclic Reduction and Hierarchical matrix arithmetic operations result in a solver with $O(N \log^2 N)$ arithmetic complexity and $O(N \log N)$ memory footprint. We provide a baseline for performance and applicability by comparing with well known implementations of the $\mathcal{H}$-LU factorization and algebraic multigrid with a parallel implementation that leverages the concurrency features of the method. Numerical experiments reveal that this method is comparable with other fast direct solvers based on Hierarchical Matrices such as $\mathcal{H}$-LU and that it can tackle problems where algebraic multigrid fails to converge.
Safe, Remote-Access Swarm Robotics Research on the Robotarium
Venue: arXiv cs.RO 2016
Year: 2016

This paper describes the development of the Robotarium -- a remotely accessible, multi-robot research facility. The impetus behind the Robotarium is that multi-robot testbeds constitute an integral and essential part of the multi-agent research cycle, yet they are expensive, complex, and time-consuming to develop, operate, and maintain. These resource constraints, in turn, limit access for large groups of researchers and students, which is what the Robotarium is remedying by providing users with remote access to a state-of-the-art multi-robot test facility. This paper details the design and operation of the Robotarium as well as connects these to the particular considerations one must take when making complex hardware remotely accessible. In particular, safety must be built in already at the design phase without overly constraining which coordinated control programs the users can upload and execute, which calls for minimally invasive safety routines with provable performance guarantees.
On Clustered Statistical MIMO Millimeter Wave Channel Simulation
Venue: arXiv cs.IT 2016
Year: 2016

The use of mmWave frequencies is one of the key strategies to achieve the fascinating 1000x increase in the capacity of future 5G wireless systems. While for traditional sub-6 GHz cellular frequencies several well-developed statistical channel models are available for system simulation, similar tools are not available for mmWave frequencies, thus preventing a fair comparison of independently developed transmission and reception schemes. In this paper we provide a simple albeit accurate statistical procedure for the generation of a clustered MIMO channel model operating at mmWaves, for both the cases of slowly and rapidly time-varying channels. Matlab scripts for channel generation are also provided, along with an example of their use.
A New Learning Method for Inference Accuracy, Core Occupation, and Performance Co-optimization on TrueNorth Chip
Venue: arXiv cs.NE 2016
Year: 2016

IBM TrueNorth chip uses digital spikes to perform neuromorphic computing and achieves ultrahigh execution parallelism and power efficiency. However, in TrueNorth chip, low quantization resolution of the synaptic weights and spikes significantly limits the inference (e.g., classification) accuracy of the deployed neural network model. Existing workaround, i.e., averaging the results over multiple copies instantiated in spatial and temporal domains, rapidly exhausts the hardware resources and slows down the computation. In this work, we propose a novel learning method on TrueNorth platform that constrains the random variance of each computation copy and reduces the number of needed copies. Compared to the existing learning method, our method can achieve up to 68.8% reduction of the required neuro-synaptic cores or 6.5X speedup, with even slightly improved inference accuracy.
Approximating (Unweighted) Tree Augmentation via Lift-and-Project (Part 0: $1.8+ε$ approximation for (Unweighted) TAP)
Venue: arXiv cs.DS 2016
Year: 2016

We study the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum of Squares) system. We prove an approximation guarantee of ($1.8+ε$) relative to an SDP relaxation, which matches the combinatorial approximation guarantee of Even, Feldman, Kortsarz and Nutov in ACM TALG (2009), where $ε>0$ is a constant. We generalize the combinatorial analysis of integral solutions of Even, et al., to fractional solutions by identifying some properties of fractional solutions of the Lasserre system via the decomposition result of Rothvoß (arXiv:1111.5473, 2011) and Karlin, Mathieu and Nguyen (IPCO 2011).
Topic Model Based Multi-Label Classification from the Crowd
Venue: arXiv cs.LG 2016
Year: 2016

Multi-label classification is a common supervised machine learning problem where each instance is associated with multiple classes. The key challenge in this problem is learning the correlations between the classes. An additional challenge arises when the labels of the training instances are provided by noisy, heterogeneous crowdworkers with unknown qualities. We first assume labels from a perfect source and propose a novel topic model where the present as well as the absent classes generate the latent topics and hence the words. We non-trivially extend our topic model to the scenario where the labels are provided by noisy crowdworkers. Extensive experimentation on real world datasets reveals the superior performance of the proposed model. The proposed model learns the qualities of the annotators as well, even with minimal training data.
Polarity and Monopolarity of $3$-colourable comparability graphs
Venue: arXiv cs.CC 2016
Year: 2016

We sharpen the result that polarity and monopolarity are NP-complete problems by showing that they remain NP-complete if the input graph is restricted to be a $3$-colourable comparability graph. We start by presenting a construction reducing $1$-$3$-SAT to monopolarity of $3$-colourable comparability graphs. Then we show that polarity is at least as hard as monopolarity for input graphs restricted to a fixed disjoint-union-closed class. We conclude the paper by stating that both polarity and monopolarity of $3$-colourable comparability graphs are NP-complete problems.
Dual Link Algorithm for the Weighted Sum Rate Maximization in MIMO Interference Channels
Venue: arXiv cs.IT 2016
Year: 2016

MIMO interference network optimization is important for increasingly crowded wireless communication networks. We provide a new algorithm, named Dual Link algorithm, for the classic problem of weighted sum-rate maximization for MIMO multiaccess channels (MAC), broadcast channels (BC), and general MIMO interference channels with Gaussian input and a total power constraint. For MIMO MAC/BC, the algorithm finds optimal signals to achieve the capacity region boundary. For interference channels with Gaussian input assumption, two of the previous state-of-the-art algorithms are the WMMSE algorithm and the polite water-filling (PWF) algorithm. The WMMSE algorithm is provably convergent, while the PWF algorithm takes the advantage of the optimal transmit signal structure and converges the fastest in most situations but is not guaranteed to converge in all situations. It is highly desirable to design an algorithm that has the advantages of both algorithms. The dual link algorithm is such an algorithm. Its fast and guaranteed convergence is important to distributed implementation and time varying channels. In addition, the technique and a scaling invariance property used in the convergence proof may find applications in other non-convex problems in communication networks.
Verification of Hierarchical Artifact Systems
Venue: arXiv cs.DB 2016
Year: 2016

Data-driven workflows, of which IBM's Business Artifacts are a prime exponent, have been successfully deployed in practice, adopted in industrial standards, and have spawned a rich body of research in academia, focused primarily on static analysis. The present work represents a significant advance on the problem of artifact verification, by considering a much richer and more realistic model than in previous work, incorporating core elements of IBM's successful Guard-Stage-Milestone model. In particular, the model features task hierarchy, concurrency, and richer artifact data. It also allows database key and foreign key dependencies, as well as arithmetic constraints. The results show decidability of verification and establish its complexity, making use of novel techniques including a hierarchy of Vector Addition Systems and a variant of quantifier elimination tailored to our context.
Direct Visual Odometry using Bit-Planes
Venue: arXiv cs.RO 2016
Year: 2016

Feature descriptors, such as SIFT and ORB, are well-known for their robustness to illumination changes, which has made them popular for feature-based VSLAM\@. However, in degraded imaging conditions such as low light, low texture, blur and specular reflections, feature extraction is often unreliable. In contrast, direct VSLAM methods which estimate the camera pose by minimizing the photometric error using raw pixel intensities are often more robust to low textured environments and blur. Nonetheless, at the core of direct VSLAM is the reliance on a consistent photometric appearance across images, otherwise known as the brightness constancy assumption. Unfortunately, brightness constancy seldom holds in real world applications. In this work, we overcome brightness constancy by incorporating feature descriptors into a direct visual odometry framework. This combination results in an efficient algorithm that combines the strength of both feature-based algorithms and direct methods. Namely, we achieve robustness to arbitrary photometric variations while operating in low-textured and poorly lit environments. Our approach utilizes an efficient binary descriptor, which we call Bit-Planes, and show how it can be used in the gradient-based optimization required by direct methods. Moreover, we show that the squared Euclidean distance between Bit-Planes is equivalent to the Hamming distance. Hence, the descriptor may be used in least squares optimization without sacrificing its photometric invariance. Finally, we present empirical results that demonstrate the robustness of the approach in poorly lit underground environments.
Optimal Parameter Settings for the $(1+(λ, λ))$ Genetic Algorithm
Venue: arXiv cs.NE 2016
Year: 2016

The $(1+(λ,λ))$ genetic algorithm is one of the few algorithms for which a super-constant speed-up through the use of crossover could be proven. So far, this algorithm has been used with parameters based also on intuitive considerations. In this work, we rigorously regard the whole parameter space and show that the asymptotic time complexity proven by Doerr and Doerr (GECCO 2015) for the intuitive choice is best possible among all settings for population size, mutation probability, and crossover bias.
Distinguishing between Personal Preferences and Social Influence in Online Activity Feeds
Venue: arXiv cs.SI 2016
Year: 2016

Many online social networks thrive on automatic sharing of friends' activities to a user through activity feeds, which may influence the user's next actions. However, identifying such social influence is tricky because these activities are simultaneously impacted by influence and homophily. We propose a statistical procedure that uses commonly available network and observational data about people's actions to estimate the extent of copy-influence---mimicking others' actions that appear in a feed. We assume that non-friends don't influence users; thus, comparing how a user's activity correlates with friends versus non-friends who have similar preferences can help tease out the effect of copy-influence. Experiments on datasets from multiple social networks show that estimates that don't account for homophily overestimate copy-influence by varying, often large amounts. Further, copy-influence estimates fall below 1% of total actions in all networks: most people, and almost all actions, are not affected by the feed. Our results question common perceptions around the extent of copy-influence in online social networks and suggest improvements to diffusion and recommendation models.
C3PO: Computation Congestion Control (PrOactive) - an algorithm for dynamic diffusion of ephemeral in-network services
Venue: arXiv cs.NI 2016
Year: 2016

There is an obvious trend that more and more data and computation are migrating into networks nowadays. Combining mature virtualization technologies with service-centric net- working, we are entering into an era where countless services reside in an ISP network to provide low-latency access. Such services are often computation intensive and are dynamically created and destroyed on demands everywhere in the network to perform various tasks. Consequently, these ephemeral in-network services introduce a new type of congestion in the network which we refer to as "computation congestion". The service load need to be effectively distributed on different nodes in order to maintain the funtionality and responsiveness of the network, which calls for a new design rather than reusing the centralised scheduler designed for cloud-based services. In this paper, we study both passive and proactive control strategies, based on the proactive control we further propose a fully distributed solution which is low complexity, adaptive, and responsive to network dynamics.
Deep Cross Residual Learning for Multitask Visual Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Residual learning has recently surfaced as an effective means of constructing very deep neural networks for object recognition. However, current incarnations of residual networks do not allow for the modeling and integration of complex relations between closely coupled recognition tasks or across domains. Such problems are often encountered in multimedia applications involving large-scale content recognition. We propose a novel extension of residual learning for deep networks that enables intuitive learning across multiple related tasks using cross-connections called cross-residuals. These cross-residuals connections can be viewed as a form of in-network regularization and enables greater network generalization. We show how cross-residual learning (CRL) can be integrated in multitask networks to jointly train and detect visual concepts across several tasks. We present a single multitask cross-residual network with >40% less parameters that is able to achieve competitive, or even better, detection performance on a visual sentiment concept detection problem normally requiring multiple specialized single-task networks. The resulting multitask cross-residual network also achieves better detection performance by about 10.4% over a standard multitask residual network without cross-residuals with even a small amount of cross-task weighting.
Designing robust watermark barcodes for multiplex long-read sequencing
Venue: arXiv cs.OH 2016
Year: 2016

A method for designing sequencing barcodes that can withstand a large number of insertion, deletion and substitution errors and are suitable for use in multiplex single-molecule real-time sequencing is presented. The manuscript focuses on the design of barcodes for full-length single-pass reads, impaired by challenging error rates in the order of 11%. To the authors' knowledge, this is the first method to specifically address this problem without requiring upstream quality improvement. The proposed barcodes can multiplex hundreds or thousands of samples while achieving sample misassignment probabilities as low as $10^{-7}$, and are designed to be compatible with chemical constraints imposed by the sequencing process. Software for constructing watermark barcode sets and demultiplexing barcoded reads, together with example sets of barcodes and synthetic barcoded reads, are freely available at www.cifasis-conicet.gov.ar/ezpeleta/NS-watermark.
Heavy hitters via cluster-preserving clustering
Venue: arXiv cs.DS 2016
Year: 2016

In turnstile $\ell_p$ $\varepsilon$-heavy hitters, one maintains a high-dimensional $x\in\mathbb{R}^n$ subject to $\texttt{update}(i,Δ)$ causing $x_i\leftarrow x_i + Δ$, where $i\in[n]$, $Δ\in\mathbb{R}$. Upon receiving a query, the goal is to report a small list $L\subset[n]$, $|L| = O(1/\varepsilon^p)$, containing every "heavy hitter" $i\in[n]$ with $|x_i| \ge \varepsilon \|x_{\overline{1/\varepsilon^p}}\|_p$, where $x_{\overline{k}}$ denotes the vector obtained by zeroing out the largest $k$ entries of $x$ in magnitude. For any $p\in(0,2]$ the CountSketch solves $\ell_p$ heavy hitters using $O(\varepsilon^{-p}\log n)$ words of space with $O(\log n)$ update time, $O(n\log n)$ query time to output $L$, and whose output after any query is correct with high probability (whp) $1 - 1/poly(n)$. Unfortunately the query time is very slow. To remedy this, the work [CM05] proposed for $p=1$ in the strict turnstile model, a whp correct algorithm achieving suboptimal space $O(\varepsilon^{-1}\log^2 n)$, worse update time $O(\log^2 n)$, but much better query time $O(\varepsilon^{-1}poly(\log n))$. We show this tradeoff between space and update time versus query time is unnecessary. We provide a new algorithm, ExpanderSketch, which in the most general turnstile model achieves optimal $O(\varepsilon^{-p}\log n)$ space, $O(\log n)$ update time, and fast $O(\varepsilon^{-p}poly(\log n))$ query time, and whp correctness. Our main innovation is an efficient reduction from the heavy hitters to a clustering problem in which each heavy hitter is encoded as some form of noisy spectral cluster in a much bigger graph, and the goal is to identify every cluster. Since every heavy hitter must be found, correctness requires that every cluster be found. We then develop a "cluster-preserving clustering" algorithm, partitioning the graph into clusters without destroying any original cluster.
S-hull: a fast radial sweep-hull routine for Delaunay triangulation
Venue: arXiv cs.CG 2016
Year: 2016

A new O(nlog(n)) algorithm is presented for performing Delaunay triangulation of sets of 2D points. The novel component of the algorithm is a radially propagating \emph{sweep-hull} (sequentially created from the radially sorted set of 2D points, giving a non-overlapping triangulation), paired with a final triangle flipping step to give the Delaunay triangluation. In empirical tests the algorithm runs in approximately half the time of q-hull for 2D Delaunay triangulation on randomly generated point sets.
Does Technical Debt Lead to the Rejection of Pull Requests?
Venue: arXiv cs.SE 2016
Year: 2016

Technical Debt is a term used to classify non-optimal solutions during software development. These solutions cause several maintenance problems and hence they should be avoided or at least documented. Although there are a considered number of studies that focus on the identification of Technical Debt, we focus on the identification of Technical Debt in pull requests. Specifically, we conduct an investigation to reveal the different types of Technical Debt that can lead to the rejection of pull requests. From the analysis of 1,722 pull requests, we classify Technical Debt in seven categories namely design, documentation, test, build, project convention, performance, or security debt. Our results indicate that the most common category of Technical Debt is design with 39.34%, followed by test with 23.70% and project convention with 15.64%. We also note that the type of Technical Debt influences on the size of push request discussions, e.g., security and project convention debts instigate more discussion than the other types.
PET: An Eye-tracking Dataset for Animal-centric PASCAL Object Classes
Venue: arXiv cs.HC 2016
Year: 2016

We present the Pascal animal classes Eye Tracking database. Our database comprises eye movement recordings compiled from forty users for the bird, cat, cow, dog, horse and sheep {trainval} sets from the VOC 2012 image set. Different from recent eye-tracking databases such as \cite{kiwon_cvpr13_gaze,PapadopoulosCKF14}, a salient aspect of PET is that it contains eye movements recorded for both the free-viewing and visual search task conditions. While some differences in terms of overall gaze behavior and scanning patterns are observed between the two conditions, a very similar number of fixations are observed on target objects for both conditions. As a utility application, we show how feature pooling around fixated locations enables enhanced (animal) object classification accuracy.
Online Lower Bounds via Duality
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we exploit linear programming duality in the online setting (i.e., where input arrives on the fly) from the unique perspective of designing lower bounds on the competitive ratio. In particular, we provide a general technique for obtaining online deterministic and randomized lower bounds (i.e., hardness results) on the competitive ratio for a wide variety of problems. We show the usefulness of our approach by providing new, tight lower bounds for three diverse online problems. The three problems we show tight lower bounds for are the Vector Bin Packing problem, Ad-auctions (and various online matching problems), and the Capital Investment problem. Our methods are sufficiently general that they can also be used to reconstruct existing lower bounds. Our techniques are in stark contrast to previous works, which exploit linear programming duality to obtain positive results, often via the useful primal-dual scheme. We design a general recipe with the opposite aim of obtaining negative results via duality. The general idea behind our approach is to construct a primal linear program based on a collection of input sequences, where the objective function corresponds to optimizing the competitive ratio. We then obtain the corresponding dual linear program and provide a feasible solution, where the objective function yields a lower bound on the competitive ratio. Online lower bounds are often achieved by adapting the input sequence according to an online algorithm's behavior and doing an appropriate ad hoc case analysis. Using our unifying techniques, we simultaneously combine these cases into one linear program and achieve online lower bounds via a more robust analysis. We are confident that our framework can be successfully applied to produce many more lower bounds for a wide array of online problems.
Cournot-Nash Equilibria for Bandwidth Allocation under Base-Station Cooperation
Venue: arXiv cs.NI 2016
Year: 2016

-In this paper, a novel resource allocation scheme based on discrete Cournot-Nash equilibria and optimal transport theory is proposed. The originality of this framework lies in the joint optimization of downlink bandwidth allocation and cooperation between base stations. A tractable formalization is given in the form of a quadratic optimization problem. A low complexity approximate solution is derived and theoretically characterized. Simulations highlight the existence of an optimal working point, that maximizes user satisfaction ratio and network load. The impact of the network deployment on the optimum is numerically investigated, thanks to the $β$-Ginibre model. Indeed, base stations are assumed to be drawn according to $β$-Ginibre point processes. Numerical analysis shows that the network performance increases with $β$ going to one.