OpenRaiser/Intern-Atlas huggingface dataset:
Open-coopetition in the PC and mobile industries: the WebKit case
Venue: arXiv cs.CY 2014
Year: 2014

In an era of software crisis, the move of firms towards geographically-distributed software development teams is being challenged by collaboration issues. On this matter, the open-source phenomenon may shed some light, as successful cases on distributed collaboration in the open-source community have been recurrently reported. While practitioners move with difficulties towards globally distributed software development, there is a lack of research addressing the collaboration dynamics of large-scale distributed software projects. More particularly, even if there are empirical manifestations of collaboration among software-houses that market rival-software products within the same market, there is a clear lack of research addressing the development of information systems by coopetitive manners. While addressing a previous call for the advancement of methods and techniques to support the visualization of temporal aspects to represent change and evolution in ecosystems, we combined and virtual-ethnography (VA) with a Social Network Analysis (SNA) over publicly-available and naturally-occurring data that allowed us to re-construct and visualize the evolution of the WebKit collaboration in a sequence of networks. We started by screening, publicly available data such as company announcements, financial reports and specialized-press that allowed us to gain insights of the industrial context. After attaining a better understanding of the the competitive dynamics of the mobile-devices and PC industries, we started extracting and analyzing the social network of the WebKit community leveraging SNA, which is an emergent method widely established across disciplines of social sciences in general.Our case confirmed much of the established literature on coopetition, but more detailed observations revealed that not all coopetition theoretical propositions can be generalized to the open-source arena.
Compressed Sensing Performance Analysis via Replica Method using Bayesian framework
Venue: arXiv cs.IT 2014
Year: 2014

Compressive sensing (CS) is a new methodology to capture signals at lower rate than the Nyquist sampling rate when the signals are sparse or sparse in some domain. The performance of CS estimators is analyzed in this paper using tools from statistical mechanics, especially called replica method. This method has been used to analyze communication systems like Code Division Multiple Access (CDMA) and multiple input multi- ple output (MIMO) systems with large size. Replica analysis, now days rigorously proved, is an efficient tool to analyze large systems in general. Specifically, we analyze the performance of some of the estimators used in CS like LASSO (the Least Absolute Shrinkage and Selection Operator) estimator and Zero-Norm regularizing estimator as a special case of maximum a posteriori (MAP) estimator by using Bayesian framework to connect the CS estimators and replica method. We use both replica symmetric (RS) ansatz and one-step replica symmetry breaking (1RSB) ansatz, clamming the latter is efficient when the problem is not convex. This work is more analytical in its form. It is deferred for next step to focus on the numerical results.
Summarizing Semantic Model Differences
Venue: arXiv cs.SE 2014
Year: 2014

Fundamental building blocks for managing and understanding software evolution in the context of model-driven engineering are differencing operators one can use for model comparisons. Semantic model differencing deals with the definition and computation of semantic diff operators for model comparison, operators whose input consists of two models and whose output is a set of diff witnesses, instances of one model that are not instances of the other. However, in many cases the complete set of diff witnesses is too large to be efficiently computed and effectively presented. Moreover, many of the witnesses are very similar and hence not interesting. Thus, an important challenge of semantic differencing relates to witness selection and presentation. In this paper we propose to address this challenge using a summarization technique, based on a notion of equivalence that partitions the set of diff witnesses. The result of the computation is a summary set, consisting of a single representative witness from each equivalence class. We demonstrate our ideas using two concrete diff operators, for class diagrams and for activity diagrams, where the computation of the summary set is efficient and does not require the enumeration of all witnesses.
ADDiff: Semantic Differencing for Activity Diagrams
Venue: arXiv cs.SE 2014
Year: 2014

