OpenRaiser/Intern-Atlas huggingface dataset:
Delay Evaluation of OpenFlow Network Based on Queueing Model
Venue: arXiv cs.DC 2016
Year: 2016

As one of the most popular south-bound protocol of software-defined networking(SDN), OpenFlow decouples the network control from forwarding devices. It offers flexible and scalable functionality for networks. These advantages may cause performance issues since there are performance penalties in terms of packet processing speed. It is important to understand the performance of OpenFlow switches and controllers for its deployments. In this paper we model the packet processing time of OpenFlow switches and controllers. We mainly analyze how the probability of packet-in messages impacts the performance of switches and controllers. Our results show that there is a performance penalty in OpenFlow networks. However, the penalty is not much when probability of packet-in messages is low. This model can be used for a network designer to approximate the performance of her deployments.
Communication complexity of approximate Nash equilibria
Venue: arXiv cs.GT 2016
Year: 2016

For a constant $ε$, we prove a poly(N) lower bound on the (randomized) communication complexity of $ε$-Nash equilibrium in two-player NxN games. For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of $(ε,ε)$-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least $(1-ε)$-fraction of the players are $ε$-best replying.
Self-Averaging Expectation Propagation
Venue: arXiv cs.IT 2016
Year: 2016

We investigate the problem of approximate Bayesian inference for a general class of observation models by means of the expectation propagation (EP) framework for large systems under some statistical assumptions. Our approach tries to overcome the numerical bottleneck of EP caused by the inversion of large matrices. Assuming that the measurement matrices are realizations of specific types of ensembles we use the concept of freeness from random matrix theory to show that the EP cavity variances exhibit an asymptotic self-averaging property. They can be pre-computed using specific generating functions, i.e. the R- and/or S-transforms in free probability, which do not require matrix inversions. Our approach extends the framework of (generalized) approximate message passing -- assumes zero-mean iid entries of the measurement matrix -- to a general class of random matrix ensembles. The generalization is via a simple formulation of the R- and/or S-transforms of the limiting eigenvalue distribution of the Gramian of the measurement matrix. We demonstrate the performance of our approach on a signal recovery problem of nonlinear compressed sensing and compare it with that of EP.
New quantum codes from dual-containing cyclic codes over finite rings
Venue: arXiv cs.IT 2016
Year: 2016

Let $R=\mathbb{F}_{2^{m}}+u\mathbb{F}_{2^{m}}+\cdots+u^{k}\mathbb{F}_{2^{m}}$ , where $\mathbb{F}_{2^{m}}$ is a finite field with $2^{m}$ elements, $m$ is a positive integer, $u$ is an indeterminate with $u^{k+1}=0.$ In this paper, we propose the constructions of two new families of quantum codes obtained from dual-containing cyclic codes of odd length over $R$. A new Gray map over $R$ is defined and a sufficient and necessary condition for the existence of dual-containing cyclic codes over $R$ is given. A new family of $2^{m}$-ary quantum codes is obtained via the Gray map and the Calderbank-Shor-Steane construction from dual-containing cyclic codes over $R.$ Furthermore, a new family of binary quantum codes is obtained via the Gray map, the trace map and the Calderbank-Shor-Steane construction from dual-containing cyclic codes over $R.$
A Convolutional Neural Network Approach for Post-Processing in HEVC Intra Coding
Venue: arXiv cs.MM 2016
Year: 2016

Lossy image and video compression algorithms yield visually annoying artifacts including blocking, blurring, and ringing, especially at low bit-rates. To reduce these artifacts, post-processing techniques have been extensively studied. Recently, inspired by the great success of convolutional neural network (CNN) in computer vision, some researches were performed on adopting CNN in post-processing, mostly for JPEG compressed images. In this paper, we present a CNN-based post-processing algorithm for High Efficiency Video Coding (HEVC), the state-of-the-art video coding standard. We redesign a Variable-filter-size Residue-learning CNN (VRCNN) to improve the performance and to accelerate network training. Experimental results show that using our VRCNN as post-processing leads to on average 4.6% bit-rate reduction compared to HEVC baseline. The VRCNN outperforms previously studied networks in achieving higher bit-rate reduction, lower memory cost, and multiplied computational speedup.
Conversion Methods for Improving Structural Analysis of Differential-Algebraic Equation Systems
Venue: arXiv cs.SC 2016
Year: 2016

