OpenRaiser/Intern-Atlas huggingface dataset:
Game Theory with Translucent Players
Venue: arXiv cs.GT 2013
Year: 2013

A traditional assumption in game theory is that players are opaque to one another -- if a player changes strategies, then this change in strategies does not affect the choice of other players' strategies. In many situations this is an unrealistic assumption. We develop a framework for reasoning about games where the players may be translucent to one another; in particular, a player may believe that if she were to change strategies, then the other player would also change strategies. Translucent players may achieve significantly more efficient outcomes than opaque ones. Our main result is a characterization of strategies consistent with appropriate analogues of common belief of rationality. Common Counterfactual Belief of Rationality (CCBR) holds if (1) everyone is rational, (2) everyone counterfactually believes that everyone else is rational (i.e., all players i believe that everyone else would still be rational even if i were to switch strategies), (3) everyone counterfactually believes that everyone else is rational, and counterfactually believes that everyone else is rational, and so on. CCBR characterizes the set of strategies surviving iterated removal of minimax dominated strategies: a strategy $σ_i$ is minimax dominated for i if there exists a strategy $σ'_i$ for i such that $\min_{μ'_{-i}} u_i(σ_i, μ_{-i}') > \max_{μ_{-i}} u_i(σ_i, μ_{-i})$.
An Epistemic Approach to Compositional Reasoning about Anonymity and Privacy
Venue: arXiv cs.CR 2013
Year: 2013

In this paper, we present an epistemic logic approach to the compositionality of several privacy-related informationhiding/ disclosure properties. The properties considered here are anonymity, privacy, onymity, and identity. Our initial observation reveals that anonymity and privacy are not necessarily sequentially compositional; this means that even though a system comprising several sequential phases satisfies a certain unlinkability property in each phase, the entire system does not always enjoy a desired unlinkability property. We show that the compositionality can be guaranteed provided that the phases of the system satisfy what we call the independence assumptions. More specifically, we develop a series of theoretical case studies of what assumptions are sufficient to guarantee the sequential compositionality of various degrees of anonymity, privacy, onymity, and/or identity properties. Similar results for parallel composition are also discussed.
Simulating the Influence of Collaborative Networks on the Structure of Networks of Organizations, Employment Structure, and Organization Value
Venue: arXiv cs.SI 2013
Year: 2013

From the perspective of reindustrialization, it is important to understand the evolution of the structure of the network of organizations employment structure, and organization value. Understanding the potential influence of collaborative networks (CNs) on these aspects may lead to the development of appropriate economic policies. In this paper, we propose a theoretical approach to analysis this potential influence, based on a model of dynamic networked ecosystem of organizations encompassing collaboration relations among organization, employment mobility, and organization value. A large number of simulations has been performed to identify factors influencing the structure of the network of organizations employment structure, and organization value. The main findings are that 1) the higher the number of members of CNs, the better the clustering and the shorter the average path length among organizations; 2) the constitution of CNs does not affect neither the structure of the network of organizations, nor the employment structure and the organization value.
Randomized co-training: from cortical neurons to machine learning and back again
Venue: arXiv cs.LG 2013
Year: 2013

Despite its size and complexity, the human cortex exhibits striking anatomical regularities, suggesting there may simple meta-algorithms underlying cortical learning and computation. We expect such meta-algorithms to be of interest since they need to operate quickly, scalably and effectively with little-to-no specialized assumptions. This note focuses on a specific question: How can neurons use vast quantities of unlabeled data to speed up learning from the comparatively rare labels provided by reward systems? As a partial answer, we propose randomized co-training as a biologically plausible meta-algorithm satisfying the above requirements. As evidence, we describe a biologically-inspired algorithm, Correlated Nystrom Views (XNV) that achieves state-of-the-art performance in semi-supervised learning, and sketch work in progress on a neuronal implementation.
A Hierarchical Dynamic Programming Algorithm for Optimal Coalition Structure Generation
Venue: arXiv cs.MA 2013
Year: 2013

