OpenRaiser/Intern-Atlas huggingface dataset:
Revisited Design Criteria For STBCs With Reduced Complexity ML Decoding
Venue: arXiv cs.IT 2016
Year: 2016

The design of linear STBCs offering a low-complexity ML decoding using the well known Sphere Decoder (SD) has been extensively studied in last years. The first considered approach to derive design criteria for the construction of such codes is based on the Hurwitz-Radon (HR) Theory for mutual orthogonality between the weight matrices defining the linear code. This appproach served to construct new families of codes admitting fast sphere decoding such as multi-group decodable, fast decodable, and fast-group decodable codes. In a second Quadratic Form approach, the Fast Sphere Decoding (FSD) complexity of linear STBCs is captured by a Hurwitz Radon Quadratic Form (HRQF) matrix based in its essence on the HR Theory. In this work, we revisit the structure of weight matrices for STBCs to admit Fast Sphere decoding. We first propose novel sufficient conditions and design criteria for reduced-complexity ML decodable linear STBCs considering an arbitrary number of antennas and linear STBCs of an arbitrary coding rate. Then we apply the derived criteria to the three families of codes mentioned above and provide analytical proofs showing that the FSD complexity depends only on the weight matrices and their ordering and not on the channel gains or the number of antennas and explain why the so far used HR theory-based approaches are suboptimal.
Analysis of Algorithms for Permutations Biased by Their Number of Records
Venue: arXiv cs.DM 2016
Year: 2016

The topic of the article is the parametric study of the complexity of algorithms on arrays of pairwise distinct integers. We introduce a model that takes into account the non-uniformness of data, which we call the Ewens-like distribution of parameter $θ$ for records on permutations: the weight $θ^r$ of a permutation depends on its number $r$ of records. We show that this model is meaningful for the notion of presortedness, while still being mathematically tractable. Our results describe the expected value of several classical permutation statistics in this model, and give the expected running time of three algorithms: the Insertion Sort, and two variants of the Min-Max search.
Need Polynomial Systems be Doubly-exponential?
Venue: arXiv cs.SC 2016
Year: 2016

Polynomial Systems, or at least their algorithms, have the reputation of being doubly-exponential in the number of variables [Mayr and Mayer, 1982], [Davenport and Heintz, 1988]. Nevertheless, the Bezout bound tells us that that number of zeros of a zero-dimensional system is singly-exponential in the number of variables. How should this contradiction be reconciled? We first note that [Mayr and Ritscher, 2013] shows that the doubly exponential nature of Gröbner bases is with respect to the dimension of the ideal, not the number of variables. This inspires us to consider what can be done for Cylindrical Algebraic Decomposition which produces a doubly-exponential number of polynomials of doubly-exponential degree. We review work from ISSAC 2015 which showed the number of polynomials could be restricted to doubly-exponential in the (complex) dimension using McCallum's theory of reduced projection in the presence of equational constraints. We then discuss preliminary results showing the same for the degree of those polynomials. The results are under primitivity assumptions whose importance we illustrate.
The Yahoo Query Treebank, V. 1.0
Venue: arXiv cs.CL 2016
Year: 2016

A description and annotation guidelines for the Yahoo Webscope release of Query Treebank, Version 1.0, May 2016.
The dynamics of the CBC Mode of Operation
Venue: arXiv cs.CR 2016
Year: 2016

In cryptography, the Cipher Block Chaining (CBC), one of the most commonly used mode in recent years, is a mode of operation that uses a block cipher to provide confidentiality or authenticity. In our previous research work, we have shown that this mode of operation exhibits, under some conditions, a chaotic behaviour. We have studied this behaviour by evaluating both its level of sensibility and expansivity. In this paper, we intend to deepen the topological study of the CBC mode of operation and evaluate its property of topological mixing. Additionally, other quantitative evaluations are performed, and the level of topological entropy has been evaluated too.
Weakly Supervised Learning of Affordances
Venue: arXiv cs.CV 2016
Year: 2016

Localizing functional regions of objects or affordances is an important aspect of scene understanding. In this work, we cast the problem of affordance segmentation as that of semantic image segmentation. In order to explore various levels of supervision, we introduce a pixel-annotated affordance dataset of 3090 images containing 9916 object instances with rich contextual information in terms of human-object interactions. We use a deep convolutional neural network within an expectation maximization framework to take advantage of weakly labeled data like image level annotations or keypoint annotations. We show that a further reduction in supervision is possible with a minimal loss in performance when human pose is used as context.
Lattice paths of slope 2/5
Venue: arXiv cs.DM 2016
Year: 2016

