OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Intrusion Detection for the Security of Societies of Robots
Venue: arXiv cs.RO 2011
Year: 2011

This paper addresses the problem of detecting possible intruders in a group of autonomous robots, which coexist in a shared environment and interact with each other according to a set of "social behaviors", or common rules. Such rules specify what actions each robot is allowed to perform in the pursuit of its individual goals: rules are distributed, i.e. they can evaluated based only on the state of the individual robot, and on information that can be sensed directly or through communication with immediate neighbors. We consider intruders as robots which misbehave, i.e. do not follow the rules, because of either spontaneous failures or malicious reprogramming. Our goal is to detect intruders by observing the congruence of their behavior with the social rules as applied to the current state of the overall system. Moreover, in accordance with the fully distributed nature of the problem, the detection itself must be peformed by individual robots, based only on local information. The paper introduces a formalism that allows to model uniformly a large variety of possible robot societies. The main contribution consists in the proposal of an Intrusion Detection System, i.e. a protocol that, under suitabkle conditions, allows individual robots to detect possible misbehaving robots in their vicinity, and trigger possible further actions to secure the society. It is worth noting that the generality of the protocol formalism makes so that local monitors can be automatically generated once the cooperation rules and the robot dynamics are specified. The effectiveness of the proposed technique is shown through application to examples of automated robotic systems.
Content-Based Filtering for Video Sharing Social Networks
Venue: arXiv cs.CV 2011
Year: 2011

In this paper we compare the use of several features in the task of content filtering for video social networks, a very challenging task, not only because the unwanted content is related to very high-level semantic concepts (e.g., pornography, violence, etc.) but also because videos from social networks are extremely assorted, preventing the use of constrained a priori information. We propose a simple method, able to combine diverse evidence, coming from different features and various video elements (entire video, shots, frames, keyframes, etc.). We evaluate our method in three social network applications, related to the detection of unwanted content - pornographic videos, violent videos, and videos posted to artificially manipulate popularity scores. Using challenging test databases, we show that this simple scheme is able to obtain good results, provided that adequate features are chosen. Moreover, we establish a representation using codebooks of spatiotemporal local descriptors as critical to the success of the method in all three contexts. This is consequential, since the state-of-the-art still relies heavily on static features for the tasks addressed.
Generalized Silver Codes
Venue: arXiv cs.IT 2011
Year: 2011

For an $n_t$ transmit, $n_r$ receive antenna system ($n_t \times n_r$ system), a {\it{full-rate}} space time block code (STBC) transmits $n_{min} = min(n_t,n_r)$ complex symbols per channel use. The well known Golden code is an example of a full-rate, full-diversity STBC for 2 transmit antennas. Its ML-decoding complexity is of the order of $M^{2.5}$ for square $M$-QAM. The Silver code for 2 transmit antennas has all the desirable properties of the Golden code except its coding gain, but offers lower ML-decoding complexity of the order of $M^2$. Importantly, the slight loss in coding gain is negligible compared to the advantage it offers in terms of lowering the ML-decoding complexity. For higher number of transmit antennas, the best known codes are the Perfect codes, which are full-rate, full-diversity, information lossless codes (for $n_r \geq n_t$) but have a high ML-decoding complexity of the order of $M^{n_tn_{min}}$ (for $n_r < n_t$, the punctured Perfect codes are considered). In this paper, a scheme to obtain full-rate STBCs for $2^a$ transmit antennas and any $n_r$ with reduced ML-decoding complexity of the order of $M^{n_t(n_{min}-(3/4))-0.5}$, is presented. The codes constructed are also information lossless for $n_r \geq n_t$, like the Perfect codes and allow higher mutual information than the comparable punctured Perfect codes for $n_r < n_t$. These codes are referred to as the {\it generalized Silver codes}, since they enjoy the same desirable properties as the comparable Perfect codes (except possibly the coding gain) with lower ML-decoding complexity, analogous to the Silver-Golden codes for 2 transmit antennas. Simulation results of the symbol error rates for 4 and 8 transmit antennas show that the generalized Silver codes match the punctured Perfect codes in error performance while offering lower ML-decoding complexity.
A Low ML-decoding Complexity, Full-diversity, Full-rate MIMO Precoder
Venue: arXiv cs.IT 2011
Year: 2011

