OpenRaiser/Intern-Atlas huggingface dataset:
Neural network to identify individuals at health risk
Venue: arXiv cs.NE 2011
Year: 2011

The risk of diseases such as heart attack and high blood pressure could be reduced by adequate physical activity. However, even though majority of general population claims to perform some physical exercise, only a minority exercises enough to keep a healthy living style. Thus, physical inactivity has become one of the major concerns of public health in the past decade. Research shows that the highest decrease in physical activity is noticed from high school to college. Thus, it is of great importance to quickly identify college students at health risk due to physical inactivity. Research also shows that the level of physical activity of an individual is highly correlated to demographic features such as race and gender, as well as self motivation and support from family and friends. This information could be collected from each student via a 20 minute questionnaire, but the time needed to distribute and analyze each questionnaire is infeasible on a collegiate campus. Thus, we propose an automatic identifier of students at risk, so that these students could easier be targeted by collegiate campuses and physical activity promotion departments. We present in this paper preliminary results of a supervised backpropagation multilayer neural network for classifying students into at-risk or not at-risk group.
"Eppur si muove", Software Libero e Ricerca Riproducibile
Venue: arXiv cs.CY 2011
Year: 2011

This article describes similarities of the scientific method and the free open source software development, and how reproducibility is the key of an healthy scientific production.
Algebra-Logical Repair Method for FPGA Logic Blocks
Venue: arXiv cs.AR 2011
Year: 2011

An algebra-logical repair method for FPGA functional logic blocks on the basis of solving the coverage problem is proposed. It is focused on implementation into Infrastructure IP for system-on-a chip and system-in-package. A method is designed for providing the operability of FPGA blocks and digital system as a whole. It enables to obtain exact and optimal solution associated with the minimum number of spares needed to repair the FPGA logic components with multiple faults.
On Symmetry of Independence Polynomials
Venue: arXiv cs.DM 2011
Year: 2011

An independent set in a graph is a set of pairwise non-adjacent vertices, and alpha(G) is the size of a maximum independent set in the graph G. A matching is a set of non-incident edges, while mu(G) is the cardinality of a maximum matching. If s_{k} is the number of independent sets of cardinality k in G, then I(G;x)=s_{0}+s_{1}x+s_{2}x^{2}+...+s_{α(G)}x^{α(G)} is called the independence polynomial of G (Gutman and Harary, 1983). If $s_{j}=s_{α-j}$, 0=< j =< alpha(G), then I(G;x) is called symmetric (or palindromic). It is known that the graph G*2K_{1} obtained by joining each vertex of G to two new vertices, has a symmetric independence polynomial (Stevanovic, 1998). In this paper we show that for every graph G and for each non-negative integer k =< mu(G), one can build a graph H, such that: G is a subgraph of H, I(H;x) is symmetric, and I(G*2K_{1};x)=(1+x)^{k}*I(H;x).
Steady Marginality: A Uniform Approach to Shapley Value for Games with Externalities
Venue: arXiv cs.GT 2011
Year: 2011

The Shapley value is one of the most important solution concepts in cooperative game theory. In coalitional games without externalities, it allows to compute a unique payoff division that meets certain desirable fairness axioms. However, in many realistic applications where externalities are present, Shapley's axioms fail to indicate such a unique division. Consequently, there are many extensions of Shapley value to the environment with externalities proposed in the literature built upon additional axioms. Two important such extensions are "externality-free" value by Pham Do and Norde and value that "absorbed all externalities" by McQuillin. They are good reference points in a space of potential payoff divisions for coalitional games with externalities as they limit the space at two opposite extremes. In a recent, important publication, De Clippel and Serrano presented a marginality-based axiomatization of the value by Pham Do Norde. In this paper, we propose a dual approach to marginality which allows us to derive the value of McQuillin. Thus, we close the picture outlined by De Clippel and Serrano.
Analysis of Power-aware Buffering Schemes in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