We present a new Dynamic Programming (DP) formulation of the Coalition Structure Generation (CSG) problem based on imposing a hierarchical organizational structure over the agents. We show the efficiency of this formulation by deriving DyPE, a new optimal DP algorithm which significantly outperforms current DP approaches in speed and memory usage. In the classic case, in which all coalitions are feasible, DyPE has half the memory requirements of other DP approaches. On graph-restricted CSG, in which feasibility is restricted by a (synergy) graph, DyPE has either the same or lower computational complexity depending on the underlying graph structure of the problem. Our empirical evaluation shows that DyPE outperforms the state-of-the-art DP approaches by several orders of magnitude in a large range of graph structures (e.g. for certain scalefree graphs DyPE reduces the memory requirements by $10^6$ and solves problems that previously needed hours in minutes).
Curiosity Based Exploration for Learning Terrain Models
Venue: arXiv cs.RO 2013
Year: 2013

We present a robotic exploration technique in which the goal is to learn to a visual model and be able to distinguish between different terrains and other visual components in an unknown environment. We use ROST, a realtime online spatiotemporal topic modeling framework to model these terrains using the observations made by the robot, and then use an information theoretic path planning technique to define the exploration path. We conduct experiments with aerial view and underwater datasets with millions of observations and varying path lengths, and find that paths that are biased towards locations with high topic perplexity produce better terrain models with high discriminative power, especially with paths of length close to the diameter of the world.
Sockpuppet Detection in Wikipedia: A Corpus of Real-World Deceptive Writing for Linking Identities
Venue: arXiv cs.CL 2013
Year: 2013

This paper describes the corpus of sockpuppet cases we gathered from Wikipedia. A sockpuppet is an online user account created with a fake identity for the purpose of covering abusive behavior and/or subverting the editing regulation process. We used a semi-automated method for crawling and curating a dataset of real sockpuppet investigation cases. To the best of our knowledge, this is the first corpus available on real-world deceptive writing. We describe the process for crawling the data and some preliminary results that can be used as baseline for benchmarking research. The dataset will be released under a Creative Commons license from our project website: http://docsig.cis.uab.edu.
IC3 Modulo Theories via Implicit Predicate Abstraction
Venue: arXiv cs.LO 2013
Year: 2013

We present a novel approach for generalizing the IC3 algorithm for invariant checking from finite-state to infinite-state transition systems, expressed over some background theories. The procedure is based on a tight integration of IC3 with Implicit (predicate) Abstraction, a technique that expresses abstract tran- sitions without computing explicitly the abstract system and is incremental with respect to the addition of predicates. In this scenario, IC3 operates only at the Boolean level of the abstract state space, discovering inductive clauses over the abstraction predicates. Theory reasoning is confined within the underlying SMT solver, and applied transparently when performing satisfiability checks. When the current abstraction allows for a spurious counterexample, it is refined by discov- ering and adding a sufficient set of new predicates. Importantly, this can be done in a completely incremental manner, without discarding the clauses found in the previous search. The proposed approach has two key advantages. First, unlike current SMT gener- alizations of IC3, it allows to handle a wide range of background theories without relying on ad-hoc extensions, such as quantifier elimination or theory-specific clause generalization procedures, which might not always be available, and can moreover be inefficient. Second, compared to a direct exploration of the concrete transition system, the use of abstraction gives a significant performance improve- ment, as our experiments demonstrate.
Managing Heterogeneous WSNs in Smart Cities: Challenges and Requirements
Venue: arXiv cs.NI 2013
Year: 2013