Differential-algebraic equation systems (DAEs) are generated routinely by simulation and modeling environments. Before a simulation starts and a numerical method is applied, some kind of structural analysis (SA) is used to determine which equations to be differentiated, and how many times. Both Pantelides's algorithm and Pryce's $Σ$-method are equivalent: if one of them finds correct structural information, the other does also. Nonsingularity of the Jacobian produced by SA indicates a success, which occurs on many problems of interest. However, these methods can fail on simple, solvable DAEs and give incorrect structural information including the index. This article investigates $Σ$-method's failures and presents two conversion methods for fixing them. Both methods convert a DAE on which the $Σ$-method fails to an equivalent problem on which this SA is more likely to succeed.
A Large-Scale Multilingual Disambiguation of Glosses
Venue: arXiv cs.CL 2016
Year: 2016

Linking concepts and named entities to knowledge bases has become a crucial Natural Language Understanding task. In this respect, recent works have shown the key advantage of exploiting textual definitions in various Natural Language Processing applications. However, to date there are no reliable large-scale corpora of sense-annotated textual definitions available to the research community. In this paper we present a large-scale high-quality corpus of disambiguated glosses in multiple languages, comprising sense annotations of both concepts and named entities from a unified sense inventory. Our approach for the construction and disambiguation of the corpus builds upon the structure of a large multilingual semantic network and a state-of-the-art disambiguation system; first, we gather complementary information of equivalent definitions across different languages to provide context for disambiguation, and then we combine it with a semantic similarity-based refinement. As a result we obtain a multilingual corpus of textual definitions featuring over 38 million definitions in 263 languages, and we make it freely available at http://lcl.uniroma1.it/disambiguated-glosses. Experiments on Open Information Extraction and Sense Clustering show how two state-of-the-art approaches improve their performance by integrating our disambiguated corpus into their pipeline.
On the Sensitivity Complexity of $k$-Uniform Hypergraph Properties
Venue: arXiv cs.CC 2016
Year: 2016

In this paper we investigate the sensitivity complexity of hypergraph properties. We present a $k$-uniform hypergraph property with sensitivity complexity $O(n^{\lceil k/3\rceil})$ for any $k\geq3$, where $n$ is the number of vertices. Moreover, we can do better when $k\equiv1$ (mod 3) by presenting a $k$-uniform hypergraph property with sensitivity $O(n^{\lceil k/3\rceil-1/2})$. This result disproves a conjecture of Babai~\cite{Babai}, which conjectures that the sensitivity complexity of $k$-uniform hypergraph properties is at least $Ω(n^{k/2})$. We also investigate the sensitivity complexity of other symmetric functions and show that for many classes of transitive Boolean functions the minimum achievable sensitivity complexity can be $O(N^{1/3})$, where $N$ is the number of variables. Finally, we give a lower bound for sensitivity of $k$-uniform hypergraph properties, which implies the {\em sensitivity conjecture} of $k$-uniform hypergraph properties for any constant $k$.
Load Coupling Power Optimization in Cloud Radio Access Networks
Venue: arXiv cs.IT 2016
Year: 2016

