OpenRaiser/Intern-Atlas huggingface dataset:
A Conceptual UX-aware Model of Requirements
Venue: arXiv cs.SE 2016
Year: 2016

User eXperience (UX) is becoming increasingly important for success of software products. Yet, many companies still face various challenges in their work with UX. Part of these challenges relate to inadequate knowledge and awareness of UX and that current UX models are commonly not practical nor well integrated into existing Software Engineering (SE) models and concepts. Therefore, we present a conceptual UX-aware model of requirements for software development practitioners. This layered model shows the interrelation between UX and functional and quality requirements. The model is developed based on current models of UX and software quality characteristics. Through the model we highlight the main differences between various requirement types in particular essentially subjective and accidentally subjective quality requirements. We also present the result of an initial validation of the model through interviews with 12 practitioners and researchers. Our results show that the model can raise practitioners' knowledge and awareness of UX in particular in relation to requirement and testing activities. It can also facilitate UX-related communication among stakeholders with different backgrounds.
Efficient Feature Group Sequencing for Anytime Linear Prediction
Venue: arXiv cs.LG 2016
Year: 2016

We consider \textit{anytime} linear prediction in the common machine learning setting, where features are in groups that have costs. We achieve anytime (or interruptible) predictions by sequencing the computation of feature groups and reporting results using the computed features at interruption. We extend Orthogonal Matching Pursuit (OMP) and Forward Regression (FR) to learn the sequencing greedily under this group setting with costs. We theoretically guarantee that our algorithms achieve near-optimal linear predictions at each budget when a feature group is chosen. With a novel analysis of OMP, we improve its theoretical bound to the same strength as that of FR. In addition, we develop a novel algorithm that consumes cost $4B$ to approximate the optimal performance of \textit{any} cost $B$, and prove that with cost less than $4B$, such an approximation is impossible. To our knowledge, these are the first anytime bounds at \textit{all} budgets. We test our algorithms on two real-world data-sets and evaluate them in terms of anytime linear prediction performance against cost-weighted Group Lasso and alternative greedy algorithms.
A Survey on Soft Subspace Clustering
Venue: arXiv cs.LG 2016
Year: 2016

Subspace clustering (SC) is a promising clustering technology to identify clusters based on their associations with subspaces in high dimensional spaces. SC can be classified into hard subspace clustering (HSC) and soft subspace clustering (SSC). While HSC algorithms have been extensively studied and well accepted by the scientific community, SSC algorithms are relatively new but gaining more attention in recent years due to better adaptability. In the paper, a comprehensive survey on existing SSC algorithms and the recent development are presented. The SSC algorithms are classified systematically into three main categories, namely, conventional SSC (CSSC), independent SSC (ISSC) and extended SSC (XSSC). The characteristics of these algorithms are highlighted and the potential future development of SSC is also discussed.
Some properties of antistochastic strings
Venue: arXiv cs.IT 2016
Year: 2016

Antistochastic strings are those strings that lack any reasonable statistical explanations. We establish the follow property of such strings: every absolutely non-stochastic string $x$ is "holographic" in the sense that it can be restored by a short program from any its part whose length equals the Kolmogorov complexity of $x$. Further we will show how it can be used for list decoding from erasing and for prove that symmetry of information fails for total conditional complexity.
On Ideal Lattices, Gröbner Bases and Generalized Hash Functions
Venue: arXiv cs.SC 2016
Year: 2016

In this paper, we draw connections between ideal lattices and multivariate polynomial rings over integers using Gröbner bases. Ideal lattices are ideals in the residue class ring, $\mathbb{Z}[x]/\langle f \rangle$ (here $f$ is a monic polynomial), and cryptographic primitives have been built based on these objects. As ideal lattices in the univariate case are generalizations of cyclic lattices, we introduce the notion of multivariate cyclic lattices and show that multivariate ideal lattices are indeed a generalization of them. Based on multivariate ideal lattices, we establish the existence of collision resistant hash functions using Gröbner basis techniques. For the construction of hash functions, we define a worst case problem, shortest substitution problem w.r.t. an ideal in $\mathbb{Z}[x_1,\ldots, x_n]$, and establish hardness results using functional fields.
Process-aware web programming with Jolie
Venue: arXiv cs.DC 2016
Year: 2016

