OpenRaiser/Intern-Atlas huggingface dataset:
Designing Networks with Good Equilibria under Uncertainty
Venue: arXiv cs.GT 2015
Year: 2015

We consider the problem of designing network cost-sharing protocols with good equilibria under uncertainty. The underlying game is a multicast game in a rooted undirected graph with nonnegative edge costs. A set of k terminal vertices or players need to establish connectivity with the root. The social optimum is the Minimum Steiner Tree. We are interested in situations where the designer has incomplete information about the input. We propose two different models, the adversarial and the stochastic. In both models, the designer has prior knowledge of the underlying metric but the requested subset of the players is not known and is activated either in an adversarial manner (adversarial model) or is drawn from a known probability distribution (stochastic model). In the adversarial model, the designer's goal is to choose a single, universal protocol that has low Price of Anarchy (PoA) for all possible requested subsets of players. The main question we address is: to what extent can prior knowledge of the underlying metric help in the design? We first demonstrate that there exist graphs (outerplanar) where knowledge of the underlying metric can dramatically improve the performance of good network design. Then, in our main technical result, we show that there exist graph metrics, for which knowing the underlying metric does not help and any universal protocol has PoA of $Ω(\log k)$, which is tight. We attack this problem by developing new techniques that employ powerful tools from extremal combinatorics, and more specifically Ramsey Theory in high dimensional hypercubes. Then we switch to the stochastic model, where each player is independently activated. We show that there exists a randomized ordered protocol that achieves constant PoA. By using standard derandomization techniques, we produce a deterministic ordered protocol with constant PoA.
Design and implementation of an Android application (MobilitApp+) to analyze the mobility patterns of citizens in the Metropolitan Region of Barcelona
Venue: arXiv cs.CY 2015
Year: 2015

In our project we have designed an Android application to obtain mobility data of the citizens in the metropolitan area of Barcelona. Our implementation synchronously obtains in background on the one hand, periodic location updates and, on the other hand, the type of activity citizens are doing. At the end of the day, all this data is processed and sent to a server where are stored to obtain mobility patterns from citizens that could help to improve the current transportation infrastructure. MobilitApp is fully functional and stable although the results can be improved in some situations. In future releases we will implement machine learning technics to obtain significant improvements, especially in the activity recognition modules.
Towards the Design and Implementation of Aspect-Oriented Programming for Spreadsheets
Venue: arXiv cs.SE 2015
Year: 2015

A spreadsheet usually starts as a simple and single-user software artifact, but, as frequent as in other software systems, quickly evolves into a complex system developed by many actors. Often, different users work on different aspects of the same spreadsheet: while a secretary may be only involved in adding plain data to the spreadsheet, an accountant may define new business rules, while an engineer may need to adapt the spreadsheet content so it can be used by other software systems. Unfortunately, spreadsheet systems do not offer modular mechanisms, and as a consequence, some of the previous tasks may be defined by adding intrusive "code" to the spreadsheet. In this paper we go through the design and implementation of an aspect-oriented language for spreadsheets so that users can work on different aspects of a spreadsheet in a modular way. For example, aspects can be defined in order to introduce new business rules to an existing spreadsheet, or to manipulate the spreadsheet data to be ported to another system. Aspects are defined as aspect-oriented program specifications that are dynamically woven into the underlying spreadsheet by an aspect weaver. In this aspect-oriented style of spreadsheet development, different users develop, or reuse, aspects without adding intrusive code to the original spreadsheet. Such code is added/executed by the spreadsheet weaving mechanism proposed in this paper.
Properties of simple sets in digital spaces. Contractions of simple sets preserving the homotopy type of a digital space
Venue: arXiv cs.CV 2015
Year: 2015

A point of a digital space is called simple if it can be deleted from the space without altering topology. This paper introduces the notion simple set of points of a digital space. The definition is based on contractible spaces and contractible transformations. A set of points in a digital space is called simple if it can be contracted to a point without changing topology of the space. It is shown that contracting a simple set of points does not change the homotopy type of a digital space, and the number of points in a digital space without simple points can be reduces by contracting simple sets. Using the process of contracting, we can substantially compress a digital space while preserving the topology. The paper proposes a method for thinning a digital space which shows that this approach can contribute to computer science such as medical imaging, computer graphics and pattern analysis.
Appearance-based indoor localization: A comparison of patch descriptor performance
Venue: arXiv cs.CV 2015
Year: 2015