Recently, Cloud-based Radio Access Network (C-RAN) has been proposed as a potential solution to reduce energy cost in cellular networks. C-RAN centralizes the baseband processing capabilities of Base Stations (BSs) in a cloud computing platform in the form of BaseBand Unit (BBU) pool. In C-RAN, power consumed by the traditional BS system is distributed as wireless transmission power of the Remote Radio Heads (RRHs) and baseband processing power of the BBU pool. Different from previous work where wireless transmission power and baseband processing power are optimized individually and independently, this paper focuses on joint optimization of allocation for these two kinds of power and attempts to minimize the total power consumption subject to Quality of Service (QoS) requirements from users in terms of data rates. First, we exploit the load coupling model to express the coupling relations among power, load and user data rates. Based on the load coupling mode, we formulate the joint power optimization problem in C-RAN over both wireless transmission power and baseband processing power. Second, we prove that operating at full load may not be optimal in minimizing the total power consumption in C-RAN. Finally, we propose an efficient iterative algorithm to solve the target problem. Simulations have been performed to validate our theoretical and algorithmic work. The results show that the proposed algorithm outperforms existing schemes (without joint power optimization) in terms of power consumption.
A simple linear space algorithm for computing a longest common increasing subsequence
Venue: arXiv cs.DS 2016
Year: 2016

This paper reformulates the problem of finding a longest common increasing subsequence of the two given input sequences in a very succinct way. An extremely simple linear space algorithm based on the new formula can find a longest common increasing subsequence of sizes $n$ and $m$ respectively, in time $O(nm)$ using additional $\min\{n,m\}+1$ space.
The Goodness of Covariance Selection Problem from AUC Bounds
Venue: arXiv cs.IT 2016
Year: 2016

We conduct a study of graphical models and discuss the quality of model selection approximation by formulating the problem as a detection problem and examining the area under the curve (AUC). We are specifically looking at the model selection problem for jointly Gaussian random vectors. For Gaussian random vectors, this problem simplifies to the covariance selection problem which is widely discussed in literature by Dempster [1]. In this paper, we give the definition for the correlation approximation matrix (CAM) which contains all information about the model selection problem and discuss the pth order Markov chain model and the $p$th order star network model for the a Gaussian distribution with Toeplitz covariance matrix. For each model, we compute the model covariance matrix as well as the KL divergence between the Gaussian distribution and its model. We also show that if the model order, p, is proportional to the number of nodes, n, then the model selection is asymptotically good as the number of nodes, n, goes to infinity since the AUC in this case is bounded away from one. We conduct some simulations which confirm the theoretical analysis and also show that the selected model quality increases as the model order, p, increases.
A Context-aware Natural Language Generator for Dialogue Systems
Venue: arXiv cs.CL 2016
Year: 2016

We present a novel natural language generation system for spoken dialogue systems capable of entraining (adapting) to users' way of speaking, providing contextually appropriate responses. The generator is based on recurrent neural networks and the sequence-to-sequence approach. It is fully trainable from data which include preceding context along with responses to be generated. We show that the context-aware generator yields significant improvements over the baseline in both automatic metrics and a human pairwise preference test.
Aligning Packed Dependency Trees: a theory of composition for distributional semantics
Venue: arXiv cs.CL 2016
Year: 2016

We present a new framework for compositional distributional semantics in which the distributional contexts of lexemes are expressed in terms of anchored packed dependency trees. We show that these structures have the potential to capture the full sentential contexts of a lexeme and provide a uniform basis for the composition of distributional knowledge in a way that captures both mutual disambiguation and generalization.
New Technology Assessment in Entrepreneurial Financing - Can Crowdfunding Predict Venture Capital Investments?
Venue: arXiv cs.CY 2016
Year: 2016

Recent years have seen an upsurge of novel sources of new venture financing through crowdfunding (CF). We draw on 54,943 successfully crowdfunded projects and 3,313 venture capital (VC) investments throughout the period 04/2012-06/2015 to investigate, on the aggregate level, how crowdfunding is related to a more traditional source of entrepreneurial finance, venture capital. Granger causality tests support the view that VC investments follow crowdfunding investments. Cointegration tests also suggest a long-run relationship between crowdfunding and VC investments, while impulse response functions (IRF) indicate a positive effect running from CF to VC within two to six months. Crowdfunding seems to help VC investors in assessing future trends rather than crowding them out of the market.
Capacity-achieving and Flicker-free FEC coding scheme for Dimmable Visible Light Communication Based on Polar Codes
Venue: arXiv cs.IT 2016
Year: 2016

