OpenRaiser/Intern-Atlas huggingface dataset:
SNAP: Stateful Network-Wide Abstractions for Packet Processing
Venue: arXiv cs.NI 2016
Year: 2016

Early programming languages for software-defined networking (SDN) were built on top of the simple match-action paradigm offered by OpenFlow 1.0. However, emerging hardware and software switches offer much more sophisticated support for persistent state in the data plane, without involving a central controller. Nevertheless, managing stateful, distributed systems efficiently and correctly is known to be one of the most challenging programming problems. To simplify this new SDN problem, we introduce SNAP. SNAP offers a simpler "centralized" stateful programming model, by allowing programmers to develop programs on top of one big switch rather than many. These programs may contain reads and writes to global, persistent arrays, and as a result, programmers can implement a broad range of applications, from stateful firewalls to fine-grained traffic monitoring. The SNAP compiler relieves programmers of having to worry about how to distribute, place, and optimize access to these stateful arrays by doing it all for them. More specifically, the compiler discovers read/write dependencies between arrays and translates one-big-switch programs into an efficient internal representation based on a novel variant of binary decision diagrams. This internal representation is used to construct a mixed-integer linear program, which jointly optimizes the placement of state and the routing of traffic across the underlying physical topology. We have implemented a prototype compiler and applied it to about 20 SNAP programs over various topologies to demonstrate our techniques' scalability.
On the State Complexity of the Shuffle of Regular Languages
Venue: arXiv cs.FL 2016
Year: 2016

We investigate the shuffle operation on regular languages represented by complete deterministic finite automata. We prove that $f(m,n)=2^{mn-1} + 2^{(m-1)(n-1)}(2^{m-1}-1)(2^{n-1}-1)$ is an upper bound on the state complexity of the shuffle of two regular languages having state complexities $m$ and $n$, respectively. We also state partial results about the tightness of this bound. We show that there exist witness languages meeting the bound if $2\le m\le 5$ and $n\ge2$, and also if $m=n=6$. Moreover, we prove that in the subset automaton of the NFA accepting the shuffle, all $2^{mn}$ states can be distinguishable, and an alphabet of size three suffices for that. It follows that the bound can be met if all $f(m,n)$ states are reachable. We know that an alphabet of size at least $mn$ is required provided that $m,n \ge 2$. The question of reachability, and hence also of the tightness of the bound $f(m,n)$ in general, remains open.
On the Feasibility of Sharing Spectrum Licenses in mmWave Cellular Systems
Venue: arXiv cs.IT 2016
Year: 2016

The highly directional and adaptive antennas used in mmWave communication open up the possibility of uncoordinated sharing of spectrum licenses between commercial cellular operators. There are several advantages to sharing including a reduction in license costs and an increase in spectrum utilization. In this paper, we establish the theoretical feasibility of spectrum license sharing among mmWave cellular operators. We consider a heterogeneous multi-operator system containing multiple independent cellular networks, each owned by an operator. We then compute the SINR and rate distribution for downlink mobile users of each network. Using the analysis, we compare systems with fully shared licenses and exclusive licenses for different access rules and explore the trade-offs between system performance and spectrum cost. We show that sharing spectrum licenses increases the per-user rate when antennas have narrow beams and is also favored when there is a low density of users. We also consider a multi-operator system where BSs of all the networks are co-located to show that the simultaneous sharing of spectrum and infrastructure is also feasible. We show that all networks can share licenses with less bandwidth and still achieve the same per-user median rate as if they each had an exclusive license to spectrum with more bandwidth.
Creation of a Deep Convolutional Auto-Encoder in Caffe
Venue: arXiv cs.NE 2016
Year: 2016

The development of a deep (stacked) convolutional auto-encoder in the Caffe deep learning framework is presented in this paper. We describe simple principles which we used to create this model in Caffe. The proposed model of convolutional auto-encoder does not have pooling/unpooling layers yet. The results of our experimental research show comparable accuracy of dimensionality reduction in comparison with a classic auto-encoder on the example of MNIST dataset.
Modelling and Analysis of Network Security - an Algebraic Approach
Venue: arXiv cs.CR 2016
Year: 2016