The dramatic advances in wireless communications and electronics have enabled the development of Wireless Sensor Networks (WSNs). WSNs consist of many affordable and portable sensor nodes for collecting data from the environment. In this article, we address management requirements of WSNs through presenting some key management scenarios in the Smart Cities context, such as intelligent transportation systems, smart grids and smart buildings. The limited resources and heterogeneous characteristics of WSNs pose new challenges in network management, which include the presence of various faults, the difficulty in replacing and repairing a large number of sensor nodes, the existence of an uncertain topology, and the resource allocation. To cope with these challenges, we first discuss advantages and disadvantages of centralized and distributed management approaches and then discuss the benefit of the multilevel management schema. Next, we present in detail the specific features for a WSN management system such as lightweight, self-detection, self-configuration, sharing infrastructure, service monitoring, plug and play, context awareness and interoperability. Finally, we present the required mechanisms for some basic management functions.
Computing finite models using free Boolean generators
Venue: arXiv cs.LO 2013
Year: 2013

A parallel method for computing Boolean expressions based on the properties of finite free Boolean algebras is presented. We also show how various finite combinatorial objects can be codded in the formalism of Boolean algebras and counted by this procedure. Particularly, using a translation of first order predicate formulas to propositional formulas, we give a method for constructing and counting finite models of the first order theories. An implementation of the method that can be run on multi-core CPUs as well as on highly parallel GPUs is outlined.
Nominal Regular Expressions for Languages over Infinite Alphabets. Extended Abstract
Venue: arXiv cs.FL 2013
Year: 2013

We propose regular expressions to abstractly model and study properties of resource-aware computations. Inspired by nominal techniques -- as those popular in process calculi -- we extend classical regular expressions with names (to model computational resources) and suitable operators (for allocation, deallocation, scoping of, and freshness conditions on resources). We discuss classes of such nominal regular expressions, show how such expressions have natural interpretations in terms of languages over infinite alphabets, and give Kleene theorems to characterise their formal languages in terms of nominal automata.
Computation Over Gaussian Networks With Orthogonal Components
Venue: arXiv cs.IT 2013
Year: 2013

Function computation of arbitrarily correlated discrete sources over Gaussian networks with orthogonal components is studied. Two classes of functions are considered: the arithmetic sum function and the type function. The arithmetic sum function in this paper is defined as a set of multiple weighted arithmetic sums, which includes averaging of the sources and estimating each of the sources as special cases. The type or frequency histogram function counts the number of occurrences of each argument, which yields many important statistics such as mean, variance, maximum, minimum, median, and so on. The proposed computation coding first abstracts Gaussian networks into the corresponding modulo sum multiple-access channels via nested lattice codes and linear network coding and then computes the desired function by using linear Slepian-Wolf source coding. For orthogonal Gaussian networks (with no broadcast and multiple-access components), the computation capacity is characterized for a class of networks. For Gaussian networks with multiple-access components (but no broadcast), an approximate computation capacity is characterized for a class of networks.
Object Recognition System Design in Computer Vision: a Universal Approach
Venue: arXiv cs.CV 2013
Year: 2013

The first contribution of this paper is architecture of a multipurpose system, which delegates a range of object detection tasks to a classifier, applied in special grid positions of the tested image. The second contribution is Gray Level-Radius Co-occurrence Matrix, which describes local image texture and topology and, unlike common second order statistics methods, is robust to image resolution. The third contribution is a parametrically controlled automatic synthesis of unlimited number of numerical features for classification. The fourth contribution is a method of optimizing parameters C and gamma in LibSVM-based classifier, which is 20-100 times faster than the commonly applied method. The work is essentially experimental, with demonstration of various methods for definition of objects of interest in images and video sequences.
Weak Visibility Queries of Line Segments in Simple Polygons and Polygonal Domains
Venue: arXiv cs.CG 2013
Year: 2013