We study the power-aware buffering problem in battery-powered sensor networks, focusing on the fixed-size and fixed-interval buffering schemes. The main motivation is to address the yet poorly understood size variation-induced effect on power-aware buffering schemes. Our theoretical analysis elucidates the fundamental differences between the fixed-size and fixed-interval buffering schemes in the presence of data size variation. It shows that data size variation has detrimental effects on the power expenditure of the fixed-size buffering in general, and reveals that the size variation induced effects can be either mitigated by a positive skewness or promoted by a negative skewness in size distribution. By contrast, the fixed-interval buffering scheme has an obvious advantage of being eminently immune to the data-size variation. Hence the fixed-interval buffering scheme is a risk-averse strategy for its robustness in a variety of operational environments. In addition, based on the fixed-interval buffering scheme, we establish the power consumption relationship between child nodes and parent node in a static data collection tree, and give an in-depth analysis of the impact of child bandwidth distribution on parent's power consumption. This study is of practical significance: it sheds new light on the relationship among power consumption of buffering schemes, power parameters of radio module and memory bank, data arrival rate and data size variation, thereby providing well-informed guidance in determining an optimal buffer size (interval) to maximize the operational lifespan of sensor networks.
Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
Venue: arXiv cs.DS 2011
Year: 2011

We present two on-line algorithms for maintaining a topological order of a directed $n$-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles $m$ arc additions in $O(m^{3/2})$ time. For sparse graphs ($m/n = O(1)$), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural {\em locality} property. Our second algorithm handles an arbitrary sequence of arc additions in $O(n^{5/2})$ time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take $Ω(n^2 2^{\sqrt{2\lg n}})$ time by relating its performance to a generalization of the $k$-levels problem of combinatorial geometry. A completely different algorithm running in $Θ(n^2 \log n)$ time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.
A Multiple Component Matching Framework for Person Re-Identification
Venue: arXiv cs.CV 2011
Year: 2011

Person re-identification consists in recognizing an individual that has already been observed over a network of cameras. It is a novel and challenging research topic in computer vision, for which no reference framework exists yet. Despite this, previous works share similar representations of human body based on part decomposition and the implicit concept of multiple instances. Building on these similarities, we propose a Multiple Component Matching (MCM) framework for the person re-identification problem, which is inspired by Multiple Component Learning, a framework recently proposed for object detection. We show that previous techniques for person re-identification can be considered particular implementations of our MCM framework. We then present a novel person re-identification technique as a direct, simple implementation of our framework, focused in particular on robustness to varying lighting conditions, and show that it can attain state of the art performances.
On the Cross-Correlation of a Ternary $m$-sequence of Period $3^{4k}-1$ and Its Decimated Sequence by $\frac{(3^{2k}+1)^{2}}{20}$
Venue: arXiv cs.IT 2011
Year: 2011

Let $d=\frac{(3^{2k}+1)^{2}}{20}$, where $k$ is an odd integer. We show that the magnitude of the cross-correlation values of a ternary $m$-sequence $\{s_{t}\}$ of period $3^{4k}-1$ and its decimated sequence $\{s_{dt}\}$ is upper bounded by $5\sqrt{3^{n}}+1$, where $n=4k$.
Feature Selection for MAUC-Oriented Classification Systems
Venue: arXiv cs.LG 2011
Year: 2011

Feature selection is an important pre-processing step for many pattern classification tasks. Traditionally, feature selection methods are designed to obtain a feature subset that can lead to high classification accuracy. However, classification accuracy has recently been shown to be an inappropriate performance metric of classification systems in many cases. Instead, the Area Under the receiver operating characteristic Curve (AUC) and its multi-class extension, MAUC, have been proved to be better alternatives. Hence, the target of classification system design is gradually shifting from seeking a system with the maximum classification accuracy to obtaining a system with the maximum AUC/MAUC. Previous investigations have shown that traditional feature selection methods need to be modified to cope with this new objective. These methods most often are restricted to binary classification problems only. In this study, a filter feature selection method, namely MAUC Decomposition based Feature Selection (MDFS), is proposed for multi-class classification problems. To the best of our knowledge, MDFS is the first method specifically designed to select features for building classification systems with maximum MAUC. Extensive empirical results demonstrate the advantage of MDFS over several compared feature selection methods.
Generating Similar Graphs From Spherical Features
Venue: arXiv cs.SI 2011
Year: 2011

We propose a novel model for generating graphs similar to a given example graph. Unlike standard approaches that compute features of graphs in Euclidean space, our approach obtains features on a surface of a hypersphere. We then utilize a von Mises-Fisher distribution, an exponential family distribution on the surface of a hypersphere, to define a model over possible feature values. While our approach bears similarity to a popular exponential random graph model (ERGM), unlike ERGMs, it does not suffer from degeneracy, a situation when a significant probability mass is placed on unrealistic graphs. We propose a parameter estimation approach for our model, and a procedure for drawing samples from the distribution. We evaluate the performance of our approach both on the small domain of all 8-node graphs as well as larger real-world social networks.
On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters
Venue: arXiv cs.FL 2011
Year: 2011