Vision is one of the most important of the senses, and humans use it extensively during navigation. We evaluated different types of image and video frame descriptors that could be used to determine distinctive visual landmarks for localizing a person based on what is seen by a camera that they carry. To do this, we created a database containing over 3 km of video-sequences with ground-truth in the form of distance travelled along different corridors. Using this database, the accuracy of localization - both in terms of knowing which route a user is on - and in terms of position along a certain route, can be evaluated. For each type of descriptor, we also tested different techniques to encode visual structure and to search between journeys to estimate a user's position. The techniques include single-frame descriptors, those using sequences of frames, and both colour and achromatic descriptors. We found that single-frame indexing worked better within this particular dataset. This might be because the motion of the person holding the camera makes the video too dependent on individual steps and motions of one particular journey. Our results suggest that appearance-based information could be an additional source of navigational data indoors, augmenting that provided by, say, radio signal strength indicators (RSSIs). Such visual information could be collected by crowdsourcing low-resolution video feeds, allowing journeys made by different users to be associated with each other, and location to be inferred without requiring explicit mapping. This offers a complementary approach to methods based on simultaneous localization and mapping (SLAM) algorithms.
Switching to Learn
Venue: arXiv cs.LG 2015
Year: 2015

A network of agents attempt to learn some unknown state of the world drawn by nature from a finite set. Agents observe private signals conditioned on the true state, and form beliefs about the unknown state accordingly. Each agent may face an identification problem in the sense that she cannot distinguish the truth in isolation. However, by communicating with each other, agents are able to benefit from side observations to learn the truth collectively. Unlike many distributed algorithms which rely on all-time communication protocols, we propose an efficient method by switching between Bayesian and non-Bayesian regimes. In this model, agents exchange information only when their private signals are not informative enough; thence, by switching between the two regimes, agents efficiently learn the truth using only a few rounds of communications. The proposed algorithm preserves learnability while incurring a lower communication cost. We also verify our theoretical findings by simulation examples.
Online Matrix Completion and Online Robust PCA
Venue: arXiv cs.IT 2015
Year: 2015

This work studies two interrelated problems - online robust PCA (RPCA) and online low-rank matrix completion (MC). In recent work by Candès et al., RPCA has been defined as a problem of separating a low-rank matrix (true data), $L:=[\ell_1, \ell_2, \dots \ell_{t}, \dots , \ell_{t_{\max}}]$ and a sparse matrix (outliers), $S:=[x_1, x_2, \dots x_{t}, \dots, x_{t_{\max}}]$ from their sum, $M:=L+S$. Our work uses this definition of RPCA. An important application where both these problems occur is in video analytics in trying to separate sparse foregrounds (e.g., moving objects) and slowly changing backgrounds. While there has been a large amount of recent work on both developing and analyzing batch RPCA and batch MC algorithms, the online problem is largely open. In this work, we develop a practical modification of our recently proposed algorithm to solve both the online RPCA and online MC problems. The main contribution of this work is that we obtain correctness results for the proposed algorithms under mild assumptions. The assumptions that we need are: (a) a good estimate of the initial subspace is available (easy to obtain using a short sequence of background-only frames in video surveillance); (b) the $\ell_t$'s obey a `slow subspace change' assumption; (c) the basis vectors for the subspace from which $\ell_t$ is generated are dense (non-sparse); (d) the support of $x_t$ changes by at least a certain amount at least every so often; and (e) algorithm parameters are appropriately set
Human Factors in Software Reliability Engineering
Venue: arXiv cs.SE 2015
Year: 2015

In this paper, we present our vision of the integration of human factors engineering into the software development process. The aim of this approach is to improve the quality of software and to deal with human errors in a systematic way.
Efficient Learning of Linear Separators under Bounded Noise
Venue: arXiv cs.LG 2015
Year: 2015

We study the learnability of linear separators in $\Re^d$ in the presence of bounded (a.k.a Massart) noise. This is a realistic generalization of the random classification noise model, where the adversary can flip each example $x$ with probability $η(x) \leq η$. We provide the first polynomial time algorithm that can learn linear separators to arbitrarily small excess error in this noise model under the uniform distribution over the unit ball in $\Re^d$, for some constant value of $η$. While widely studied in the statistical learning theory community in the context of getting faster convergence rates, computationally efficient algorithms in this model had remained elusive. Our work provides the first evidence that one can indeed design algorithms achieving arbitrarily small excess error in polynomial time under this realistic noise model and thus opens up a new and exciting line of research. We additionally provide lower bounds showing that popular algorithms such as hinge loss minimization and averaging cannot lead to arbitrarily small excess error under Massart noise, even under the uniform distribution. Our work instead, makes use of a margin based technique developed in the context of active learning. As a result, our algorithm is also an active learning algorithm with label complexity that is only a logarithmic the desired excess error $ε$.
Detection Algorithms for Molecular MIMO
Venue: arXiv cs.ET 2015
Year: 2015