We extend the Jolie programming language to capture the native modelling of process-aware web information systems, i.e., web information systems based upon the execution of business processes. Our main contribution is to offer a unifying approach for the programming of distributed architectures on the web, which can capture web servers, stateful process execution, and the composition of services via mediation. We discuss applications of this approach through a series of examples that cover, e.g., static content serving, multiparty sessions, and the evolution of web systems. Finally, we present a performance evaluation that includes a comparison of Jolie-based web systems to other frameworks and a measurement of its scalability.
A Multilevel Bilinear Programming Algorithm For the Vertex Separator Problem
Venue: arXiv cs.DS 2016
Year: 2016

The Vertex Separator Problem for a graph is to find the smallest collection of vertices whose removal breaks the graph into two disconnected subsets that satisfy specified size constraints. In the paper 10.1016/j.ejor.2014.05.042, the Vertex Separator Problem was formulated as a continuous (non-concave/non-convex) bilinear quadratic program. In this paper, we develop a more general continuous bilinear program which incorporates vertex weights, and which applies to the coarse graphs that are generated in a multilevel compression of the original Vertex Separator Problem. A Mountain Climbing Algorithm is used to find a stationary point of the continuous bilinear quadratic program, while second-order optimality conditions and perturbation techniques are used to escape from either a stationary point or a local maximizer. The algorithms for solving the continuous bilinear program are employed during the solution and refinement phases in a multilevel scheme. Computational results and comparisons demonstrate the advantage of the proposed algorithm.
Hardness of Peeling with Stashes
Venue: arXiv cs.CC 2016
Year: 2016

The analysis of several algorithms and data structures can be framed as a peeling process on a random hypergraph: vertices with degree less than k and their adjacent edges are removed until no vertices of degree less than k are left. Often the question is whether the remaining hypergraph, the k-core, is empty or not. In some settings, it may be possible to remove either vertices or edges from the hypergraph before peeling, at some cost. For example, in hashing applications where keys correspond to edges and buckets to vertices, one might use an additional side data structure, commonly referred to as a stash, to separately handle some keys in order to avoid collisions. The natural question in such cases is to find the minimum number of edges (or vertices) that need to be stashed in order to realize an empty k-core. We show that both these problems are NP-complete for all $k \geq 2$ on graphs and regular hypergraphs, with the sole exception being that the edge variant of stashing is solvable in polynomial time for $k = 2$ on standard (2-uniform) graphs.
Some "Goodness" Properties of LDA Lattices
Venue: arXiv cs.IT 2016
Year: 2016

We study some structural properties of Construction-A lattices obtained from low density parity check (LDPC) codes over prime fields. Such lattices are called low density Construction-A (LDA) lattices, and permit low-complexity belief propagation decoding for transmission over Gaussian channels. It has been shown that LDA lattices achieve the capacity of the power constrained additive white Gaussian noise (AWGN) channel with closest lattice-point decoding, and simulations suggested that they perform well under belief propagation decoding. We continue this line of work, and prove that these lattices are good for packing and mean squared error (MSE) quantization, and that their duals are good for packing. With this, we can conclude that codes constructed using nested LDA lattices can achieve the capacity of the power constrained AWGN channel, the capacity of the dirty paper channel, the rates guaranteed by the compute-and-forward protocol, and the best known rates for bidirectional relaying with perfect secrecy.
Collaborative Multi-sensor Classification via Sparsity-based Representation
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose a general collaborative sparse representation framework for multi-sensor classification, which takes into account the correlations as well as complementary information between heterogeneous sensors simultaneously while considering joint sparsity within each sensor's observations. We also robustify our models to deal with the presence of sparse noise and low-rank interference signals. Specifically, we demonstrate that incorporating the noise or interference signal as a low-rank component in our models is essential in a multi-sensor classification problem when multiple co-located sources/sensors simultaneously record the same physical event. We further extend our frameworks to kernelized models which rely on sparsely representing a test sample in terms of all the training samples in a feature space induced by a kernel function. A fast and efficient algorithm based on alternative direction method is proposed where its convergence to an optimal solution is guaranteed. Extensive experiments are conducted on several real multi-sensor data sets and results are compared with the conventional classifiers to verify the effectiveness of the proposed methods.
A Polynomial Delay Algorithm for Generating Connected Induced Subgraphs of a Given Cardinality
Venue: arXiv cs.DS 2016
Year: 2016