Precoding for multiple-input, multiple-output (MIMO) antenna systems is considered with perfect channel knowledge available at both the transmitter and the receiver. For 2 transmit antennas and QAM constellations, an approximately optimal (with respect to the minimum Euclidean distance between points in the received signal space) real-valued precoder based on the singular value decomposition (SVD) of the channel is proposed, and it is shown to offer a maximum-likelihood (ML)-decoding complexity of $\mathcal{O}(\sqrt{M})$ for square $M$-QAM. The proposed precoder is obtainable easily for arbitrary QAM constellations, unlike the known complex-valued optimal precoder by Collin et al. for 2 transmit antennas, which is in existence for 4-QAM alone with an ML-decoding complexity of $\mathcal{O}(M\sqrt{M})$ (M=4) and is extremely hard to obtain for larger QAM constellations. The proposed precoder's loss in error performance for 4-QAM in comparison with the complex-valued optimal precoder is only marginal. Our precoding scheme is extended to higher number of transmit antennas on the lines of the E-$d_{min}$ precoder for 4-QAM by Vrigneau et al. which is an extension of the complex-valued optimal precoder for 4-QAM. Compared with the recently proposed $X-$ and $Y-$precoders, the error performance of our precoder is significantly better. It is shown that our precoder provides full-diversity for QAM constellations and this is supported by simulation plots of the word error probability for $2\times2$, $4\times4$ and $8\times8$ systems.
Analysis of Biometric Authentication Protocols in the Blackbox Model
Venue: arXiv cs.CR 2011
Year: 2011

In this paper we analyze different biometric authentication protocols considering an internal adversary. Our contribution takes place at two levels. On the one hand, we introduce a new comprehensive framework that encompasses the various schemes we want to look at. On the other hand, we exhibit actual attacks on recent schemes such as those introduced at ACISP 2007, ACISP 2008, and SPIE 2010, and some others. We follow a blackbox approach in which we consider components that perform operations on the biometric data they contain and where only the input/output behavior of these components is analyzed.
Bi-serial DNA Encryption Algorithm(BDEA)
Venue: arXiv cs.CR 2011
Year: 2011

The vast parallelism, exceptional energy efficiency and extraordinary information inherent in DNA molecules are being explored for computing, data storage and cryptography. DNA cryptography is a emerging field of cryptography. In this paper a novel encryption algorithm is devised based on number conversion, DNA digital coding, PCR amplification, which can effectively prevent attack. Data treatment is used to transform the plain text into cipher text which provides excellent security
Parallelization Strategies for Ant Colony Optimisation on GPUs
Venue: arXiv cs.DC 2011
Year: 2011

Ant Colony Optimisation (ACO) is an effective population-based meta-heuristic for the solution of a wide variety of problems. As a population-based algorithm, its computation is intrinsically massively parallel, and it is there- fore theoretically well-suited for implementation on Graphics Processing Units (GPUs). The ACO algorithm comprises two main stages: Tour construction and Pheromone update. The former has been previously implemented on the GPU, using a task-based parallelism approach. However, up until now, the latter has always been implemented on the CPU. In this paper, we discuss several parallelisation strategies for both stages of the ACO algorithm on the GPU. We propose an alternative data-based parallelism scheme for Tour construction, which fits better on the GPU architecture. We also describe novel GPU programming strategies for the Pheromone update stage. Our results show a total speed-up exceeding 28x for the Tour construction stage, and 20x for Pheromone update, and suggest that ACO is a potentially fruitful area for future research in the GPU domain.
Lower bound for deterministic semantic-incremental branching programs solving GEN
Venue: arXiv cs.CC 2011
Year: 2011

