OpenRaiser/Intern-Atlas huggingface dataset:
On the Structure of Equilibria in Basic Network Formation
Venue: arXiv cs.GT 2013
Year: 2013

We study network connection games where the nodes of a network perform edge swaps in order to improve their communication costs. For the model proposed by Alon et al. (2010), in which the selfish cost of a node is the sum of all shortest path distances to the other nodes, we use the probabilistic method to provide a new, structural characterization of equilibrium graphs. We show how to use this characterization in order to prove upper bounds on the diameter of equilibrium graphs in terms of the size of the largest $k$-vicinity (defined as the the set of vertices within distance $k$ from a vertex), for any $k \geq 1$ and in terms of the number of edges, thus settling positively a conjecture of Alon et al. in the cases of graphs of large $k$-vicinity size (including graphs of large maximum degree) and of graphs which are dense enough. Next, we present a new swap-based network creation game, in which selfish costs depend on the immediate neighborhood of each node; in particular, the profit of a node is defined as the sum of the degrees of its neighbors. We prove that, in contrast to the previous model, this network creation game admits an exact potential, and also that any equilibrium graph contains an induced star. The existence of the potential function is exploited in order to show that an equilibrium can be reached in expected polynomial time even in the case where nodes can only acquire limited knowledge concerning non-neighboring nodes.
A DeterministicWorst-Case Message Complexity Optimal Solution for Resource Discovery
Venue: arXiv cs.DC 2013
Year: 2013

We consider the problem of resource discovery in distributed systems. In particular we give an algorithm, such that each node in a network discovers the address of any other node in the network. We model the knowledge of the nodes as a virtual overlay network given by a directed graph such that complete knowledge of all nodes corresponds to a complete graph in the overlay network. Although there are several solutions for resource discovery, our solution is the first that achieves worst-case optimal work for each node, i.e. the number of addresses (O(n)) or bits (O(n log n)) a node receives or sends coincides with the lower bound, while ensuring only a linear runtime (O(n)) on the number of rounds.
Performing Informetric Analysis on Information Retrieval Test Collections: Preliminary Experiments in the Physics Domain
Venue: arXiv cs.IR 2013
Year: 2013

The combination of informetric analysis and information retrieval allows a twofold application. (1) While in-formetrics analysis is primarily used to gain insights into a scientific domain, it can be used to build recommen-dation or alternative ranking services. They are usually based on methods like co-occurrence or citation analyses. (2) Information retrieval and its decades-long tradition of rigorous evaluation using standard document corpora, predefined topics and relevance judgements can be used as a test bed for informetric analyses. We show a preliminary experiment on how both domains can be connected using the iSearch test collection, a standard information retrieval test collection derived from the open access arXiv.org preprint server. In this paper the aim is to draw a conclusion about the appropriateness of iSearch as a test bed for the evaluation of a retrieval or recommendation system that applies informetric methods to improve retrieval results for the user. Based on an interview study with physicists, bibliographic coupling and author-co-citation analysis, important authors for ten different research questions are identified. The results show that the analysed corpus includes these authors and their corresponding documents. This study is a first step towards a combination of retrieval evaluations and the evaluation of informetric analyses methods.
Are Happy Developers more Productive? The Correlation of Affective States of Software Developers and their self-assessed Productivity
Venue: arXiv cs.SE 2013
Year: 2013

For decades now, it has been claimed that a way to improve software developers' productivity is to focus on people. Indeed, while human factors have been recognized in Software Engineering research, few empirical investigations have attempted to verify the claim. Development tasks are undertaken through cognitive processing abilities. Affective states - emotions, moods, and feelings - have an impact on work-related behaviors, cognitive processing activities, and the productivity of individuals. In this paper, we report an empirical study on the impact of affective states on software developers' performance while programming. Two affective states dimensions are positively correlated with self-assessed productivity. We demonstrate the value of applying psychometrics in Software Engineering studies and echo a call to valorize the human, individualized aspects of software developers. We introduce and validate a measurement instrument and a linear mixed-effects model to study the correlation of affective states and the productivity of software developers.
A Factor Graph Approach to Joint OFDM Channel Estimation and Decoding in Impulsive Noise Environments
Venue: arXiv cs.IT 2013
Year: 2013