In this paper, we propose a novel design for molecular communication in which both the transmitter and the receiver have, in a 3-dimensional environment, multiple bulges (in RF communication this corresponds to antenna). The proposed system consists of a fluid medium, information molecules, a transmitter, and a receiver. We simulate the system with a one-shot signal to obtain the channel's finite impulse response. We then incorporate this result within our mathematical analysis to determine interference. Molecular communication has a great need for low complexity, hence, the receiver may have incomplete information regarding the system and the channel state. Thus, for the cases of limited information set at the receiver, we propose three detection algorithms, namely adaptive thresholding, practical zero forcing, and Genie-aided zero forcing.
The Discrete Cosine Transform over Prime Finite Fields
Venue: arXiv cs.DM 2015
Year: 2015

This paper examines finite field trigonometry as a tool to construct trigonometric digital transforms. In particular, by using properties of the k-cosine function over GF(p), the Finite Field Discrete Cosine Transform (FFDCT) is introduced. The FFDCT pair in GF(p) is defined, having blocklengths that are divisors of (p+1)/2. A special case is the Mersenne FFDCT, defined when p is a Mersenne prime. In this instance blocklengths that are powers of two are possible and radix-2 fast algorithms can be used to compute the transform.
Learning to Detect Vehicles by Clustering Appearance Patterns
Venue: arXiv cs.CV 2015
Year: 2015

This paper studies efficient means for dealing with intra-category diversity in object detection. Strategies for occlusion and orientation handling are explored by learning an ensemble of detection models from visual and geometrical clusters of object instances. An AdaBoost detection scheme is employed with pixel lookup features for fast detection. The analysis provides insight into the design of a robust vehicle detection system, showing promise in terms of detection performance and orientation estimation accuracy.
Are there intelligent Turing machines?
Venue: arXiv cs.AI 2015
Year: 2015

This paper introduces a new computing model based on the cooperation among Turing machines called orchestrated machines. Like universal Turing machines, orchestrated machines are also designed to simulate Turing machines but they can also modify the original operation of the included Turing machines to create a new layer of some kind of collective behavior. Using this new model we can define some interested notions related to cooperation ability of Turing machines such as the intelligence quotient or the emotional intelligence quotient for Turing machines.
Constructing and Employing Tree Alignment Graphs for Phylogenetic Synthesis
Venue: arXiv cs.DS 2015
Year: 2015

Tree alignment graphs (TAGs) provide an intuitive data structure for storing phylogenetic trees that exhibits the relationships of the individual input trees and can potentially account for nested taxonomic relationships. This paper provides a theoretical foundation for the use of TAGs in phylogenetics. We provide a formal definition of TAG that - unlike previous definition - does not depend on the order in which input trees are provided. In the consensus case, when all input trees have the same leaf labels, we describe algorithms for constructing majority-rule and strict consensus trees using the TAG. When the input trees do not have identical sets of leaf labels, we describe how to determine if the input trees are compatible and, if they are compatible, to construct a supertree that contains the input trees.
Intelligent Device Used by an Infotmation System for Identifying and Monitoring of Patients
Venue: arXiv cs.CY 2015
Year: 2015

The aim of this paper consists in defining the hardware and software architecture of an embedded system, based on RFID technology, in order to identify patients and to achieve real time information concerning the patients biometric data, which might be used in different points of the health system (laboratory, family physician, etc.).
On Minimizing the Average Packet Decoding Delay in Wireless Network Coded Broadcast
Venue: arXiv cs.IT 2015
Year: 2015

We consider a setting in which a sender wishes to broadcast a block of K data packets to a set of wireless receivers, where each of the receivers has a subset of the data packets already available to it (e.g., from prior transmissions) and wants the rest of the packets. Our goal is to find a linear network coding scheme that yields the minimum average packet decoding delay (APDD), i.e., the average time it takes for a receiver to decode a data packet. Our contributions can be summarized as follows. First, we prove that this problem is NP-hard by presenting a reduction from the hypergraph coloring problem. Next, we show that %\alexn{an MDS-based solution or} a random linear network coding (RLNC) provides an approximate solution to this problem with approximation ratio $2$ with high probability. Next, we present a methodology for designing specialized approximation algorithms for this problem that outperform RLNC solutions while maintaining the same throughput. In a special case of practical interest with a small number of wanted packets our solution can achieve an approximation ratio (4-2/K)/3. Finally, we conduct an experimental study that demonstrates the advantages of the presented methodology.
Generalized Spatial Modulation in Large-Scale Multiuser MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