We analyze some enumerative and asymptotic properties of Dyck paths under a line of slope 2/5.This answers to Knuth's problem \\#4 from his "Flajolet lecture" during the conference "Analysis of Algorithms" (AofA'2014) in Paris in June 2014.Our approach relies on the work of Banderier and Flajolet for asymptotics and enumeration of directed lattice paths. A key ingredient in the proof is the generalization of an old trick of Knuth himself (for enumerating permutations sortable by a stack),promoted by Flajolet and others as the "kernel method". All the corresponding generating functions are algebraic,and they offer some new combinatorial identities, which can be also tackled in the A=B spirit of Wilf--Zeilberger--Petkov{\v s}ek.We show how to obtain similar results for other slopes than 2/5, an interesting case being e.g. Dyck paths below the slope 2/3, which corresponds to the so called Duchon's club model.
Context-Aware Adaptive Framework for e-Health Monitoring
Venue: arXiv cs.CY 2016
Year: 2016

For improving e-health services, we propose a context-aware framework to monitor the activities of daily living of dependent persons. We define a strategy for generating long-term realistic scenarios and a framework containing an adaptive monitoring algorithm based on three approaches for optimizing resource usage. The used approaches provide a deep knowledge about the person's context by considering: the person's profile, the activities and the relationships between activities. We evaluate the performances of our framework and show its adaptability and significant reduction in network, energy and processing usage over a traditional monitoring implementation.
On the Price of Anarchy of Highly Congested Nonatomic Network Games
Venue: arXiv cs.GT 2016
Year: 2016

We consider nonatomic network games with one source and one destination. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we show that, under suitable conditions, the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case. The counterexamples occur in very simple parallel graphs.
Transiently Consistent SDN Updates: Being Greedy is Hard
Venue: arXiv cs.NI 2016
Year: 2016

The software-defined networking paradigm introduces interesting opportunities to operate networks in a more flexible, optimized, yet formally verifiable manner. Despite the logically centralized control, however, a Software-Defined Network (SDN) is still a distributed system, with inherent delays between the switches and the controller. Especially the problem of changing network configurations in a consistent manner, also known as the consistent network update problem, has received much attention over the last years. In particular, it has been shown that there exists an inherent tradeoff between update consistency and speed. This paper revisits the problem of updating an SDN in a transiently consistent, loop-free manner. First, we rigorously prove that computing a maximum (greedy) loop-free network update is generally NP-hard; this result has implications for the classic maximum acyclic subgraph problem (the dual feedback arc set problem) as well. Second, we show that for special problem instances, fast and good approximation algorithms exist.
Approximating Min-Cost Chain-Constrained Spanning Trees: A Reduction from Weighted to Unweighted Problems
Venue: arXiv cs.DS 2016
Year: 2016

We study the {\em min-cost chain-constrained spanning-tree} (abbreviated \mcst) problem: find a min-cost spanning tree in a graph subject to degree constraints on a nested family of node sets. We devise the {\em first} polytime algorithm that finds a spanning tree that (i) violates the degree constraints by at most a constant factor {\em and} (ii) whose cost is within a constant factor of the optimum. Previously, only an algorithm for {\em unweighted} \cst was known \cite{olver}, which satisfied (i) but did not yield any cost bounds. This also yields the first result that obtains an $O(1)$-factor for {\em both} the cost approximation and violation of degree constraints for any spanning-tree problem with general degree bounds on node sets, where an edge participates in a super-constant number of degree constraints. A notable feature of our algorithm is that we {\em reduce} \mcst to unweighted \cst (and then utilize \cite{olver}) via a novel application of {\em Lagrangian duality} to simplify the {\em cost structure} of the underlying problem and obtain a decomposition into certain uniform-cost subproblems. We show that this Lagrangian-relaxation based idea is in fact applicable more generally and, for any cost-minimization problem with packing side-constraints, yields a reduction from the weighted to the unweighted problem. We believe that this reduction is of independent interest. As another application of our technique, we consider the {\em $k$-budgeted matroid basis} problem, where we build upon a recent rounding algorithm of \cite{BansalN16} to obtain an improved $n^{O(k^{1.5}/ε)}$-time algorithm that returns a solution that satisfies (any) one of the budget constraints exactly and incurs a $(1+ε)$-violation of the other budget constraints.
A mechanization of the Blakers-Massey connectivity theorem in Homotopy Type Theory
Venue: arXiv cs.LO 2016
Year: 2016

This paper continues investigations in "synthetic homotopy theory": the use of homotopy type theory to give machine-checked proofs of constructions from homotopy theory We present a mechanized proof of the Blakers-Massey connectivity theorem, a result relating the higher-dimensional homotopy groups of a pushout type (roughly, a space constructed by gluing two spaces along a shared subspace) to those of the components of the pushout. This theorem gives important information about the pushout type, and has a number of useful corollaries, including the Freudenthal suspension theorem, which has been studied in previous formalizations. The new proof is more elementary than existing ones in abstract homotopy-theoretic settings, and the mechanization is concise and high-level, thanks to novel combinations of ideas from homotopy theory and type theory.
CORDIC-based Architecture for Powering Computation in Fixed-Point Arithmetic
Venue: arXiv cs.AR 2016
Year: 2016