In this paper we consider the problem of computing the weak visibility polygon of any query line segment $pq$ (or $WVP(pq)$) inside a given polygon $P$. Our first non-trivial algorithm runs in simple polygons and needs $O(n^3 \log n)$ time and $O(n^3)$ space in the preprocessing phase to report $WVP(pq)$ of any query line segment $pq$ in time $O(\log n + |WVP(pq)|)$. We also give an algorithm to compute the weak visibility polygon of a query line segment in a non-simple polygon with $h$ pairwise-disjoint polygonal obstacles with a total of $n$ vertices. Our algorithm needs $O(n^2 \log n)$ time and $O(n^2)$ space in the preprocessing phase and computes $WVP(pq)$ in query time of $O(n\hbar \log n + k)$, in which $\hbar$ is an output sensitive parameter of at most $\min(h,k)$, and $k = O(n^2h^2)$ is the output size. This is the best query-time result on this problem so far.
Compressed Sensing SAR Imaging with Multilook Processing
Venue: arXiv cs.IT 2013
Year: 2013

Multilook processing is a widely used speckle reduction approach in synthetic aperture radar (SAR) imaging. Conventionally, it is achieved by incoherently summing of some independent low-resolution images formulated from overlapping subbands of the SAR signal. However, in the context of compressive sensing (CS) SAR imaging, where the samples are collected at sub-Nyquist rate, the data spectrum is highly aliased that hinders the direct application of the existing multilook techniques. In this letter, we propose a new CS-SAR imaging method that can realize multilook processing simultaneously during image reconstruction. The main idea is to replace the SAR observation matrix by the inverse of multilook procedures, which is then combined with random sampling matrix to yield a multilook CS-SAR observation model. Then a joint sparse regularization model, considering pixel dependency of subimages, is derived to form multilook images. The suggested SAR imaging method can not only reconstruct sparse scene efficiently below Nyquist rate, but is also able to achieve a comparable reduction of speckles during reconstruction. Simulation results are finally provided to demonstrate the effectiveness of the proposed method.
Input Design for Model Discrimination and Fault Detection via Convex Relaxation
Venue: arXiv cs.SY 2013
Year: 2013

This paper addresses the design of input signals for the purpose of discriminating among a finite set of models dynamic systems within a given finite time interval. A motivating application is fault detection and isolation. We propose several specific optimization problems, with objectives or constraints based on signal power, signal amplitude, and probability of successful model discrimination. Since these optimization problems are nonconvex, we suggest a suboptimal solution via a random search algorithm guided by the semidefinite relaxation (SDR) and analyze the accuracy of the suboptimal solution. We conclude with a simple example taken from a benchmark problem on fault detection for wind turbines.
Massive MIMO Systems: Signal Processing Challenges and Research Trends
Venue: arXiv cs.IT 2013
Year: 2013

This article presents a tutorial on multiuser multiple-antenna wireless systems with a very large number of antennas, known as massive multi-input multi-output (MIMO) systems. Signal processing challenges and future trends in the area of massive MIMO systems are presented and key application scenarios are detailed. A linear algebra approach is considered for the description of the system and data models of massive MIMO architectures. The operational requirements of massive MIMO systems are discussed along with their operation in time-division duplexing mode, resource allocation and calibration requirements. In particular, transmit and receiver processing algorithms are examined in light of the specific needs of massive MIMO systems. Simulation results illustrate the performance of transmit and receive processing algorithms under scenarios of interest. Key problems are discussed and future trends in the area of massive MIMO systems are pointed out.
Average Case Analysis of Java 7's Dual Pivot Quicksort
Venue: arXiv cs.DS 2013
Year: 2013

Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting method for Oracle's Java 7 runtime library. The decision for the change was based on empirical studies showing that on average, the new algorithm is faster than the formerly used classic Quicksort. Surprisingly, the improvement was achieved by using a dual pivot approach, an idea that was considered not promising by several theoretical studies in the past. In this paper, we identify the reason for this unexpected success. Moreover, we present the first precise average case analysis of the new algorithm showing e.g. that a random permutation of length $n$ is sorted using $1.9n\ln n-2.46n+\mathcal{O}(\ln n)$ key comparisons and $0.6n\ln n+0.08n+\mathcal{O}(\ln n)$ swaps.
Impulse Noise Removal In Speech Using Wavelets
Venue: arXiv cs.CV 2013
Year: 2013