Visible light communication (VLC) could provide short-range optical wireless communication together with illumination using LED lighting. However, conventional forward error correction (FEC) codes for reliable communication do not have the features for dimming support and flicker mitigation which are required in VLC for the main functionality of lighting. Therefore, auxiliary coding techniques are usually needed, which eventually reduce the coding efficiency and increase the complexity. In this paper, a polar codes-based FEC coding scheme for dimmable VLC is proposed to increase the coding efficiency and simplify the coding structure. Experimental results show that the proposed scheme has the following advantages: 1) equal probability of 1's and 0's in codewords, which is inherently supporting 50% dimming balance; 2) short run length property (about 90% bits have runs shorter than 5) which can avoid flickers and additional run-length limited line coding; 3) higher coding efficiency about twofold than that of other coding schemes; 4) capacity achieving error correction performance with low-complexity encoding and decoding, which is about 3 dB higher coding gain than that of RS(64,32) in IEEE standard for dimming ratio 50% and about 1 dB higher coding gain than that of LDPC codes for dimming ratio 25% (or 75%).
Embedded SML using the MLton compiler
Venue: arXiv cs.PL 2016
Year: 2016

In this extended abstract we present our current work on leveraging Standard ML for developing embedded and real-time systems. Specifically we detail our experiences in modifying MLton, a whole program, optimizing compiler for Standard ML, for use in such contexts. We focus primarily on the language runtime, re-working the threading subsystem and garbage collector, as well as necessary changes for integrating MLton generated programs into a light weight operating system kernel. We compare and contrast these changes to our previous work on extending MLton for multicore systems, which focused around acheiving scalability.
Large-scale Collaborative Imaging Genetics Studies of Risk Genetic Factors for Alzheimer's Disease Across Multiple Institutions
Venue: arXiv cs.LG 2016
Year: 2016

Genome-wide association studies (GWAS) offer new opportunities to identify genetic risk factors for Alzheimer's disease (AD). Recently, collaborative efforts across different institutions emerged that enhance the power of many existing techniques on individual institution data. However, a major barrier to collaborative studies of GWAS is that many institutions need to preserve individual data privacy. To address this challenge, we propose a novel distributed framework, termed Local Query Model (LQM) to detect risk SNPs for AD across multiple research institutions. To accelerate the learning process, we propose a Distributed Enhanced Dual Polytope Projection (D-EDPP) screening rule to identify irrelevant features and remove them from the optimization. To the best of our knowledge, this is the first successful run of the computationally intensive model selection procedure to learn a consistent model across different institutions without compromising their privacy while ranking the SNPs that may collectively affect AD. Empirical studies are conducted on 809 subjects with 5.9 million SNP features which are distributed across three individual institutions. D-EDPP achieved a 66-fold speed-up by effectively identifying irrelevant features.
Low Complexity Power Allocation Schemes in Regenerative Multi-user Relay Networks
Venue: arXiv cs.IT 2016
Year: 2016

In relay assisted wireless communications, the multi-source, single relay and single destination system (an $M$-1-1 system) is of growing importance, due to the increased demand for higher network throughput and connectivity. Previously, power allocation in $M$-1-1 systems have assumed availability of instantaneous channel state information (CSI), which is rather idealistic. In this paper we consider an $M$-1-1 Decode-and-Forward (DF), Full-Duplex, orthogonal frequencey division multiple access (OFDMA) based relay system with statistical-CSI and analyze the achievable rate $R$ of such a system. We show how $R$ can only be maximized by numerical power allocation schemes which has a high-complexity of order $\mathcal O(M^3)$. By introducing a rational approximation in the achievable rate analysis, we develop two low-complexity power allocation schemes that can obtain a system achievable rate very close to the maximum $R$. Most importantly, we show that the complexity of our power allocation schemes is of order $\mathcal O(M\log M)$. We then show how our power allocation schemes are suitable for a multi-user relay system, where either the priority is to maximize system throughput, or where lower computations in power allocation scheme are essential. The work we present in this paper will be of value to the design and implementation of real-time multi-user relay systems operating under realistic channel conditions.
YouSkyde: Information Hiding for Skype Video Traffic
Venue: arXiv cs.CR 2016
Year: 2016