Generalized spatial modulation (GSM) uses $n_t$ transmit antenna elements but fewer transmit radio frequency (RF) chains, $n_{rf}$. Spatial modulation (SM) and spatial multiplexing are special cases of GSM with $n_{rf}=1$ and $n_{rf}=n_t$, respectively. In GSM, in addition to conveying information bits through $n_{rf}$ conventional modulation symbols (for example, QAM), the indices of the $n_{rf}$ active transmit antennas also convey information bits. In this paper, we investigate {\em GSM for large-scale multiuser MIMO communications on the uplink}. Our contributions in this paper include: ($i$) an average bit error probability (ABEP) analysis for maximum-likelihood detection in multiuser GSM-MIMO on the uplink, where we derive an upper bound on the ABEP, and ($ii$) low-complexity algorithms for GSM-MIMO signal detection and channel estimation at the base station receiver based on message passing. The analytical upper bounds on the ABEP are found to be tight at moderate to high signal-to-noise ratios (SNR). The proposed receiver algorithms are found to scale very well in complexity while achieving near-optimal performance in large dimensions. Simulation results show that, for the same spectral efficiency, multiuser GSM-MIMO can outperform multiuser SM-MIMO as well as conventional multiuser MIMO, by about 2 to 9 dB at a bit error rate of $10^{-3}$. Such SNR gains in GSM-MIMO compared to SM-MIMO and conventional MIMO can be attributed to the fact that, because of a larger number of spatial index bits, GSM-MIMO can use a lower-order QAM alphabet which is more power efficient.
Synthesis of all Maximum Length Cellular Automata of Cell Size up to 12
Venue: arXiv cs.OH 2015
Year: 2015

Maximum length CA has wide range of applications in design of linear block code, cryptographic primitives and VLSI testing particularly in Built-In-Self-Test. In this paper, an algorithm to compute all $n$-cell maximum length CA-rule vectors is proposed. Also rule vectors for each primitive polynomial in GF(2^2) to GF(2^{12} have been computed by simulation and they have been listed.Programmable rule vectors based maximum length CA can be used to design cryptographic primitives.
Characterizing driving behavior using automatic visual analysis
Venue: arXiv cs.CV 2015
Year: 2015

In this work, we present the problem of rash driving detection algorithm using a single wide angle camera sensor, particularly useful in the Indian context. To our knowledge this rash driving problem has not been addressed using Image processing techniques (existing works use other sensors such as accelerometer). Car Image processing literature, though rich and mature, does not address the rash driving problem. In this work-in-progress paper, we present the need to address this problem, our approach and our future plans to build a rash driving detector.
Enron versus EUSES: A Comparison of Two Spreadsheet Corpora
Venue: arXiv cs.SE 2015
Year: 2015

Spreadsheets are widely used within companies and often form the basis for business decisions. Numerous cases are known where incorrect information in spreadsheets has lead to incorrect decisions. Such cases underline the relevance of research on the professional use of spreadsheets. Recently a new dataset became available for research, containing over 15.000 business spreadsheets that were extracted from the Enron E-mail Archive. With this dataset, we 1) aim to obtain a thorough understanding of the characteristics of spreadsheets used within companies, and 2) compare the characteristics of the Enron spreadsheets with the EUSES corpus which is the existing state of the art set of spreadsheets that is frequently used in spreadsheet studies. Our analysis shows that 1) the majority of spreadsheets are not large in terms of worksheets and formulas, do not have a high degree of coupling, and their formulas are relatively simple; 2) the spreadsheets from the EUSES corpus are, with respect to the measured characteristics, quite similar to the Enron spreadsheets.
Virtual sectorization: design and self-optimization
Venue: arXiv cs.NI 2015
Year: 2015

Virtual Sectorization (ViSn) aims at covering a confined area such as a traffic hot-spot using a narrow beam. The beam is generated by a remote antenna array located at-or close to the Base Station (BS). This paper develops the ViSn model and provides the guidelines for designing the Virtual Sector (ViS) antenna. In order to mitigate interference between the ViS and the traditional macro sector covering the rest of the area, a Dynamic Spectrum Allocation (DSA) algorithm that self-optimizes the frequency bandwidth split between the macro cell and the ViS is also proposed. The Self-Organizing Network (SON) algorithm is constructed to maximize the proportional fair utility of all the users throughputs. Numerical simulations show the interest in deploying ViSn, and the significant capacity gain brought about by the self-optimized bandwidth sharing with respect to a full reuse of the bandwidth by the ViS.
A Minimal Active Inference Agent
Venue: arXiv cs.AI 2015
Year: 2015

Research on the so-called "free-energy principle'' (FEP) in cognitive neuroscience is becoming increasingly high-profile. To date, introductions to this theory have proved difficult for many readers to follow, but it depends mainly upon two relatively simple ideas: firstly that normative or teleological values can be expressed as probability distributions (active inference), and secondly that approximate Bayesian reasoning can be effectively performed by gradient descent on model parameters (the free-energy principle). The notion of active inference is of great interest for a number of disciplines including cognitive science and artificial intelligence, as well as cognitive neuroscience, and deserves to be more widely known. This paper attempts to provide an accessible introduction to active inference and informational free-energy, for readers from a range of scientific backgrounds. In this work introduce an agent-based model with an agent trying to make predictions about its position in a one-dimensional discretized world using methods from the FEP.