We answer a problem posed in (Gál, Koucký, McKenzie 2008) regarding a restricted model of small-space computation, tailored for solving the GEN problem. They define two variants of "incremental branching programs", the syntactic variant defined by a restriction on the graph-theoretic paths in the program, and the more-general semantic variant in which the same restriction is enforced only on the consistent paths - those that are followed by at least one input. They show that exponential size is required for the syntactic variant, but leave open the problem of superpolynomial lower bounds for the semantic variant. Here we give an exponential lower bound for the semantic variant by generalizing lower bound arguments, from earlier work, for a similar restricted model tailored for solving a special case of GEN called Tree Evaluation.
A Proposal to Classify Latinamerican Scientific Journals using Citation Indicators: Case Study in Colombia
Venue: arXiv cs.DL 2011
Year: 2011

Colombian scientific journals are poorly represented in international digital libraries; however, through Google Scholar (GS) it is possible to determine their use by the community. Between the years of 2003 and 2007 a classification of 185 Colombian journals indexed in the Colombian National Bibliographical Index (IBNP) was performed using the information provided by GS, basing categorization on size indicators, indexation and citation. The indicators were analyzed by grouping the journals in two general areas: sciences and social sciences. In each area, the indicators provided by the digital libraries Scopus, Redalyc and Scielo were compared. Additionally, the indicators provided by IBNP journals categories (A1, A2, B and C) were also compared. The sciences and social sciences had a similar pattern in their indicators. The existence of positive correlations was established between some indicators and they predicted that the number of citations per journal in GS and the h index depends on its visibility in GS and Scopus. We put forward that the current IBNP categories (A1, A2, B or C) faintly reflect the use of journals by the community and we propose a classification based on the h index as an infometric indicator, which reflects not only its visibility in Google Scholar, but also its inclusion in certain international digital libraries, particularly Scopus. Our results may be applied to the creation of public policies regarding science and technology in Colombia and in developing countries.
CSSF MIMO RADAR: Low-Complexity Compressive Sensing Based MIMO Radar That Uses Step Frequency
Venue: arXiv cs.IT 2011
Year: 2011

A new approach is proposed, namely CSSF MIMO radar, which applies the technique of step frequency (SF) to compressive sensing (CS) based multi-input multi-output (MIMO) radar. The proposed approach enables high resolution range, angle and Doppler estimation, while transmitting narrowband pulses. The problem of joint angle-Doppler-range estimation is first formulated to fit the CS framework, i.e., as an L1 optimization problem. Direct solution of this problem entails high complexity as it employs a basis matrix whose construction requires discretization of the angle-Doppler-range space. Since high resolution requires fine space discretization, the complexity of joint range, angle and Doppler estimation can be prohibitively high. For the case of slowly moving targets, a technique is proposed that achieves significant complexity reduction by successively estimating angle-range and Doppler in a decoupled fashion and by employing initial estimates obtained via matched filtering to further reduce the space that needs to be digitized. Numerical results show that the combination of CS and SF results in a MIMO radar system that has superior resolution and requires far less data as compared to a system that uses a matched filter with SF.
Multiplexed Model Predictive Control
Venue: arXiv cs.SY 2011
Year: 2011

This paper proposes a form of MPC in which the control variables are moved asynchronously. This contrasts with most MIMO control schemes, which assume that all variables are updated simultaneously. MPC outperforms other control strategies through its ability to deal with constraints. This requires on-line optimization, hence computational complexity can become an issue when applying MPC to complex systems with fast response times. The multiplexed MPC scheme described in this paper solves the MPC problem for each subsystem sequentially, and updates subsystem controls as soon as the solution is available, thus distributing the control moves over a complete update cycle. The resulting computational speed-up allows faster response to disturbances, which may result in improved performance, despite finding sub-optimal solutions to the original problem.
Resequencing: A Method for Conforming to Conventions for Sharing Credits Among Multiple Authors
Venue: arXiv cs.DL 2011
Year: 2011