Game theory has been applied to investigate network security. But different security scenarios were often modeled via different types of games and analyzed in an ad-hoc manner. In this paper, we propose an algebraic approach for modeling and analyzing uniformly several types of network security games. This approach is based on a probabilistic extension of the value-passing Calculus of Communicating Systems (CCS) which is regarded as a Generative model for Probabilistic Value-passing CCS (PVCCSG for short). Our approach gives a uniform framework, called PVCCSG based security model, for the security scenarios modeled via perfect and complete or incomplete information games. We present then a uniform algorithm for computing the Nash equilibria strategies of a network security game on its PVCCSG based security model. The algorithm first generates a transition system for each of the PVCCSG based security models, then simplifies this transition system through graph-theoretic abstraction and bisimulation minimization. Then, a backward induction method, which is only applicable to finite tree models, can be used to compute all the Nash equilibria strategies of the (possibly infinite) security games. This algorithm is implemented and can also be tuned smoothly for computing its social optimal strategies. The effectiveness and efficiency of this approach are further demonstrated with four detailed case studies from the field of network security.
Network Coding: Connections Between Information Theory And Estimation Theory
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we prove the existence of fundamental relations between information theory and estimation theory for network-coded flows. When the network is represented by a directed graph G=(V, E) and under the assumption of uncorrelated noise over information flows between the directed links connecting transmitters, switches (relays), and receivers. We unveil that there yet exist closed-form relations for the gradient of the mutual information with respect to different components of the system matrix M. On the one hand, this result opens a new class of problems casting further insights into effects of the network topology, topological changes when nodes are mobile, and the impact of errors and delays in certain links into the network capacity which can be further studied in scenarios where one source multi-sinks multicasts and multi-source multicast where the invertibility and the rank of matrix M plays a significant role in the decoding process and therefore, on the network capacity. On the other hand, it opens further research questions of finding precoding solutions adapted to the network level.
SentiBench - a benchmark comparison of state-of-the-practice sentiment analysis methods
Venue: arXiv cs.CL 2016
Year: 2016

In the last few years thousands of scientific papers have investigated sentiment analysis, several startups that measure opinions on real data have emerged and a number of innovative products related to this theme have been developed. There are multiple methods for measuring sentiments, including lexical-based and supervised machine learning methods. Despite the vast interest on the theme and wide popularity of some methods, it is unclear which one is better for identifying the polarity (i.e., positive or negative) of a message. Accordingly, there is a strong need to conduct a thorough apple-to-apple comparison of sentiment analysis methods, \textit{as they are used in practice}, across multiple datasets originated from different data sources. Such a comparison is key for understanding the potential limitations, advantages, and disadvantages of popular methods. This article aims at filling this gap by presenting a benchmark comparison of twenty-four popular sentiment analysis methods (which we call the state-of-the-practice methods). Our evaluation is based on a benchmark of eighteen labeled datasets, covering messages posted on social networks, movie and product reviews, as well as opinions and comments in news articles. Our results highlight the extent to which the prediction performance of these methods varies considerably across datasets. Aiming at boosting the development of this research area, we open the methods' codes and datasets used in this article, deploying them in a benchmark system, which provides an open API for accessing and comparing sentence-level sentiment analysis methods.
Rank Pooling for Action Recognition
Venue: arXiv cs.CV 2016
Year: 2016

We propose a function-based temporal pooling method that captures the latent structure of the video sequence data - e.g. how frame-level features evolve over time in a video. We show how the parameters of a function that has been fit to the video data can serve as a robust new video representation. As a specific example, we learn a pooling function via ranking machines. By learning to rank the frame-level features of a video in chronological order, we obtain a new representation that captures the video-wide temporal dynamics of a video, suitable for action recognition. Other than ranking functions, we explore different parametric models that could also explain the temporal changes in videos. The proposed functional pooling methods, and rank pooling in particular, is easy to interpret and implement, fast to compute and effective in recognizing a wide variety of actions. We evaluate our method on various benchmarks for generic action, fine-grained action and gesture recognition. Results show that rank pooling brings an absolute improvement of 7-10 average pooling baseline. At the same time, rank pooling is compatible with and complementary to several appearance and local motion based methods and features, such as improved trajectories and deep learning features.
Finding $k$ Simple Shortest Paths and Cycles
Venue: arXiv cs.DS 2016
Year: 2016