Activity diagrams (ADs) have recently become widely used in the modeling of workflows, business processes, and web-services, where they serve various purposes, from documentation, requirement definitions, and test case specifications, to simulation and code generation. As models, programs, and systems evolve over time, understanding changes and their impact is an important challenge, which has attracted much research efforts in recent years. In this paper we present addiff, a semantic differencing operator for ADs. Unlike most existing approaches to model comparison, which compare the concrete or the abstract syntax of two given diagrams and output a list of syntactical changes or edit operations, addiff considers the Semantics of the diagrams at hand and outputs a set of diff witnesses, each of which is an execution trace that is possible in the first AD and is not possible in the second. We motivate the use of addiff, formally define it, and show two algorithms to compute it, a concrete forward-search algorithm and a symbolic xpoint algorithm, implemented using BDDs and integrated into the Eclipse IDE. Empirical results and examples demonstrate the feasibility and unique contribution of addiff to the state-of-the-art in version comparison and evolution analysis.
On the Capacity Region of the Two-user Interference Channel with a Cognitive Relay
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers a variation of the classical two-user interference channel where the communication of two interfering source-destination pairs is aided by an additional node that has a priori knowledge of the messages to be transmitted, which is referred to as the it cognitive relay. For this Interference Channel with a Cognitive Relay (ICCR) In particular, for the class of injective semi-deterministic ICCRs, a sum-rate upper bound is derived for the general memoryless ICCR and further tightened for the Linear Deterministic Approximation (LDA) of the Gaussian noise channel at high SNR, which disregards the noise and focuses on the interaction among the users' signals. The capacity region of the symmetric LDA is completely characterized except for the regime of moderately weak interference and weak links from the CR to the destinations. The insights gained from the analysis of the LDA are then translated back to the symmetric Gaussian noise channel (GICCR). For the symmetric GICCR, an approximate characterization (to within a constant gap) of the capacity region is provided for a parameter regime where capacity was previously unknown. The approximately optimal scheme suggests that message cognition at a relay is beneficial for interference management as it enables simultaneous over the air neutralization of the interference at both destinations.
Extensible Validation Framework for DSLs using MontiCore on the Example of Coding Guidelines
Venue: arXiv cs.SE 2014
Year: 2014

Unit test environments are today's state of the art for many programming languages to keep the software's quality above a certain level. However, the software's syntactic quality necessary for the developers themselves is not covered by the aforementioned frameworks. This paper presents a tool realized using the DSL framework MontiCore for automatically validating easily extensible coding guidelines for any domain specific language or even general purpose languages like C++ and its application in an automotive R&D project where a German OEM and several suppliers were involved. Moreover, it was exemplary applied on UML/P-based sequence charts as well.
Representation Independent Analytics Over Structured Data
Venue: arXiv cs.DB 2014
Year: 2014

Database analytics algorithms leverage quantifiable structural properties of the data to predict interesting concepts and relationships. The same information, however, can be represented using many different structures and the structural properties observed over particular representations do not necessarily hold for alternative structures. Thus, there is no guarantee that current database analytics algorithms will still provide the correct insights, no matter what structures are chosen to organize the database. Because these algorithms tend to be highly effective over some choices of structure, such as that of the databases used to validate them, but not so effective with others, database analytics has largely remained the province of experts who can find the desired forms for these algorithms. We argue that in order to make database analytics usable, we should use or develop algorithms that are effective over a wide range of choices of structural organizations. We introduce the notion of representation independence, study its fundamental properties for a wide range of data analytics algorithms, and empirically analyze the amount of representation independence of some popular database analytics algorithms. Our results indicate that most algorithms are not generally representation independent and find the characteristics of more representation independent heuristics under certain representational shifts.
Feedback Control of Switched Stochastic Systems Using Randomly Available Active Mode Information
Venue: arXiv cs.SY 2014
Year: 2014

Almost sure asymptotic stabilization of a discrete-time switched stochastic system is investigated. Information on the active operation mode of the switched system is assumed to be available for control purposes only at random time instants. We propose a stabilizing feedback control framework that utilizes the information obtained through mode observations. We first consider the case where stochastic properties of mode observation instants are fully known. We obtain sufficient asymptotic stabilization conditions for the closed-loop switched stochastic system under our proposed control law. We then explore the case where exact knowledge of the stochastic properties of mode observation instants is not available. We present a set of alternative stabilization conditions for this case. The results for both cases are predicated on the analysis of a sequence-valued process that encapsulates the stochastic nature of the evolution of active operation mode between mode observation instants. Finally, we demonstrate the efficacy of our results with numerical examples.
A simple proof of the completeness of APAL
Venue: arXiv cs.LO 2014
Year: 2014

We provide a simple proof of the completeness of arbitrary public announcement logic APAL. The proof is an improvement over the proof found in the publication Knowable as Known after an Announcement.
When Can a Relay Reduce End-to-End Communication Delay?
Venue: arXiv cs.IT 2014
Year: 2014

The impact of relaying on the latency of communication in a relay channel is studied. Both decode-forward (DF) and amplify-forward (AF) are considered, and are compared with the point-to-point (P2P) scheme which does not use the relay. The question as to whether DF and AF can decrease the latency of communicating a number of bits with a given reliability requirement is addressed. Latency expressions for the three schemes are derived. Although both DF and AF use a block-transmission structure which sends the information over multiple transmission blocks, they can both achieve latencies lower that P2P. Conditions under which this occurs are obtained. Interestingly, these conditions are more strict when compared to the conditions under which DF and AF achieve higher information-theoretic rates than P2P.
Unifying Hyper and Epistemic Temporal Logic
Venue: arXiv cs.LO 2014
Year: 2014