Devising an appropriate scheme that assigns the weights to share credits among multiple authors of a paper is a challenging task. This challenge comes from the fact that different types of conventions might be followed among different research discipline or research groups. In this paper, we discuss that for the purpose of evaluating the quality of research produced by authors, one can resequence either authors or weights and can apply a weight assignment policy which the evaluator deems fit for the particular research discipline or research group.
A Robust and Secure Aggregation Protocol for Wireless Sensor Networks
Venue: arXiv cs.CR 2011
Year: 2011

The purpose of a wireless sensor network (WSN) is to provide the users with access to the information of interest from data gathered by spatially distributed sensors. Generally the users require only certain aggregate functions of this distributed data. Computation of this aggregate data under the end-to-end information flow paradigm by communicating all the relevant data to a central collector node is a highly inefficient solution for this purpose. An alternative proposition is to perform in-network computation. This, however, raises questions such as: what is the optimal way to compute an aggregate function from a set of statistically correlated values stored in different nodes; what is the security of such aggregation as the results sent by a compromised or faulty node in the network can adversely affect the accuracy of the computed result. In this paper, we have presented an energy-efficient aggregation algorithm for WSNs that is secure and robust against malicious insider attack by any compromised or faulty node in the network. In contrast to the traditional snapshot aggregation approach in WSNs, a node in the proposed algorithm instead of unicasting its sensed information to its parent node, broadcasts its estimate to all its neighbors. This makes the system more fault-tolerant and increase the information availability in the network. The simulations conducted on the proposed algorithm have produced results that demonstrate its effectiveness.
A note on the multiple unicast capacity of directed acyclic networks
Venue: arXiv cs.IT 2011
Year: 2011

We consider the multiple unicast problem under network coding over directed acyclic networks with unit capacity edges. There is a set of n source-terminal (s_i - t_i) pairs that wish to communicate at unit rate over this network. The connectivity between the s_i - t_i pairs is quantified by means of a connectivity level vector, [k_1 k_2 ... k_n] such that there exist k_i edge-disjoint paths between s_i and t_i. Our main aim is to characterize the feasibility of achieving this for different values of n and [k_1 ... k_n]. For 3 unicast connections (n = 3), we characterize several achievable and unachievable values of the connectivity 3-tuple. In addition, in this work, we have found certain network topologies, and capacity characterizations that are useful in understanding the case of general n.
Borel Hierarchy and Omega Context Free Languages
Venue: arXiv cs.LO 2011
Year: 2011

We give in this paper additional answers to questions of Lescow and Thomas [Logical Specifications of Infinite Computations, In:"A Decade of Concurrency", Springer LNCS 803 (1994), 583-621], proving new topological properties of omega context free languages : there exist some omega-CFL which are non Borel sets. And one cannot decide whether an omega-CFL is a Borel set. We give also an answer to questions of Niwinski and Simonnet about omega powers of finitary languages, giving an example of a finitary context free language L such that L^omega is not a Borel set. Then we prove some recursive analogues to preceding properties: in particular one cannot decide whether an omega-CFL is an arithmetical set.
Error-Free Multi-Valued Consensus with Byzantine Failures
Venue: arXiv cs.DC 2011
Year: 2011

In this paper, we present an efficient deterministic algorithm for consensus in presence of Byzantine failures. Our algorithm achieves consensus on an $L$-bit value with communication complexity $O(nL + n^4 L^{0.5} + n^6)$ bits, in a network consisting of $n$ processors with up to $t$ Byzantine failures, such that $t<n/3$. For large enough $L$, communication complexity of the proposed algorithm approaches $O(nL)$ bits. In other words, for large $L$, the communication complexity is linear in the number of processors in the network. This is an improvement over the work of Fitzi and Hirt (from PODC 2006), who proposed a probabilistically correct multi-valued Byzantine consensus algorithm with a similar complexity for large $L$. In contrast to the algorithm by Fitzi and Hirt, our algorithm is guaranteed to be always error-free. Our algorithm require no cryptographic technique, such as authentication, nor any secret sharing mechanism. To the best of our knowledge, we are the first to show that, for large $L$, error-free multi-valued Byzantine consensus on an $L$-bit value is achievable with $O(nL)$ bits of communication.
A Game-Theoretic View of the Interference Channel: Impact of Coordination and Bargaining
Venue: arXiv cs.IT 2011
Year: 2011