We give lower bounds on the growth rate of Dejean words, i.e. minimally repetitive words, over a k-letter alphabet, for k=5, 6, 7, 8, 9, 10. Put together with the known upper bounds, we estimate these growth rates with the precision of 0,005. As an consequence, we establish the exponential growth of the number of Dejean words over a k-letter alphabet, for k=5, 6, 7, 8, 9, 10.
Rigid components in fixed-lattice and cone frameworks
Venue: arXiv cs.DS 2011
Year: 2011

We study the fundamental algorithmic rigidity problems for generic frameworks periodic with respect to a fixed lattice or a finite-order rotation in the plane. For fixed-lattice frameworks we give an $O(n^2)$ algorithm for deciding generic rigidity and an O(n^3) algorithm for computing rigid components. If the order of rotation is part of the input, we give an O(n^4) algorithm for deciding rigidity; in the case where the rotation's order is 3, a more specialized algorithm solves all the fundamental algorithmic rigidity problems in O(n^2) time.
Double Blind Comparisons using Groups with Infeasible Inversion
Venue: arXiv cs.CR 2011
Year: 2011

Double Blind Comparison is a new cryptographic primitive that allows a user who is in possession of a ciphertext to determine if the corresponding plaintext is identical to the plaintext for a different ciphertext held by a different user, but only if both users co-operate. Neither user knows anything about the plaintexts corresponding to either ciphertext, and neither user learns anything about the plaintexts as a result of the comparison, other than whether the two plaintexts are identical. Neither user can determine whether the plaintexts are equal without the other user's co-operation. Double Blind Comparisons have potential application in Anonymous Credentials and the Database Aggregation Problem. This paper shows how Double Blind Comparisons can be implemented using a Strong Associative One-Way Function (SAOWF). Proof of security is given, making an additional assumption that the SAOWF is implemented on a Group with Infeasible Inversion (GII), whose existence was postulated by Hohenberger and Molnar.
On Rényi and Tsallis entropies and divergences for exponential families
Venue: arXiv cs.IT 2011
Year: 2011

Many common probability distributions in statistics like the Gaussian, multinomial, Beta or Gamma distributions can be studied under the unified framework of exponential families. In this paper, we prove that both Rényi and Tsallis divergences of distributions belonging to the same exponential family admit a generic closed form expression. Furthermore, we show that Rényi and Tsallis entropies can also be calculated in closed-form for sub-families including the Gaussian or exponential distributions, among others.
Scholarly Communication
Venue: arXiv cs.DL 2011
Year: 2011

The chapter tackles the role of scholarly publication in the research process (quality, preservation) and looks at the consequences of new information technologies in the organization of the scholarly communication ecology. It will then show how new technologies have had an impact on the scholarly communication process and made it depart from the traditional publishing environment. Developments will address new editorial processes, dissemination of new content and services, as well as the development of publication archives. This last aspect will be covered on all levels (open access, scientific, technical and legal aspects). A view on the possible evolutions of the scientific publishing environment will be provided.
Xampling at the Rate of Innovation
Venue: arXiv cs.IT 2011
Year: 2011

We address the problem of recovering signals from samples taken at their rate of innovation. Our only assumption is that the sampling system is such that the parameters defining the signal can be stably determined from the samples, a condition that lies at the heart of every sampling theorem. Consequently, our analysis subsumes previously studied nonlinear acquisition devices and nonlinear signal classes. In particular, we do not restrict attention to memoryless nonlinear distortions or to union-of-subspace models. This allows treatment of various finite-rate-of-innovation (FRI) signals that were not previously studied, including, for example, continuous phase modulation transmissions. Our strategy relies on minimizing the error between the measured samples and those corresponding to our signal estimate. This least-squares (LS) objective is generally non-convex and might possess many local minima. Nevertheless, we prove that under the stability hypothesis, any optimization method designed to trap a stationary point of the LS criterion necessarily converges to the true solution. We demonstrate our approach in the context of recovering pulse streams in settings that were not previously treated. Furthermore, in situations for which other algorithms are applicable, we show that our method is often preferable in terms of noise robustness.
On the Tradeoff Between Multiuser Diversity and Training Overhead in Multiple Access Channels
Venue: arXiv cs.IT 2011
Year: 2011