In the literature, two powerful temporal logic formalisms have been proposed for expressing information flow security requirements, that in general, go beyond regular properties. One is classic, based on the knowledge modalities of epistemic logic. The other one, the so called hyper logic, is more recent and subsumes many proposals from the literature; it is based on explicit and simultaneous quantification over multiple paths. In an attempt to better understand how these logics compare with each other, we consider the logic KCTL* (the extension of CTL* with knowledge modalities and synchronous perfect recall semantics) and HyperCTL*. We first establish that KCTL* and HyperCTL* are expressively incomparable. Second, we introduce and study a natural linear past extension of HyperCTL* to unify KCTL* and HyperCTL*; indeed, we show that KCTL* can be easily translated in linear time into the proposed logic. Moreover, we show that the model-checking problem for this novel logic is decidable, and we provide its exact computational complexity in terms of a new measure of path quantifiers' alternation. For this, we settle open complexity issues for unrestricted quantified propositional temporal logic.
Synergy cycles in the Norwegian innovation system: The relation between synergy and cycle values
Venue: arXiv cs.CY 2014
Year: 2014

The knowledge base of an economy measured in terms of Triple Helix relations can be analyzed in terms of mutual information among geographical, sectorial, and size distributions of firms as dimensions of the probabilistic entropy. The resulting synergy values of a TH system provide static snapshots. In this study, we add the time dimension and analyze the synergy dynamics using the Norwegian innovation system as an example. The synergy among the three dimensions can be mapped as a set of partial time series and spectrally analyzed. The results suggest that the synergy at the level of both the country and its 19 counties shoe non-chaotic oscillatory behavior and resonates in a set of natural frequencies. That is, synergy surges and drops are non-random and can be analyzed and predicted. There is a proportional dependence between the amplitudes of oscillations and synergy values and an inverse proportional dependence between the oscillation frequencies' relative inputs and synergy values. This analysis of the data informs us that one can expect frequency-related synergy-volatility growth in relation to the synergy value and a shift in the synergy volatility towards the long-term fluctuations with the synergy growth.
Co-adaptation in a Handwriting Recognition System
Venue: arXiv cs.HC 2014
Year: 2014

Handwriting is a natural and versatile method for human-computer interaction, especially on small mobile devices such as smart phones. However, as handwriting varies significantly from person to person, it is difficult to design handwriting recognizers that perform well for all users. A natural solution is to use machine learning to adapt the recognizer to the user. One complicating factor is that, as the computer adapts to the user, the user also adapts to the computer and probably changes their handwriting. This paper investigates the dynamics of co-adaptation, a process in which both the computer and the user are adapting their behaviors in order to improve the speed and accuracy of the communication through handwriting. We devised an information-theoretic framework for quantifying the efficiency of a handwriting system where the system includes both the user and the computer. Using this framework, we analyzed data collected from an adaptive handwriting recognition system and characterized the impact of machine adaptation and of human adaptation. We found that both machine adaptation and human adaptation have significant impact on the input rate and must be considered together in order to improve the efficiency of the system as a whole.
A Framework for Practical Parallel Fast Matrix Multiplication
Venue: arXiv cs.DC 2014
Year: 2014

Matrix multiplication is a fundamental computation in many scientific disciplines. In this paper, we show that novel fast matrix multiplication algorithms can significantly outperform vendor implementations of the classical algorithm and Strassen's fast algorithm on modest problem sizes and shapes. Furthermore, we show that the best choice of fast algorithm depends not only on the size of the matrices but also the shape. We develop a code generation tool to automatically implement multiple sequential and shared-memory parallel variants of each fast algorithm, including our novel parallelization scheme. This allows us to rapidly benchmark over 20 fast algorithms on several problem sizes. Furthermore, we discuss a number of practical implementation issues for these algorithms on shared-memory machines that can direct further research on making fast algorithms practical.
Path algebra algorithm for finding longest increasing subsequence
Venue: arXiv cs.DS 2014
Year: 2014

New algorithm for finding longest increasing subsequence is discussed. This algorithm is based on the ideas of idempotent mathematics and uses Max-Plus idempotent semiring. Problem of finding longest increasing sub- sequence is reformulated in a matrix form and solved with linear algebra.
"Look Ma, No Hands!" A Parameter-Free Topic Model
Venue: arXiv cs.LG 2014
Year: 2014