We present a fixed point architecture (source VHDL code is provided) for powering computation. The fully customized architecture, based on the expanded hyperbolic CORDIC algorithm, allows for design space exploration to establish trade-offs among design parameters (numerical format, number of iterations), execution time, resource usage and accuracy. We also generate Pareto-optimal realizations in the resource-accuracy space: this approach can produce optimal hardware realizations that simultaneously satisfy resource and accuracy requirements.
Sensorimotor Input as a Language Generalisation Tool: A Neurorobotics Model for Generation and Generalisation of Noun-Verb Combinations with Sensorimotor Inputs
Venue: arXiv cs.RO 2016
Year: 2016

The paper presents a neurorobotics cognitive model to explain the understanding and generalisation of nouns and verbs combinations when a vocal command consisting of a verb-noun sentence is provided to a humanoid robot. This generalisation process is done via the grounding process: different objects are being interacted, and associated, with different motor behaviours, following a learning approach inspired by developmental language acquisition in infants. This cognitive model is based on Multiple Time-scale Recurrent Neural Networks (MTRNN).With the data obtained from object manipulation tasks with a humanoid robot platform, the robotic agent implemented with this model can ground the primitive embodied structure of verbs through training with verb-noun combination samples. Moreover, we show that a functional hierarchical architecture, based on MTRNN, is able to generalise and produce novel combinations of noun-verb sentences. Further analyses of the learned network dynamics and representations also demonstrate how the generalisation is possible via the exploitation of this functional hierarchical recurrent network.
A Fast 2-Approximation Algorithm for Guarding Orthogonal Terrains
Venue: arXiv cs.CG 2016
Year: 2016

Terrain Guarding Problem(TGP), which is known to be NP-complete, asks to find a smallest set of guard locations on a terrain $T$ such that every point on $T$ is visible by a guard. Here, we study this problem on 1.5D orthogonal terrains where the edges are bound to be horizontal or vertical. We propose a 2-approximation algorithm that runs in O($n \log m$) time, where $n$ and $m$ are the sizes of input and output, respectively. This is an improvement over the previous best algorithm, which is a 2-approximation with O($n^2$) running time.
Implementation of the open source virtualization technologies in cloud computing
Venue: arXiv cs.DC 2016
Year: 2016

The Virtualization and Cloud Computing is a recent buzzword in the digital world. Cloud computing provide IT as a service to the users on demand basis. This service has greater flexibility, availability, reliability and scalability with utility computing model. This new concept of computing has an immense potential in it to be used in the field of e-governance and in the overall IT development perspective in developing countries like Bangladesh.
Dual of Codes over Finite Quotients of Polynomial Rings
Venue: arXiv cs.IT 2016
Year: 2016

Let $A=\frac{\mathbb{F}[x]}{\langle f(x)\rangle }$, where $f(x)$ is a monic polynomial over a finite field $\mathbb{F}$. In this paper, we study the relation between $A$-codes and their duals. In particular, we state a counterexample and a correction to a theorem of Berger and El Amrani (Codes over finite quotients of polynomial rings, \emph{Finite Fields Appl.} \textbf{25} (2014), 165--181) and present an efficient algorithm to find a system of generators for the dual of a given $A$-code. Also we characterize self-dual $A$-codes of length 2 and investigate when the $\mathbb{F}$-dual of $A$-codes are $A$-codes.
Deep Neural Networks Under Stress
Venue: arXiv cs.CV 2016
Year: 2016

In recent years, deep architectures have been used for transfer learning with state-of-the-art performance in many datasets. The properties of their features remain, however, largely unstudied under the transfer perspective. In this work, we present an extensive analysis of the resiliency of feature vectors extracted from deep models, with special focus on the trade-off between performance and compression rate. By introducing perturbations to image descriptions extracted from a deep convolutional neural network, we change their precision and number of dimensions, measuring how it affects the final score. We show that deep features are more robust to these disturbances when compared to classical approaches, achieving a compression rate of 98.4%, while losing only 0.88% of their original score for Pascal VOC 2007.
Characterizing Quantifier Fuzzification Mechanisms: a behavioral guide for practical applications
Venue: arXiv cs.AI 2016
Year: 2016