We propose a novel receiver for orthogonal frequency division multiplexing (OFDM) transmissions in impulsive noise environments. Impulsive noise arises in many modern wireless and wireline communication systems, such as Wi-Fi and powerline communications, due to uncoordinated interference that is much stronger than thermal noise. We first show that the bit-error-rate optimal receiver jointly estimates the propagation channel coefficients, the noise impulses, the finite-alphabet symbols, and the unknown bits. We then propose a near-optimal yet computationally tractable approach to this joint estimation problem using loopy belief propagation. In particular, we merge the recently proposed "generalized approximate message passing" (GAMP) algorithm with the forward-backward algorithm and soft-input soft-output decoding using a "turbo" approach. Numerical results indicate that the proposed receiver drastically outperforms existing receivers under impulsive noise and comes within 1 dB of the matched-filter bound. Meanwhile, with N tones, the proposed factor-graph-based receiver has only O(N log N) complexity, and it can be parallelized.
Decomposition Lemmas
Venue: arXiv cs.DM 2013
Year: 2013

We define two recursive functions obtained by decomposition of a given interval into four close parts and prove two lemmas which determine features of these functions.
A Solution of Simultaneous Recurrences
Venue: arXiv cs.DM 2013
Year: 2013

The paper is devoted to the methods of solving simultaneous recurrences. Specifically, we discuss transformation of matrix recurrences to regular recurrences and propose a way of solving special matrix recurrences of order three by their decomposition to matrix recurrences of order two.
A Framework for Software-as-a-Service Selection and Provisioning
Venue: arXiv cs.DC 2013
Year: 2013

As cloud computing is increasingly transforming the information technology landscape, organizations and businesses are exhibiting strong interest in Software-as-a-Service (SaaS) offerings that can help them increase business agility and reduce their operational costs. They increasingly demand services that can meet their functional and non-functional requirements. Given the plethora and the variety of SaaS offerings, we propose, in this paper, a framework for SaaS provisioning, which relies on brokered Service Level agreements (SLAs), between service consumers and SaaS providers. The Cloud Service Broker (CSB) helps service consumers find the right SaaS providers that can fulfil their functional and non-functional requirements. The proposed selection algorithm ranks potential SaaS providers by matching their offerings against the requirements of the service consumer using an aggregate utility function. Furthermore, the CSB is in charge of conducting SLA negotiation with selected SaaS providers, on behalf of service consumers, and performing SLA compliance monitoring.
Speckle Reduction with Adaptive Stack Filters
Venue: arXiv cs.CV 2013
Year: 2013

Stack filters are a special case of non-linear filters. They have a good performance for filtering images with different types of noise while preserving edges and details. A stack filter decomposes an input image into stacks of binary images according to a set of thresholds. Each binary image is then filtered by a Boolean function, which characterizes the filter. Adaptive stack filters can be computed by training using a prototype (ideal) image and its corrupted version, leading to optimized filters with respect to a loss function. In this work we propose the use of training with selected samples for the estimation of the optimal Boolean function. We study the performance of adaptive stack filters when they are applied to speckled imagery, in particular to Synthetic Aperture Radar (SAR) images. This is done by evaluating the quality of the filtered images through the use of suitable image quality indexes and by measuring the classification accuracy of the resulting images. We used SAR images as input, since they are affected by speckle noise that makes classification a difficult task.
A Light-Weight Distributed System for the processing of Replicated Counter-like Objects
Venue: arXiv cs.DC 2013
Year: 2013

In order to increase availability in a distributed system some or all of the data items are replicated and stored at separate sites. This is an issue of key concern especially since there is such a proliferation of wireless technologies and mobile users. However, the concurrent processing of transactions at separate sites can generate inconsistencies in the stored information. We have built a distributed service that manages updates to widely deployed counter-like replicas. There are many heavy-weight distributed systems targeting large information critical applications. Our system is intentionally, relatively lightweight and useful for the somewhat reduced information critical applications. The service is built on our distributed concurrency control scheme which combines optimism and pessimism in the processing of transactions. The service allows a transaction to be processed immediately (optimistically) at any individual replica as long as the transaction satisfies a cost bound. All transactions are also processed in a concurrent pessimistic manner to ensure mutual consistency.
Detecting Useless Transitions in Pushdown Automata
Venue: arXiv cs.FL 2013
Year: 2013

Pushdown automata may contain transitions that are never used in any accepting run of the automaton. We present an algorithm for detecting such useless transitions. A finite automaton that captures the possible stack content during runs of the pushdown automaton, is first constructed in a forward procedure to determine which transitions are reachable, and then employed in a backward procedure to determine which of these transitions can lead to a final stat
Matrix Partitions of Split Graphs
Venue: arXiv cs.DM 2013
Year: 2013

Matrix partition problems generalize a number of natural graph partition problems, and have been studied for several standard graph classes. We prove that each matrix partition problem has only finitely many minimal obstructions for split graphs. Previously such a result was only known for the class of cographs. (In particular, there are matrix partition problems which have infinitely many minimal chordal obstructions.) We provide (close) upper and lower bounds on the maximum size of a minimal split obstruction. This shows for the first time that some matrices have exponential-sized minimal obstructions of any kind (not necessarily split graphs). We also discuss matrix partitions for bipartite and co-bipartite graphs.
CSI Feedback Reduction for MIMO Interference Alignment
Venue: arXiv cs.IT 2013
Year: 2013