It has always been a burden to the users of statistical topic models to predetermine the right number of topics, which is a key parameter of most topic models. Conventionally, automatic selection of this parameter is done through either statistical model selection (e.g., cross-validation, AIC, or BIC) or Bayesian nonparametric models (e.g., hierarchical Dirichlet process). These methods either rely on repeated runs of the inference algorithm to search through a large range of parameter values which does not suit the mining of big data, or replace this parameter with alternative parameters that are less intuitive and still hard to be determined. In this paper, we explore to "eliminate" this parameter from a new perspective. We first present a nonparametric treatment of the PLSA model named nonparametric probabilistic latent semantic analysis (nPLSA). The inference procedure of nPLSA allows for the exploration and comparison of different numbers of topics within a single execution, yet remains as simple as that of PLSA. This is achieved by substituting the parameter of the number of topics with an alternative parameter that is the minimal goodness of fit of a document. We show that the new parameter can be further eliminated by two parameter-free treatments: either by monitoring the diversity among the discovered topics or by a weak supervision from users in the form of an exemplar topic. The parameter-free topic model finds the appropriate number of topics when the diversity among the discovered topics is maximized, or when the granularity of the discovered topics matches the exemplar topic. Experiments on both synthetic and real data prove that the parameter-free topic model extracts topics with a comparable quality comparing to classical topic models with "manual transmission". The quality of the topics outperforms those extracted through classical Bayesian nonparametric models.
A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
Venue: arXiv cs.SY 2014
Year: 2014

This paper studies efficient distributed optimization methods for multi-agent networks. Specifically, we consider a convex optimization problem with a globally coupled linear equality constraint and local polyhedra constraints, and develop distributed optimization methods based on the alternating direction method of multipliers (ADMM). The considered problem has many applications in machine learning and smart grid control problems. Due to the presence of the polyhedra constraints, agents in the existing methods have to deal with polyhedra constrained subproblems at each iteration. One of the key issues is that projection onto a polyhedra constraint is not trivial, which prohibits from closed-form solutions or the use of simple algorithms for solving these subproblems. In this paper, by judiciously integrating the proximal minimization method with ADMM, we propose a new distributed optimization method where the polyhedra constraints are handled softly as penalty terms in the subproblems. This makes the subproblems efficiently solvable and consequently reduces the overall computation time. Furthermore, we propose a randomized counterpart that is robust against randomly ON/OFF agents and imperfect communication links. We analytically show that both the proposed methods have a worst-case $\mathcal{O}(1/k)$ convergence rate, where $k$ is the iteration number. Numerical results show that the proposed methods offer considerably lower computation time than the existing distributed ADMM method.
A type system for Continuation Calculus
Venue: arXiv cs.LO 2014
Year: 2014

Continuation Calculus (CC), introduced by Geron and Geuvers, is a simple foundational model for functional computation. It is closely related to lambda calculus and term rewriting, but it has no variable binding and no pattern matching. It is Turing complete and evaluation is deterministic. Notions like "call-by-value" and "call-by-name" computation are available by choosing appropriate function definitions: e.g. there is a call-by-value and a call-by-name addition function. In the present paper we extend CC with types, to be able to define data types in a canonical way, and functions over these data types, defined by iteration. Data type definitions follow the so-called "Scott encoding" of data, as opposed to the more familiar "Church encoding". The iteration scheme comes in two flavors: a call-by-value and a call-by-name iteration scheme. The call-by-value variant is a double negation variant of call-by-name iteration. The double negation translation allows to move between call-by-name and call-by-value.
How constructive is constructing measures?
Venue: arXiv cs.LO 2014
Year: 2014

Given some set, how hard is it to construct a measure supported by it? We classify some variations of this task in the Weihrauch lattice. Particular attention is paid to Frostman measures on sets with positive Hausdorff dimension. As a side result, the Weihrauch degree of Hausdorff dimension itself is determined.
On Minimax Optimal Offline Policy Evaluation
Venue: arXiv cs.AI 2014
Year: 2014

This paper studies the off-policy evaluation problem, where one aims to estimate the value of a target policy based on a sample of observations collected by another policy. We first consider the multi-armed bandit case, establish a minimax risk lower bound, and analyze the risk of two standard estimators. It is shown, and verified in simulation, that one is minimax optimal up to a constant, while another can be arbitrarily worse, despite its empirical success and popularity. The results are applied to related problems in contextual bandits and fixed-horizon Markov decision processes, and are also related to semi-supervised learning.
A novel recovery mechanism enabling fine-granularity locking and fast, REDO-only recovery
Venue: arXiv cs.DB 2014
Year: 2014

We present a series of novel techniques and algorithms for transaction commit, logging, recovery, and propagation control. In combination, they provide a recovery component that maintains the persistent state of the database (both log and data pages) always in a committed state. Recovery from system and media failures only requires only REDO operations, which can happen concurrently with the processing of new transactions. The mechanism supports fine-granularity locking, partial rollbacks, and snapshot isolation for reader transactions. Our design does not assume a specific hardware configuration such as non-volatile RAM or flash---it is designed for traditional disk environments. Nevertheless, it can exploit modern I/O devices for higher transaction throughput and reduced recovery time with a high degree of flexibility.