In this paper a new information hiding method for Skype videoconference calls - YouSkyde - is introduced. A Skype traffic analysis revealed that introducing intentional losses into the Skype video traffic stream to provide the means for clandestine communication is the most favourable solution. A YouSkyde proof-of-concept implementation was carried out and its experimental evaluation is presented. The results obtained prove that the proposed method is feasible and offer a steganographic bandwidth as high as 0.93 kbps, while introducing negligible distortions into transmission quality and providing high undetectability.
Fast Trajectory Simplification Algorithm for Natural User Interfaces in Robot Programming by Demonstration
Venue: arXiv cs.CV 2016
Year: 2016

Trajectory simplification is a problem encountered in areas like Robot programming by demonstration, CAD/CAM, computer vision, and in GPS-based applications like traffic analysis. This problem entails reduction of the points in a given trajectory while keeping the relevant points which preserve important information. The benefits include storage reduction, computational expense, while making data more manageable. Common techniques formulate a minimization problem to be solved, where the solution is found iteratively under some error metric, which causes the algorithms to work in super-linear time. We present an algorithm called FastSTray, which selects the relevant points in the trajectory in linear time by following an open loop heuristic approach. While most current trajectory simplification algorithms are tailored for GPS trajectories, our approach focuses on smooth trajectories for robot programming by demonstration recorded using motion capture systems.Two variations of the algorithm are presented: 1. aims to preserve shape and temporal information; 2. preserves only shape information. Using the points in the simplified trajectory we use cubic splines to interpolate between these points and recreate the original trajectory. The presented algorithm was tested on trajectories recorded from a hand-tracking system. It was able to eliminate about 90% of the points in the original trajectories while maintaining errors between 0.78-2cm which corresponds to 1%-2.4% relative error with respect to the bounding box of the trajectories.
Connectivity-Aware Traffic Phase Scheduling for Heterogeneously Connected Vehicles
Venue: arXiv cs.SY 2016
Year: 2016

We consider a transportation system of heterogeneously connected vehicles, where not all vehicles are able to communicate. Heterogeneous connectivity in transportation systems is coupled to practical constraints such that (i) not all vehicles may be equipped with devices having communication interfaces, (ii) some vehicles may not prefer to communicate due to privacy and security reasons, and (iii) communication links are not perfect and packet losses and delay occur in practice. In this context, it is crucial to develop control algorithms by taking into account the heterogeneity. In this paper, we particularly focus on making traffic phase scheduling decisions. We develop a connectivity-aware traffic phase scheduling algorithm for heterogeneously connected vehicles that increases the intersection efficiency (in terms of the average number of vehicles that are allowed to pass the intersection) by taking into account the heterogeneity. The simulation results show that our algorithm significantly improves the efficiency of intersections as compared to the baselines.
Optimal Bidding in Repeated Wireless Spectrum Auctions with Budget Constraints
Venue: arXiv cs.NI 2016
Year: 2016

Small operators who take part in secondary wireless spectrum markets typically have strict budget limits. In this paper, we study the bidding problem of a budget constrained operator in repeated secondary spectrum auctions. In existing truthful auctions, truthful bidding is the optimal strategy of a bidder. However, budget limits impact bidding behaviors and make bidding decisions complicated, since bidders may behave differently to avoid running out of money. We formulate the problem as a dynamic auction game between operators, where knowledge of other operators is limited due to the distributed nature of wireless networks/markets. We first present a Markov Decision Process (MDP) formulation of the problem and characterize the optimal bidding strategy of an operator, provided that opponents' bids are i.i.d. Next, we generalize the formulation to a Markov game that, in conjunction with model-free reinforcement learning approaches, enables an operator to make inferences about its opponents based on local observations. Finally, we present a fully distributed learning-based bidding algorithm which relies only on local information. Our numerical results show that our proposed learning-based bidding results in a better utility than truthful bidding.