The problem of finding multiple simple shortest paths in a weighted directed graph $G=(V,E)$ has many applications, and is considerably more difficult than the corresponding problem when cycles are allowed in the paths. Even for a single source-sink pair, it is known that two simple shortest paths cannot be found in time polynomially smaller than $n^3$ (where $n=|V|$) unless the All-Pairs Shortest Paths problem can be solved in a similar time bound. The latter is a well-known open problem in algorithm design. We consider the all-pairs version of the problem, and we give a new algorithm to find $k$ simple shortest paths for all pairs of vertices. For $k=2$, our algorithm runs in $O(mn + n^2 \log n)$ time (where $m=|E|$), which is almost the same bound as for the single pair case, and for $k=3$ we improve earlier bounds. Our approach is based on forming suitable path extensions to find simple shortest paths; this method is different from the `detour finding' technique used in most of the prior work on simple shortest paths, replacement paths, and distance sensitivity oracles. Enumerating simple cycles is a well-studied classical problem. We present new algorithms for generating simple cycles and simple paths in $G$ in non-decreasing order of their weights; the algorithm for generating simple paths is much faster, and uses another variant of path extensions. We also give hardness results for sparse graphs, relative to the complexity of computing a minimum weight cycle in a graph, for several variants of problems related to finding $k$ simple paths and cycles.
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Venue: arXiv cs.DS 2016
Year: 2016

We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a random low-rank overcomplete 3-tensor. For both problems, the best known guarantees are based on the sum-of-squares method. We develop new algorithms inspired by analyses of the sum-of-squares method. Our algorithms achieve the same or similar guarantees as sum-of-squares for these problems but the running time is significantly faster. For the planted sparse vector problem, we give an algorithm with running time nearly linear in the input size that approximately recovers a planted sparse vector with up to constant relative sparsity in a random subspace of $\mathbb R^n$ of dimension up to $\tilde Ω(\sqrt n)$. These recovery guarantees match the best known ones of Barak, Kelner, and Steurer (STOC 2014) up to logarithmic factors. For tensor decomposition, we give an algorithm with running time close to linear in the input size (with exponent $\approx 1.086$) that approximately recovers a component of a random 3-tensor over $\mathbb R^n$ of rank up to $\tilde Ω(n^{4/3})$. The best previous algorithm for this problem due to Ge and Ma (RANDOM 2015) works up to rank $\tilde Ω(n^{3/2})$ but requires quasipolynomial time.
Crossing Number is Hard for Kernelization
Venue: arXiv cs.CC 2016
Year: 2016

The graph crossing number problem, cr(G)<=k, asks for a drawing of a graph G in the plane with at most k edge crossings. Although this problem is in general notoriously difficult, it is fixed- parameter tractable for the parameter k [Grohe]. This suggests a closely related question of whether this problem has a polynomial kernel, meaning whether every instance of cr(G)<=k can be in polynomial time reduced to an equivalent instance of size polynomial in k (and independent of |G|). We answer this question in the negative. Along the proof we show that the tile crossing number problem of twisted planar tiles is NP-hard, which has been an open problem for some time, too, and then employ the complexity technique of cross-composition. Our result holds already for the special case of graphs obtained from planar graphs by adding one edge.
Tracking Objects with Higher Order Interactions using Delayed Column Generation
Venue: arXiv cs.CV 2016
Year: 2016

We study the problem of multi-target tracking and data association in video. We formulate this in terms of selecting a subset of high-quality tracks subject to the constraint that no pair of selected tracks is associated with a common detection (of an object). This objective is equivalent to the classic NP-hard problem of finding a maximum-weight set packing (MWSP) where tracks correspond to sets and is made further difficult since the number of candidate tracks grows exponentially in the number of detections. We present a relaxation of this combinatorial problem that uses a column generation formulation where the pricing problem is solved via dynamic programming to efficiently explore the space of tracks. We employ row generation to tighten the bound in such a way as to preserve efficient inference in the pricing problem. We show the practical utility of this algorithm for tracking problems in natural and biological video datasets.
Perfect Recovery Conditions For Non-Negative Sparse Modeling
Venue: arXiv cs.IT 2016
Year: 2016

Sparse modeling has been widely and successfully used in many applications such as computer vision, machine learning, and pattern recognition. Accompanied with those applications, significant research has studied the theoretical limits and algorithm design for convex relaxations in sparse modeling. However, theoretical analyses on non-negative versions of sparse modeling are limited in the literature either to a noiseless setting or a scenario with a specific statistical noise model such as Gaussian noise. This paper studies the performance of non-negative sparse modeling in a more general scenario where the observed signals have an unknown arbitrary distortion, especially focusing on non-negativity constrained and L1-penalized least squares, and gives an exact bound for which this problem can recover the correct signal elements. We pose two conditions to guarantee the correct signal recovery: minimum coefficient condition (MCC) and nonlinearity vs. subset coherence condition (NSCC). The former defines the minimum weight for each of the correct atoms present in the signal and the latter defines the tolerable deviation from the linear model relative to the positive subset coherence (PSC), a novel type of "coherence" metric. We provide rigorous performance guarantees based on these conditions and experimentally verify their precise predictive power in a hyperspectral data unmixing application.
Structured Compressive Sensing Based Spatio-Temporal Joint Channel Estimation for FDD Massive MIMO
Venue: arXiv cs.IT 2016
Year: 2016

Massive MIMO is a promising technique for future 5G communications due to its high spectrum and energy efficiency. To realize its potential performance gain, accurate channel estimation is essential. However, due to massive number of antennas at the base station (BS), the pilot overhead required by conventional channel estimation schemes will be unaffordable, especially for frequency division duplex (FDD) massive MIMO. To overcome this problem, we propose a structured compressive sensing (SCS)-based spatio-temporal joint channel estimation scheme to reduce the required pilot overhead, whereby the spatio-temporal common sparsity of delay-domain MIMO channels is leveraged. Particularly, we first propose the non-orthogonal pilots at the BS under the framework of CS theory to reduce the required pilot overhead. Then, an adaptive structured subspace pursuit (ASSP) algorithm at the user is proposed to jointly estimate channels associated with multiple OFDM symbols from the limited number of pilots, whereby the spatio-temporal common sparsity of MIMO channels is exploited to improve the channel estimation accuracy. Moreover, by exploiting the temporal channel correlation, we propose a space-time adaptive pilot scheme to further reduce the pilot overhead. Additionally, we discuss the proposed channel estimation scheme in multi-cell scenario. Simulation results demonstrate that the proposed scheme can accurately estimate channels with the reduced pilot overhead, and it is capable of approaching the optimal oracle least squares estimator.
Energy-Efficient Power Allocation in Cognitive Radio Systems with Imperfect Spectrum Sensing
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies energy-efficient power allocation schemes for secondary users in sensing-based spectrum sharing cognitive radio systems. It is assumed that secondary users first perform channel sensing possibly with errors and then initiate data transmission with different power levels based on sensing decisions. The circuit power is taken into account in total power consumption. In this setting, the optimization problem is to maximize energy efficiency (EE) subject to peak/average transmission power constraints and peak/average interference constraints. By exploiting quasiconcave property of EE maximization problem, the original problem is transformed into an equivalent parameterized concave problem and an iterative power allocation algorithm based on Dinkelbach's method is proposed. The optimal power levels are identified in the presence of different levels of channel side information (CSI) regarding the transmission and interference links at the secondary transmitter, namely perfect CSI of both transmission and interference links, perfect CSI of the transmission link and imperfect CSI of the interference link, imperfect CSI of both links or only statistical CSI of both links. Through numerical results, the impact of sensing performance, different types of CSI availability, and transmit and interference power constraints on the EE of the secondary users is analyzed.
On the Embeddability of Delaunay Triangulations in Anisotropic, Normed, and Bregman Spaces
Venue: arXiv cs.CG 2016
Year: 2016

Given a two-dimensional space endowed with a divergence function that is convex in the first argument, continuously differentiable in the second, and satisfies suitable regularity conditions at Voronoi vertices, we show that orphan-freedom (the absence of disconnected Voronoi regions) is sufficient to ensure that Voronoi edges and vertices are also connected, and that the dual is a simple planar graph. We then prove that the straight-edge dual of an orphan-free Voronoi diagram (with sites as the first argument of the divergence) is always an embedded triangulation. Among the divergences covered by our proofs are Bregman divergences, anisotropic divergences, as well as all distances derived from strictly convex $\mathcal{C}^1$ norms (including the $L_p$ norms with $1< p < \infty$). While Bregman diagrams of the {first kind} are simply affine diagrams, and their duals ({weighted} Delaunay triangulations) are always embedded, we show that duals of orphan-free Bregman diagrams of the \emph{second kind} are always embedded.
How to find the least upper bound on the van der Waerden Number $W(r, k)$ that is some integer Power of the coloring Integer $r$
Venue: arXiv cs.DM 2016
Year: 2016

What is a least integer upper bound on van der Waerden number $W(r, k)$ among the powers of the integer $r$? We show how this can be found by expanding the integer $W(r, k)$ into powers of $r$. Doing this enables us to find both a least upper bound and a greatest lower bound on $W(r, k)$ that are some powers of $r$ and where the greatest lower bound is equal to or smaller than $W(r, k)$. A finite series expansion of each $W(r, k)$ into integer powers of $r$ then helps us to find also a greatest real lower bound on any $k$ for which a conjecture posed by R. Graham is true, following immediately as a particular case of the overall result.
Distributed Optimization with Arbitrary Local Solvers
Venue: arXiv cs.LG 2016
Year: 2016

With the growth of data and necessity for distributed optimization methods, solvers that work well on a single machine must be re-designed to leverage distributed computation. Recent work in this area has been limited by focusing heavily on developing highly specific methods for the distributed environment. These special-purpose methods are often unable to fully leverage the competitive performance of their well-tuned and customized single machine counterparts. Further, they are unable to easily integrate improvements that continue to be made to single machine methods. To this end, we present a framework for distributed optimization that both allows the flexibility of arbitrary solvers to be used on each (single) machine locally, and yet maintains competitive performance against other state-of-the-art special-purpose distributed methods. We give strong primal-dual convergence rate guarantees for our framework that hold for arbitrary local solvers. We demonstrate the impact of local solver selection both theoretically and in an extensive experimental comparison. Finally, we provide thorough implementation details for our framework, highlighting areas for practical performance gains.