We give a polynomial delay algorithm, that for any graph $G$ and positive integer $k$, enumerates all connected induced subgraphs of $G$ of order $k$. Our algorithm enumerates each subgraph in at most $O((k\min\{(n-k),kΔ\})^2(Δ+\log k))$ and uses linear space $O(n+m)$, where $n$ and $m$ are respectively the number of vertices and edges of $G$ and $Δ$ is the maximum degree.
Strong data processing inequalities and $Φ$-Sobolev inequalities for discrete channels
Venue: arXiv cs.IT 2016
Year: 2016

The noisiness of a channel can be measured by comparing suitable functionals of the input and output distributions. For instance, the worst-case ratio of output relative entropy to input relative entropy for all possible pairs of input distributions is bounded from above by unity, by the data processing theorem. However, for a fixed reference input distribution, this quantity may be strictly smaller than one, giving so-called strong data processing inequalities (SDPIs). The same considerations apply to an arbitrary $Φ$-divergence. This paper presents a systematic study of optimal constants in SDPIs for discrete channels, including their variational characterizations, upper and lower bounds, structural results for channels on product probability spaces, and the relationship between SDPIs and so-called $Φ$-Sobolev inequalities (another class of inequalities that can be used to quantify the noisiness of a channel by controlling entropy-like functionals of the input distribution by suitable measures of input-output correlation). Several applications to information theory, discrete probability, and statistical physics are discussed.
Modeling LRU caches with Shot Noise request processes
Venue: arXiv cs.PF 2016
Year: 2016

In this paper we analyze Least Recently Used (LRU) caches operating under the Shot Noise requests Model (SNM). The SNM was recently proposed to better capture the main characteristics of today Video on Demand (VoD) traffic. We investigate the validity of Che's approximation through an asymptotic analysis of the cache eviction time. In particular, we provide a large deviation principle, a law of large numbers and a central limit theorem for the cache eviction time, as the cache size grows large. Finally, we derive upper and lower bounds for the "hit" probability in tandem networks of caches under Che's approximation.
Do Capacity Constraints Constrain Coalitions?
Venue: arXiv cs.GT 2016
Year: 2016

We study strong equilibria in symmetric capacitated cost-sharing games. In these games, a graph with designated source $s$ and sink $t$ is given, and each edge is associated with some cost. Each agent chooses strategically an $s$-$t$ path, knowing that the cost of each edge is shared equally between all agents using it. Two variants of cost-sharing games have been previously studied: (i) games where coalitions can form, and (ii) games where edges are associated with capacities; both variants are inspired by real-life scenarios. In this work we combine these variants and analyze strong equilibria (profiles where no coalition can deviate) in capacitated games. This combination gives rise to new phenomena that do not occur in the previous variants. Our contribution is two-fold. First, we provide a topological characterization of networks that always admit a strong equilibrium. Second, we establish tight bounds on the efficiency loss that may be incurred due to strategic behavior, as quantified by the strong price of anarchy (and stability) measures. Interestingly, our results are qualitatively different than those obtained in the analysis of each variant alone, and the combination of coalitions and capacities entails the introduction of more refined topology classes than previously studied.
Processing SPARQL Queries Over Distributed RDF Graphs
Venue: arXiv cs.DB 2016
Year: 2016