A new method for removing impulse noise from speech in the wavelet transform domain is proposed. The method utilizes the multiresolution property of the wavelet transform, which provides finer time resolution at the higher frequencies than the short-time Fourier transform (STFT), to effectively identify and remove impulse noise. It uses two features of speech to discriminate speech from impulse noise: one is the slow time-varying nature of speech and the other is the Lipschitz regularity of the speech components. On the basis of these features, an algorithm has been developed to identify and suppress wavelet coefficients that correspond to impulse noise. Experiment results show that the new method is able to significantly reduce impulse noise without degrading the quality of the speech signal or introducing any audible artifacts.
Greedy Graph Colouring is a Misleading Heuristic
Venue: arXiv cs.DS 2013
Year: 2013

State of the art maximum clique algorithms use a greedy graph colouring as a bound. We show that greedy graph colouring can be misleading, which has implications for parallel branch and bound.
Compact manifolds with computable boundaries
Venue: arXiv cs.LO 2013
Year: 2013

We investigate conditions under which a co-computably enumerable closed set in a computable metric space is computable and prove that in each locally computable computable metric space each co-computably enumerable compact manifold with computable boundary is computable. In fact, we examine the notion of a semi-computable compact set and we prove a more general result: in any computable metric space each semi-computable compact manifold with computable boundary is computable. In particular, each semi-computable compact (boundaryless) manifold is computable.
IRM4MLS: the influence reaction model for multi-level simulation
Venue: arXiv cs.MA 2013
Year: 2013

In this paper, a meta-model called IRM4MLS, that aims to be a generic ground to specify and execute multi-level agent-based models is presented. It relies on the influence/reaction principle and more specifically on IRM4S. Simulation models for IRM4MLS are defined. The capabilities and possible extensions of the meta-model are discussed.
E-Business Implications for Productivity and Competitiveness
Venue: arXiv cs.OH 2013
Year: 2013

Information and Communication Technology (ICT) affects to a great extent the output and productivity growth. Evidence suggests that investment growth in ICT has rapidly accelerated the TFP (total factor productivity) growth within the European Union. Such progress is particularly essential for the sectors which themselves produce new technology, but it is dispersing to other sectors, as well. Nevertheless, decrease in ICT investment does not necessarily decline the ICT contribution to output and productivity growth. These variations come out from the problems related to the particular phenomenon proper assessment, but predominantly from the companies' special requirements, as well as the necessary adjustments of labour employed. Hence, this paper aims at estimating the huge distinction in terms of ICT and TFB contributions to labour productivity growth among some of the European member states, as well as the factors which might stand behind the particular findings.
Some Efficient Solutions to Yao's Millionaire Problem
Venue: arXiv cs.CR 2013
Year: 2013

We present three simple and efficient protocol constructions to solve Yao's Millionaire Problem when the parties involved are non-colluding and semi-honest. The first construction uses a partially homomorphic Encryption Scheme and is a 4-round scheme using 2 encryptions, 2 homomorphic circuit evaluations (subtraction and XOR) and a single decryption. The second construction uses an untrusted third party and achieves a communication overhead linear in input bit-size with the help of an order preserving function.Moreover, the second construction does not require an apriori input bound and can work on inputs of different bit-sizes. The third construction does not use a third party and, even though, it has a quadratic communication overhead, it is a fairly simple construction.
Towards an Assessment-oriented Model for External Information System Quality Characterization
Venue: arXiv cs.SE 2013
Year: 2013

Information System Quality (ISQ) management discipline requires a set of assessment mechanisms to evaluate external quality characteristics that are influenced by the environmental parameters and impacted by the ecosystem factors. The present paper suggests a new assessment oriented model that takes into consideration all facets of each external quality feature. The proposed model, named RatQual, gives a hierarchical categorization for quality. RatQual is designed to quantify dependent-environment qualities by considering internal, external and in use aspects. This model is supported by a tool that automates the assessment process. This tool gives assistance in quality evolution planning and serves for periodical monitoring operations used to enhance and improve information system quality.