We consider a single antenna narrowband multiple access channel in which users send training sequences to the base station and scheduling is performed based on minimum mean square error (MMSE) channel estimates. In such a system, there is an inherent tradeoff between training overhead and the amount of multiuser diversity achieved. We analyze a block fading channel with independent Rayleigh distributed channel gains, where the parameters to be optimized are the number of users considered for transmission in each block and the corresponding time and power spent on training by each user. We derive closed form expressions for the optimal parameters in terms K and L, where K is the number of users considered for transmission in each block and L is the block length in symbols. Considering the behavior of the system as L grows large, we optimize K with respect to an approximate expression for the achievable rate, and obtain second order expressions for the resulting parameters in terms of L.
Invariant Representative Cocycles of Cohomology Generators using Irregular Graph Pyramids
Venue: arXiv cs.CV 2011
Year: 2011

Structural pattern recognition describes and classifies data based on the relationships of features and parts. Topological invariants, like the Euler number, characterize the structure of objects of any dimension. Cohomology can provide more refined algebraic invariants to a topological space than does homology. It assigns `quantities' to the chains used in homology to characterize holes of any dimension. Graph pyramids can be used to describe subdivisions of the same object at multiple levels of detail. This paper presents cohomology in the context of structural pattern recognition and introduces an algorithm to efficiently compute representative cocycles (the basic elements of cohomology) in 2D using a graph pyramid. An extension to obtain scanning and rotation invariant cocycles is given.
Chain Homotopies for Object Topological Representations
Venue: arXiv cs.DM 2011
Year: 2011

This paper presents a set of tools to compute topological information of simplicial complexes, tools that are applicable to extract topological information from digital pictures. A simplicial complex is encoded in a (non-unique) algebraic-topological format called AM-model. An AM-model for a given object K is determined by a concrete chain homotopy and it provides, in particular, integer (co)homology generators of K and representative (co)cycles of these generators. An algorithm for computing an AM-model and the cohomological invariant HB1 (derived from the rank of the cohomology ring) with integer coefficients for a finite simplicial complex in any dimension is designed here. A concept of generators which are "nicely" representative cycles is also presented. Moreover, we extend the definition of AM-models to 3D binary digital images and we design algorithms to update the AM-model information after voxel set operations (union, intersection, difference and inverse).
Where are my followers? Understanding the Locality Effect in Twitter
Venue: arXiv cs.SI 2011
Year: 2011

Twitter is one of the most used applications in the current Internet with more than 200M accounts created so far. As other large-scale systems Twitter can obtain enefit by exploiting the Locality effect existing among its users. In this paper we perform the first comprehensive study of the Locality effect of Twitter. For this purpose we have collected the geographical location of around 1M Twitter users and 16M of their followers. Our results demonstrate that language and cultural characteristics determine the level of Locality expected for different countries. Those countries with a different language than English such as Brazil typically show a high intra-country Locality whereas those others where English is official or co-official language suffer from an external Locality effect. This is, their users have a larger number of followers in US than within their same country. This is produced by two reasons: first, US is the dominant country in Twitter counting with around half of the users, and second, these countries share a common language and cultural characteristics with US.
Typical models: minimizing false beliefs
Venue: arXiv cs.AI 2011
Year: 2011

A knowledge system S describing a part of real world does in general not contain complete information. Reasoning with incomplete information is prone to errors since any belief derived from S may be false in the present state of the world. A false belief may suggest wrong decisions and lead to harmful actions. So an important goal is to make false beliefs as unlikely as possible. This work introduces the notions of "typical atoms" and "typical models", and shows that reasoning with typical models minimizes the expected number of false beliefs over all ways of using incomplete information. Various properties of typical models are studied, in particular, correctness and stability of beliefs suggested by typical models, and their connection to oblivious reasoning.
Protocols for Relay-Assisted Free-Space Optical Systems
Venue: arXiv cs.IT 2011
Year: 2011

We investigate transmission protocols for relay-assisted free-space optical (FSO) systems, when multiple parallel relays are employed and there is no direct link between the source and the destination. As alternatives to all-active FSO relaying, where all the available relays transmit concurrently, we propose schemes that select only a single relay to participate in the communication between the source and the destination in each transmission slot. This selection is based on the channel state information (CSI) obtained either from all or from some of the FSO links. Thus, the need for synchronizing the relays' transmissions is avoided and the slowly varying nature of the atmospheric channel is exploited. For both relay selection and all-active relaying, novel closed-form expressions for their outage performance are derived, assuming the versatile Gamma-Gamma channel model. Furthermore, based on the derived analytical results, the problem of allocating the optical power resources to the FSO links is addressed, and optimum and suboptimum solutions are proposed. Numerical results are provided for equal and non-equal length FSO links, which illustrate the outage behavior of the considered relaying protocols and demonstrate the significant performance gains offered by the proposed power allocation schemes.