We propose techniques for processing SPARQL queries over a large RDF graph in a distributed environment. We adopt a "partial evaluation and assembly" framework. Answering a SPARQL query Q is equivalent to finding subgraph matches of the query graph Q over RDF graph G. Based on properties of subgraph matching over a distributed graph, we introduce local partial match as partial answers in each fragment of RDF graph G. For assembly, we propose two methods: centralized and distributed assembly. We analyze our algorithms from both theoretically and experimentally. Extensive experiments over both real and benchmark RDF repositories of billions of triples confirm that our method is superior to the state-of-the-art methods in both the system's performance and scalability.
Large-scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications
Venue: arXiv cs.CV 2016
Year: 2016

In computer vision, many problems such as image segmentation, pixel labelling, and scene parsing can be formulated as binary quadratic programs (BQPs). For submodular problems, cuts based methods can be employed to efficiently solve large-scale problems. However, general nonsubmodular problems are significantly more challenging to solve. Finding a solution when the problem is of large size to be of practical interest, however, typically requires relaxation. Two standard relaxation methods are widely used for solving general BQPs--spectral methods and semidefinite programming (SDP), each with their own advantages and disadvantages. Spectral relaxation is simple and easy to implement, but its bound is loose. Semidefinite relaxation has a tighter bound, but its computational complexity is high, especially for large scale problems. In this work, we present a new SDP formulation for BQPs, with two desirable properties. First, it has a similar relaxation bound to conventional SDP formulations. Second, compared with conventional SDP methods, the new SDP formulation leads to a significantly more efficient and scalable dual optimization approach, which has the same degree of complexity as spectral methods. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the dual problem. Both of them are significantly more efficiently than standard interior-point methods. In practice, the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems. Our experiments on a few computer vision applications including clustering, image segmentation, co-segmentation and registration show the potential of our SDP formulation for solving large-scale BQPs.
Stable marriage and roommates problems with restricted edges: complexity and approximability
Venue: arXiv cs.DM 2016
Year: 2016

In the stable marriage and roommates problems, a set of agents is given, each of them having a strictly ordered preference list over some or all of the other agents. A matching is a set of disjoint pairs of mutually accepted agents. If any two agents mutually prefer each other to their partner, then they block the matching, otherwise, the matching is said to be stable. In this paper we investigate the complexity of finding a solution satisfying additional constraints on restricted pairs of agents. Restricted pairs can be either forced or forbidden. A stable solution must contain all of the forced pairs, while it must contain none of the forbidden pairs. Dias et al. gave a polynomial-time algorithm to decide whether such a solution exists in the presence of restricted edges. If the answer is no, one might look for a solution close to optimal. Since optimality in this context means that the matching is stable and satisfies all constraints on restricted pairs, there are two ways of relaxing the constraints by permitting a solution to: (1) be blocked by some pairs (as few as possible), or (2) violate some constraints on restricted pairs (again as few as possible). Our main theorems prove that for the (bipartite) stable marriage problem, case (1) leads to NP-hardness and inapproximability results, whilst case (2) can be solved in polynomial time. For the non-bipartite stable roommates instances, case (2) yields an NP-hard problem. In the case of NP-hard problems, we also discuss polynomially solvable special cases, arising from restrictions on the lengths of the preference lists, or upper bounds on the numbers of restricted pairs.
Multitask diffusion adaptation over asynchronous networks
Venue: arXiv cs.SY 2016
Year: 2016