Interference alignment (IA) is a linear precoding strategy that can achieve optimal capacity scaling at high SNR in interference networks. Most of the existing IA designs require full channel state information (CSI) at the transmitters, which induces a huge CSI signaling cost. Hence it is desirable to improve the feedback efficiency for IA and in this paper, we propose a novel IA scheme with a significantly reduced CSI feedback. To quantify the CSI feedback cost, we introduce a novel metric, namely the feedback dimension. This metric serves as a first-order measurement of CSI feedback overhead. Due to the partial CSI feedback constraint, conventional IA schemes can not be applied and hence, we develop a novel IA precoder / decorrelator design and establish new IA feasibility conditions. Via dynamic feedback profile design, the proposed IA scheme can also achieve a flexible tradeoff between the degree of freedom (DoF) requirements for data streams, the antenna resources and the CSI feedback cost. We show by analysis and simulations that the proposed scheme achieves substantial reductions of CSI feedback overhead under the same DoF requirement in MIMO interference networks.
A Numerical Example about the Geometric Approach to the Output Regulation Problem with Stability for Linear Switching Systems
Venue: arXiv cs.SY 2013
Year: 2013

This note presents a numerical example worked out in order to illustrate the solution to the output regulation problem with quadratic stability for linear switching systems derived in [1].
Metro-Line Crossing Minimization: Hardness, Approximations, and Tractable Cases
Venue: arXiv cs.DS 2013
Year: 2013

Crossing minimization is one of the central problems in graph drawing. Recently, there has been an increased interest in the problem of minimizing crossings between paths in drawings of graphs. This is the metro-line crossing minimization problem (MLCM): Given an embedded graph and a set L of simple paths, called lines, order the lines on each edge so that the total number of crossings is minimized. So far, the complexity of MLCM has been an open problem. In contrast, the problem variant in which line ends must be placed in outermost position on their edges (MLCM-P) is known to be NP-hard. Our main results answer two open questions: (i) We show that MLCM is NP-hard. (ii) We give an $O(\sqrt{\log |L|})$-approximation algorithm for MLCM-P.
Privacy and Mechanism Design
Venue: arXiv cs.GT 2013
Year: 2013

This paper is a survey of recent work at the intersection of mechanism design and privacy. The connection is a natural one, but its study has been jump-started in recent years by the advent of differential privacy, which provides a rigorous, quantitative way of reasoning about the costs that an agent might experience because of the loss of his privacy. Here, we survey several facets of this study, and differential privacy plays a role in more than one way. Of course, it provides us a basis for modeling agent costs for privacy, which is essential if we are to attempt mechanism design in a setting in which agents have preferences for privacy. It also provides a toolkit for controlling those costs. However, perhaps more surprisingly, it provides a powerful toolkit for controlling the stability of mechanisms in general, which yields a set of tools for designing novel mechanisms even in economic settings completely unrelated to privacy.
A Novel Approach for Single Gene Selection Using Clustering and Dimensionality Reduction
Venue: arXiv cs.CE 2013
Year: 2013

We extend the standard rough set-based approach to deal with huge amounts of numeric attributes versus small amount of available objects. Here, a novel approach of clustering along with dimensionality reduction; Hybrid Fuzzy C Means-Quick Reduct (FCMQR) algorithm is proposed for single gene selection. Gene selection is a process to select genes which are more informative. It is one of the important steps in knowledge discovery. The problem is that all genes are not important in gene expression data. Some of the genes may be redundant, and others may be irrelevant and noisy. In this study, the entire dataset is divided in proper grouping of similar genes by applying Fuzzy C Means (FCM) algorithm. A high class discriminated genes has been selected based on their degree of dependence by applying Quick Reduct algorithm based on Rough Set Theory to all the resultant clusters. Average Correlation Value (ACV) is calculated for the high class discriminated genes. The clusters which have the ACV value a s 1 is determined as significant clusters, whose classification accuracy will be equal or high when comparing to the accuracy of the entire dataset. The proposed algorithm is evaluated using WEKA classifiers and compared. Finally, experimental results related to the leukemia cancer data confirm that our approach is quite promising, though it surely requires further research.
Image segmentation by optimal and hierarchical piecewise constant approximations
Venue: arXiv cs.CV 2013
Year: 2013

Piecewise constant image approximations of sequential number of segments or clusters of disconnected pixels are treated. The method of majorizing of optimal approximation sequence by hierarchical sequence of image approximations is proposed. A generalization for multidimensional case of color and multispectral images is foreseen.
Paradigms for Parameterized Enumeration
Venue: arXiv cs.CC 2013
Year: 2013