This work considers coordination and bargaining between two selfish users over a Gaussian interference channel. The usual information theoretic approach assumes full cooperation among users for codebook and rate selection. In the scenario investigated here, each user is willing to coordinate its actions only when an incentive exists and benefits of cooperation are fairly allocated. The users are first allowed to negotiate for the use of a simple Han-Kobayashi type scheme with fixed power split. Conditions for which users have incentives to cooperate are identified. Then, two different approaches are used to solve the associated bargaining problem. First, the Nash Bargaining Solution (NBS) is used as a tool to get fair information rates and the operating point is obtained as a result of an optimization problem. Next, a dynamic alternating-offer bargaining game (AOBG) from bargaining theory is introduced to model the bargaining process and the rates resulting from negotiation are characterized. The relationship between the NBS and the equilibrium outcome of the AOBG is studied and factors that may affect the bargaining outcome are discussed. Finally, under certain high signal-to-noise ratio regimes, the bargaining problem for the generalized degrees of freedom is studied.
Multiplicity Preserving Triangular Set Decomposition of Two Polynomials
Venue: arXiv cs.SC 2011
Year: 2011

In this paper, a multiplicity preserving triangular set decomposition algorithm is proposed for a system of two polynomials. The algorithm decomposes the variety defined by the polynomial system into unmixed components represented by triangular sets, which may have negative multiplicities. In the bivariate case, we give a complete algorithm to decompose the system into multiplicity preserving triangular sets with positive multiplicities. We also analyze the complexity of the algorithm in the bivariate case. We implement our algorithm and show the effectiveness of the method with extensive experiments.
Bio-inspired Methods for Dynamic Network Analysis in Science Mapping
Venue: arXiv cs.DL 2011
Year: 2011

We apply bio-inspired methods for the analysis of different dynamic bibliometric networks (linking papers by citation, authors, and keywords, respectively). Biological species are clusters of individuals defined by widely different criteria and in the biological perspective it is natural to (1) use different categorizations on the same entities (2) to compare the different categorizations and to analyze the dissimilarities, especially as they change over time. We employ the same methodology to comparisons of bibliometric classifications. We constructed them as analogs of three species concepts: cladistic or lineage based, similarity based, and "biological species" (based on co-reproductive ability). We use the Rand and Jaccard indexes to compare classifications in different time intervals. The experiment is aimed to address the classic problem of science mapping, as to what extent the various techniques based on different bibliometric indicators, such as citations, keywords or authors are able to detect convergent structures in the litrerature, that is, to identify coherent specialities or research directions and their dynamics.
U-Learning Within A Context-Aware Multiagent Environment
Venue: arXiv cs.HC 2011
Year: 2011

New technological developments have made it possible to interact with computer systems and applications anywhere and anytime. It is vital that these applications are able to adapt to the user, as a person, and to its current situation, whatever that is. Therefore, the premises for evolution towards a learning society and a knowledge economy are present. Hence, there is a stringent demand for new learner-centred frameworks that allow active participation of learners in knowledge creation within communities, organizations, territories and society, at large. This paper presents the multi-agent architecture of our context-aware system and the learning scenarios within ubiquitous learning environments that the system provides support for. This architecture is the outcome of our endeavour to develop ePH, a system for sharing public interest information and knowledge, which is accessible through always-on, context-aware services.
An Upper Bound for Signal Transmission Error Probability in Hyperbolic Spaces
Venue: arXiv cs.IT 2011
Year: 2011

We introduce and discuss the concept of Gaussian probability density function (pdf) for the n-dimensional hyperbolic space which has been proposed as an environment for coding and decoding signals. An upper bound for the error probability of signal transmission associated with the hyperbolic distance is established. The pdf and the upper bound were developed using Poincare models for the hyperbolic spaces.