The multitask diffusion LMS is an efficient strategy to simultaneously infer, in a collaborative manner, multiple parameter vectors. Existing works on multitask problems assume that all agents respond to data synchronously. In several applications, agents may not be able to act synchronously because networks can be subject to several sources of uncertainties such as changing topology, random link failures, or agents turning on and off for energy conservation. In this work, we describe a model for the solution of multitask problems over asynchronous networks and carry out a detailed mean and mean-square error analysis. Results show that sufficiently small step-sizes can still ensure both stability and performance. Simulations and illustrative examples are provided to verify the theoretical findings. The framework is applied to a particular application involving spectral sensing.
Dimensionality Reduction with Subspace Structure Preservation
Venue: arXiv cs.LG 2016
Year: 2016

Modeling data as being sampled from a union of independent subspaces has been widely applied to a number of real world applications. However, dimensionality reduction approaches that theoretically preserve this independence assumption have not been well studied. Our key contribution is to show that $2K$ projection vectors are sufficient for the independence preservation of any $K$ class data sampled from a union of independent subspaces. It is this non-trivial observation that we use for designing our dimensionality reduction technique. In this paper, we propose a novel dimensionality reduction algorithm that theoretically preserves this structure for a given dataset. We support our theoretical analysis with empirical results on both synthetic and real world data achieving \textit{state-of-the-art} results compared to popular dimensionality reduction techniques.
On Gate Complexity of Reversible Circuits Consisting of NOT, CNOT and 2-CNOT Gates
Venue: arXiv cs.ET 2016
Year: 2016

The paper discusses the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates. The Shannon gate complexity function $L(n, q)$ for a reversible circuit, implementing a Boolean transformation $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$, is defined as a function of $n$ and the number of additional inputs $q$. The general lower bound $L(n,q) \geq \frac{2^n(n-2)}{3\log_2(n+q)} - \frac{n}{3}$ for the gate complexity of a reversible circuit is proved. An upper bound $L(n,0) \leqslant 3n2^{n+4}(1+o(1)) \mathop / \log_2n$ for the gate complexity of a reversible circuit without additional inputs is proved. An upper bound $L(n,q_0) \lesssim 2^n$ for the gate complexity of a reversible circuit with $q_0 \sim n2^{n-o(n)}$ additional inputs is proved.
Sparse Sampling in Helical Cone-Beam CT Perfect Reconstruction Algorithms
Venue: arXiv cs.IT 2016
Year: 2016

In the current paper we consider the Helical Cone Beam CT. This scanning method exposes the patient to large quantities of radiation and results in very large amounts of data being collected and stored. Both these facts are prime motivators for the development of an efficient, reduced rate, sampling pattern. We calculate bounds on the support in the frequency domain of the collected data and use these to suggest an efficient sampling pattern. A reduction of up to a factor of 2 in sampling rate is suggested. Indeed, we show that reconstruction quality is not affected by this reduction of sampling rates.
Integrating formal methods into traditional practices for software development: an overview
Venue: arXiv cs.SE 2016
Year: 2016

This paper shows an overview of a research project for integrating formal methods in popular practices for software development in Mexico. The article shows only the main results from the survey about methods and practices and an overview of the initial proposal of practices applying lightweight formal methods to requirements specification and software modelling.
Equivariant algorithms for constraint satisfaction problems over coset templates
Venue: arXiv cs.LO 2016
Year: 2016

We investigate the Constraint Satisfaction Problem (CSP) over templates with a group structure, and algorithms solving CSP that are equivariant, i.e. invariant under a natural group action induced by a template. Our main result is a method of proving the implication: if CSP over a coset template T is solvable by an equivariant algorithm then T is 2-Helly (or equivalently, has a majority polymorphism). Therefore bounded width, and definability in fixed-point logics, coincide with 2-Helly. Even if these facts may be derived from already known results, our new proof method has two advantages. First, the proof is short, self-contained, and completely avoids referring to the omitting-types theorems. Second, it brings to light some new connections between CSP theory and descriptive complexity theory, via a construction similar to CFI graphs.