The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity. First we define formally different notions of efficient enumeration in the context of parameterized complexity. Second we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a number of examples. These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility. The concept of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems.
Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization
Venue: arXiv cs.CC 2013
Year: 2013

We study the parameterized complexity of a broad class of problems called "local graph partitioning problems" that includes the classical fixed cardinality problems as max k-vertex cover, k-densest subgraph, etc. By developing a technique "greediness-for-parameterization", we obtain fixed parameter algorithms with respect to a pair of parameters k, the size of the solution (but not its value) and Δ, the maximum degree of the input graph. In particular, greediness-for-parameterization improves asymptotic running times for these problems upon random separation (that is a special case of color coding) and is more intuitive and simple. Then, we show how these results can be easily extended for getting standard-parameterization results (i.e., with parameter the value of the optimal solution) for a well known local graph partitioning problem.
Let's Annotate to Let Our Code Run in Parallel
Venue: arXiv cs.PL 2013
Year: 2013

This paper presents an approach that exploits Java annotations to provide meta information needed to automatically transform plain Java programs into parallel code that can be run on multicore workstation. Programmers just need to decorate the methods that will eventually be executed in parallel with standard Java annotations. Annotations are automatically processed at launch-time and parallel byte code is derived. Once in execution the program automatically retrieves the information about the executing platform and evaluates the information specified inside the annotations to transform the byte-code into a semantically equivalent multithreaded version, depending on the target architecture features. The results returned by the annotated methods, when invoked, are futures with a wait-by-necessity semantics.
Accomplishable Tasks in Knowledge Representation
Venue: arXiv cs.AI 2013
Year: 2013

Knowledge Representation (KR) is traditionally based on the logic of facts, expressed in boolean logic. However, facts about an agent can also be seen as a set of accomplished tasks by the agent. This paper proposes a new approach to KR: the notion of task logical KR based on Computability Logic. This notion allows the user to represent both accomplished tasks and accomplishable tasks by the agent. This notion allows us to build sophisticated KRs about many interesting agents, which have not been supported by previous logical languages.
Fast Search for Dynamic Multi-Relational Graphs
Venue: arXiv cs.DB 2013
Year: 2013

Acting on time-critical events by processing ever growing social media or news streams is a major technical challenge. Many of these data sources can be modeled as multi-relational graphs. Continuous queries or techniques to search for rare events that typically arise in monitoring applications have been studied extensively for relational databases. This work is dedicated to answer the question that emerges naturally: how can we efficiently execute a continuous query on a dynamic graph? This paper presents an exact subgraph search algorithm that exploits the temporal characteristics of representative queries for online news or social media monitoring. The algorithm is based on a novel data structure called the Subgraph Join Tree (SJ-Tree) that leverages the structural and semantic characteristics of the underlying multi-relational graph. The paper concludes with extensive experimentation on several real-world datasets that demonstrates the validity of this approach.
StreamWorks - A system for Dynamic Graph Search
Venue: arXiv cs.DB 2013
Year: 2013

Acting on time-critical events by processing ever growing social media, news or cyber data streams is a major technical challenge. Many of these data sources can be modeled as multi-relational graphs. Mining and searching for subgraph patterns in a continuous setting requires an efficient approach to incremental graph search. The goal of our work is to enable real-time search capabilities for graph databases. This demonstration will present a dynamic graph query system that leverages the structural and semantic characteristics of the underlying multi-relational graph.
Case Study Based Software Engineering Project Development: State of Art
Venue: arXiv cs.SE 2013
Year: 2013

This research paper designates the importance and usage of the case study approach effectively to educating and training software designers and software engineers both in academic and industry. Subsequently an account of the use of case studies based on software engineering in the education of professionals, there is a conversation of issues in training software designers and how a case teaching method can be used to state these issues. The paper describes a software project titled Online Tower Plotting System (OTPS) to develop a complete and comprehensive case study, along with supporting educational material. The case study is aimed to demonstrate a variety of software areas, modules and courses: from bachelor through masters, doctorates and even for ongoing professional development.
Fixed-to-Variable Length Resolution Coding for Target Distributions
Venue: arXiv cs.IT 2013
Year: 2013

The number of random bits required to approximate a target distribution in terms of un-normalized informational divergence is considered. It is shown that for a variable-to-variable length encoder, this number is lower bounded by the entropy of the target distribution. A fixed-to-variable length encoder is constructed using M-type quantization and Tunstall coding. It is shown that the encoder achieves in the limit an un-normalized informational divergence of zero with the number of random bits per generated symbol equal to the entropy of the target distribution. Numerical results show that the proposed encoder significantly outperforms the optimal block-to-block encoder in the finite length regime.