Important advances have been made in the fuzzy quantification field. Nevertheless, some problems remain when we face the decision of selecting the most convenient model for a specific application. In the literature, several desirable adequacy properties have been proposed, but theoretical limits impede quantification models from simultaneously fulfilling every adequacy property that has been defined. Besides, the complexity of model definitions and adequacy properties makes very difficult for real users to understand the particularities of the different models that have been presented. In this work we will present several criteria conceived to help in the process of selecting the most adequate Quantifier Fuzzification Mechanisms for specific practical applications. In addition, some of the best known well-behaved models will be compared against this list of criteria. Based on this analysis, some guidance to choose fuzzy quantification models for practical applications will be provided.
The Non-Uniform k-Center Problem
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we introduce and study the Non-Uniform k-Center problem (NUkC). Given a finite metric space $(X,d)$ and a collection of balls of radii $\{r_1\geq \cdots \ge r_k\}$, the NUkC problem is to find a placement of their centers on the metric space and find the minimum dilation $α$, such that the union of balls of radius $α\cdot r_i$ around the $i$th center covers all the points in $X$. This problem naturally arises as a min-max vehicle routing problem with fleets of different speeds. The NUkC problem generalizes the classic $k$-center problem when all the $k$ radii are the same (which can be assumed to be $1$ after scaling). It also generalizes the $k$-center with outliers (kCwO) problem when there are $k$ balls of radius $1$ and $\ell$ balls of radius $0$. There are $2$-approximation and $3$-approximation algorithms known for these problems respectively; the former is best possible unless P=NP and the latter remains unimproved for 15 years. We first observe that no $O(1)$-approximation is to the optimal dilation is possible unless P=NP, implying that the NUkC problem is more non-trivial than the above two problems. Our main algorithmic result is an $(O(1),O(1))$-bi-criteria approximation result: we give an $O(1)$-approximation to the optimal dilation, however, we may open $Θ(1)$ centers of each radii. Our techniques also allow us to prove a simple (uni-criteria), optimal $2$-approximation to the kCwO problem improving upon the long-standing $3$-factor. Our main technical contribution is a connection between the NUkC problem and the so-called firefighter problems on trees which have been studied recently in the TCS community.
Direct Method for Training Feed-forward Neural Networks using Batch Extended Kalman Filter for Multi-Step-Ahead Predictions
Venue: arXiv cs.NE 2016
Year: 2016

This paper is dedicated to the long-term, or multi-step-ahead, time series prediction problem. We propose a novel method for training feed-forward neural networks, such as multilayer perceptrons, with tapped delay lines. Special batch calculation of derivatives called Forecasted Propagation Through Time and batch modification of the Extended Kalman Filter are introduced. Experiments were carried out on well-known time series benchmarks, the Mackey-Glass chaotic process and the Santa Fe Laser Data Series. Recurrent and feed-forward neural networks were evaluated.
SplitBox: Toward Efficient Private Network Function Virtualization
Venue: arXiv cs.CR 2016
Year: 2016

This paper presents SplitBox, a scalable system for privately processing network functions that are outsourced as software processes to the cloud. Specifically, providers processing the network functions do not learn the network policies instructing how the functions are to be processed. We first propose an abstract model of a generic network function based on match-action pairs, assuming that this is processed in a distributed manner by multiple honest-but-curious providers. Then, we introduce our SplitBox system for private network function virtualization and present a proof-of-concept implementation on FastClick -- an extension of the Click modular router -- using a firewall as a use case. Our experimental results show that SplitBox achieves a throughput of over 2 Gbps with 1 kB-sized packets on average, traversing up to 60 firewall rules.
Joint Embeddings of Hierarchical Categories and Entities
Venue: arXiv cs.CL 2016
Year: 2016

Due to the lack of structured knowledge applied in learning distributed representation of categories, existing work cannot incorporate category hierarchies into entity information.~We propose a framework that embeds entities and categories into a semantic space by integrating structured knowledge and taxonomy hierarchy from large knowledge bases. The framework allows to compute meaningful semantic relatedness between entities and categories.~Compared with the previous state of the art, our framework can handle both single-word concepts and multiple-word concepts with superior performance in concept categorization and semantic relatedness.
An Alternative Framework for Time Series Decomposition and Forecasting and its Relevance for Portfolio Choice: A Comparative Study of the Indian Consumer Durable and Small Cap Sectors
Venue: arXiv cs.OH 2016
Year: 2016

One of the challenging research problems in the domain of time series analysis and forecasting is making efficient and robust prediction of stock market prices. With rapid development and evolution of sophisticated algorithms and with the availability of extremely fast computing platforms, it has now become possible to effectively extract, store, process and analyze high volume stock market time series data. Complex algorithms for forecasting are now available for speedy execution over parallel architecture leading to fairly accurate results. In this paper, we have used time series data of the two sectors of the Indian economy: Consumer Durables sector and the Small Cap sector for the period January 2010 to December 2015 and proposed a decomposition approach for better understanding of the behavior of each of the time series. Our contention is that various sectors reveal different time series patterns and understanding them is essential for portfolio formation. Further, based on this structural analysis, we have also proposed several robust forecasting techniques and analyzed their accuracy in prediction using suitably chosen training and test data sets. Extensive results are presented to demonstrate the effectiveness of our propositions.