OpenRaiser/Intern-Atlas huggingface dataset:
Interplay: Dispersed Activation in Neural Networks
Venue: arXiv cs.NE 2012
Year: 2012

This paper presents a multi-point stimulation of a Hebbian neural network with investigation of the interplay between the stimulus waves through the neurons of the network. Equilibrium of the resulting memory is achieved for recall of specific memory data at a rate faster than single point stimulus. The interplay of the intersecting stimuli appears to parallel the clarification process of recall in biological systems.
Time After Time: Notes on Delays In Spiking Neural P Systems
Venue: arXiv cs.NE 2012
Year: 2012

Spiking Neural P systems, SNP systems for short, are biologically inspired computing devices based on how neurons perform computations. SNP systems use only one type of symbol, the spike, in the computations. Information is encoded in the time differences of spikes or the multiplicity of spikes produced at certain times. SNP systems with delays (associated with rules) and those without delays are two of several Turing complete SNP system variants in literature. In this work we investigate how restricted forms of SNP systems with delays can be simulated by SNP systems without delays. We show the simulations for the following spike routing constructs: sequential, iteration, join, and split.
Textural Approach to Palmprint Identification
Venue: arXiv cs.CV 2012
Year: 2012

Biometrics which use of human physiological characteristics for identifying an individual is now a widespread method of identification and authentication. Biometric identification is a technology which uses several image processing techniques and describes the general procedure for identification and verification using feature extraction, storage and matching from the digitized image of biometric characters such as Finger Print, Face, Iris or Palm Print. The current paper uses palm print biometrics. Here we have presented an identification approach using textural properties of palm print images. The elegance of the method is that the conventional edge detection technique is extended to suitably describe the texture features. In this technique all the characteristics of the palm such as principal lines, edges and wrinkles are considered with equal importance.
Network Localization by Shadow Edges
Venue: arXiv cs.SY 2012
Year: 2012

Localization is a fundamental task for sensor networks. Traditional network construction approaches allow to obtain localized networks requiring the nodes to be at least tri-connected (in 2D), i.e., the communication graph needs to be globally rigid. In this paper we exploit, besides the information on the neighbors sensed by each robot/sensor, also the information about the lack of communication among nodes. The result is a framework where the nodes are required to be bi-connected and the communication graph has to be rigid. This is possible considering a novel typology of link, namely Shadow Edges, that account for the lack of communication among nodes and allow to reduce the uncertainty associated to the position of the nodes.
Resilient Source Coding
Venue: arXiv cs.IT 2012
Year: 2012

This paper provides a source coding theorem for multi-dimensional information signals when, at a given instant, the distribution associated with one arbitrary component of the signal to be compressed is not known and a side information is available at the destination. This new framework appears to be both of information-theoretical and game-theoretical interest: it provides a new type of constraints to compress an information source; it is useful for designing certain types of mediators in games and characterize utility regions for games with signals. Regarding the latter aspect, we apply the derived source coding theorem to the prisoner's dilemma and the battle of the sexes.
Elaborating Inductive Definitions
Venue: arXiv cs.PL 2012
Year: 2012

We present an elaboration of inductive definitions down to a universe of datatypes. The universe of datatypes is an internal presentation of strictly positive families within type theory. By elaborating an inductive definition -- a syntactic artifact -- to its code -- its semantics -- we obtain an internalized account of inductives inside the type theory itself: we claim that reasoning about inductive definitions could be carried in the type theory, not in the meta-theory as it is usually the case. Besides, we give a formal specification of that elaboration process. It is therefore amenable to formal reasoning too. We prove the soundness of our translation and hint at its correctness with respect to Coq's Inductive definitions. The practical benefits of this approach are numerous. For the type theorist, this is a small step toward bootstrapping, ie. implementing the inductive fragment in the type theory itself. For the programmer, this means better support for generic programming: we shall present a lightweight deriving mechanism, entirely definable by the programmer and therefore not requiring any extension to the type theory.
Neural Networks for Complex Data
Venue: arXiv cs.NE 2012
Year: 2012

Artificial neural networks are simple and efficient machine learning tools. Defined originally in the traditional setting of simple vector data, neural network models have evolved to address more and more difficulties of complex real world problems, ranging from time evolving data to sophisticated data structures such as graphs and functions. This paper summarizes advances on those themes from the last decade, with a focus on results obtained by members of the SAMM team of Université Paris 1
Advanced Automata Minimization
Venue: arXiv cs.FL 2012
Year: 2012

We present an efficient algorithm to reduce the size of nondeterministic Buchi word automata, while retaining their language. Additionally, we describe methods to solve PSPACE-complete automata problems like universality, equivalence and inclusion for much larger instances (1-3 orders of magnitude) than before. This can be used to scale up applications of automata in formal verification tools and decision procedures for logical theories. The algorithm is based on new transition pruning techniques. These use criteria based on combinations of backward and forward trace inclusions. Since these relations are themselves PSPACE-complete, we describe methods to compute good approximations of them in polynomial time. Extensive experiments show that the average-case complexity of our algorithm scales quadratically. The size reduction of the automata depends very much on the class of instances, but our algorithm consistently outperforms all previous techniques by a wide margin. We tested our algorithm on Buchi automata derived from LTL-formulae, many classes of random automata and automata derived from mutual exclusion protocols, and compared its performance to the well-known automata tool GOAL.
Measure What Should be Measured: Progress and Challenges in Compressive Sensing
Venue: arXiv cs.IT 2012
Year: 2012

Is compressive sensing overrated? Or can it live up to our expectations? What will come after compressive sensing and sparsity? And what has Galileo Galilei got to do with it? Compressive sensing has taken the signal processing community by storm. A large corpus of research devoted to the theory and numerics of compressive sensing has been published in the last few years. Moreover, compressive sensing has inspired and initiated intriguing new research directions, such as matrix completion. Potential new applications emerge at a dazzling rate. Yet some important theoretical questions remain open, and seemingly obvious applications keep escaping the grip of compressive sensing. In this paper I discuss some of the recent progress in compressive sensing and point out key challenges and opportunities as the area of compressive sensing and sparse representations keeps evolving. I also attempt to assess the long-term impact of compressive sensing.
An upper bound on relaying over capacity based on channel simulation
Venue: arXiv cs.IT 2012
Year: 2012

The upper bound on the capacity of a 3-node discrete memoryless relay channel is considered, where a source X wants to send information to destination Y with the help of a relay Z. Y and Z are independent given X, and the link from Z to Y is lossless with rate $R_0$. A new inequality is introduced to upper-bound the capacity when the encoding rate is beyond the capacities of both individual links XY and XZ. It is based on generalization of the blowing-up lemma, linking conditional entropy to decoding error, and channel simulation, to the case with side information. The achieved upper-bound is strictly better than the well-known cut-set bound in several cases when the latter is $C_{XY}+R_0$, with $C_{XY}$ being the channel capacity between X and Y. One particular case is when the channel is statistically degraded, i.e., either Y is a statistically degraded version of Z with respect to X, or Z is a statistically degraded version of Y with respect to X. Moreover in this case, the bound is shown to be explicitly computable. The binary erasure channel is analyzed in detail and evaluated numerically.
Adaptive Modulation in OSA-based Cognitive Radio Networks
Venue: arXiv cs.NI 2012
Year: 2012

Opportunistic spectrum access is based on channel state information and can lead to important performance improvements for the underlying communication systems. On the other hand adaptive modulation is also based on channel state information and can achieve increased transmission rates in fading channels. In this work we propose the combination of adaptive modulation with opportunistic spectrum access and we study the anticipated effects on the performance of wireless communication systems in terms of achieved spectral efficiency and power consumption.
Well-Covered Graphs Without Cycles of Lengths 4, 5 and 6
Venue: arXiv cs.DM 2012
Year: 2012

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space. Given an input graph G without cycles of length 4, 5, and 6, we characterize polynomially the vector space of weight functions w for which G is w-well-covered. Let B be an induced complete bipartite subgraph of G on vertex sets of bipartition B_{X} and B_{Y}. Assume that there exists an independent set S such that both the union of S and B_{X} and the union of S and B_{Y} are maximal independent sets of G. Then B is a generating subgraph of G, and it produces the restriction w(B_{X})=w(B_{Y}). It is known that for every weight function w, if G is w-well-covered, then the above restriction is satisfied. In the special case, where B_{X}={x} and B_{Y}={y}, we say that xy is a relating edge. Recognizing relating edges and generating subgraphs is an NP-complete problem. However, we provide a polynomial algorithm for recognizing generating subgraphs of an input graph without cycles of length 5, 6 and 7. We also present a polynomial algorithm for recognizing relating edges in an input graph without cycles of length 5 and 6.
On Construction of a Class of Orthogonal Arrays (Thesis)
Venue: arXiv cs.DM 2012
Year: 2012

We propose a novel method for the construction of orthogonal arrays. The algorithm makes use of the Kronecker Product operator in association with unit column vectors to generate new orthogonal arrays from existing orthogonal arrays. The effectiveness of the proposed algorithm lies in the fact that it works well with any linear seed orthogonal array without imposing any constraints on the strength or the number of levels. The resulting orthogonal array has the same strength as the seed orthogonal array. We also discuss the proof of correctness of the algorithm. In the Results section we provide a list of new orthogonal arrays generated using this algorithm, that are currently not present in the libraries of orthogonal arrays.
Building on the DEPLOY Legacy: Code Generation and Simulation
Venue: arXiv cs.SE 2012
Year: 2012

The RODIN, and DEPLOY projects laid solid foundations for further theoretical, and practical (methodological and tooling) advances with Event-B. Our current interest is the co-simulation of cyber-physical systems using Event-B. Using this approach we aim to simulate various features of the environment separately, in order to exercise deployable code. This paper has two contributions, the first is the extension of the code generation work of DEPLOY, where we add the ability to generate code from Event-B state-machine diagrams. The second describes how we may use code, generated from state-machines, to simulate the environment, and simulate concurrently executing state-machines, in a single task. We show how we can instrument the code to guide the simulation, by controlling the relative rate that non-deterministic transitions are traversed in the simulation.
3D Face Recognition using Significant Point based SULD Descriptor
Venue: arXiv cs.CV 2012
Year: 2012

In this work, we present a new 3D face recognition method based on Speeded-Up Local Descriptor (SULD) of significant points extracted from the range images of faces. The proposed model consists of a method for extracting distinctive invariant features from range images of faces that can be used to perform reliable matching between different poses of range images of faces. For a given 3D face scan, range images are computed and the potential interest points are identified by searching at all scales. Based on the stability of the interest point, significant points are extracted. For each significant point we compute the SULD descriptor which consists of vector made of values from the convolved Haar wavelet responses located on concentric circles centred on the significant point, and where the amount of Gaussian smoothing is proportional to the radii of the circles. Experimental results show that the newly proposed method provides higher recognition rate compared to other existing contemporary models developed for 3D face recognition.
Index notation of grid graphs
Venue: arXiv cs.CG 2012
Year: 2012

By defining grids as graphs, geometric graphs can be represented in a very concise way.
The star and biclique coloring and choosability problems
Venue: arXiv cs.DM 2012
Year: 2012

A biclique of a graph G is an induced complete bipartite graph. A star of G is a biclique contained in the closed neighborhood of a vertex. A star (biclique) k-coloring of G is a k-coloring of G that contains no monochromatic maximal stars (bicliques). Similarly, for a list assignment L of G, a star (biclique) L-coloring is an L-coloring of G in which no maximal star (biclique) is monochromatic. If G admits a star (biclique) L-coloring for every k-list assignment L, then G is said to be star (biclique) k-choosable. In this article we study the computational complexity of the star and biclique coloring and choosability problems. Specifically, we prove that the star (biclique) k-coloring and k-choosability problems are Σ_2^p-complete and Π_3^p-complete for k > 2, respectively, even when the input graph contains no induced C_4 or K_{k+2}. Then, we study all these problems in some related classes of graphs, including H-free graphs for every H on three vertices, graphs with restricted diamonds, split graphs, threshold graphs, and net-free block graphs.
Joint Doppler frequency shift compensation and data detection method using 2-D unitary ESPRIT algorithm for SIMO-OFDM railway communication systems
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we present a joint Doppler frequency shift compensation and data detection method using 2-D unitary ESPRIT algorithm for SIMO-OFDM railway communication systems over fast time-varying sparse multipath channels. By creating the spatio-temporal array data matrix utilizing the ISI-free part of the CP (cyclic prefix), we first propose a novel algorithm for obtaining auto-paired joint DOA and Doppler frequency shift estimates of all paths via 2-D unitary ESPRIT algorithm. Thereafter, based on the obtained estimates, a joint Doppler frequency shift compensation and data detection method is developed. This method consists of three parts: (a) the received signal is spatially filtered to get the signal corresponding to each path, and the signal corresponding to each path is compensated for the Doppler frequency shift in time domain, (b) the Doppler frequency shift-compensated signals of all paths are summed together, and (c) the desired information is detected by performing FFT on the summed signal after excluding the CP. Moreover, we prove that the channel matrix becomes time-invariant after Doppler frequency shift compensation and the ICI is effectively avoided. Finally, simulation results are presented to demonstrate the performance of the proposed method and compare it with the conventional method.
Joint Viterbi Decoding and Decision Feedback Equalization for Monobit Digital Receivers
Venue: arXiv cs.IT 2012
Year: 2012

In ultra-wideband (UWB) communication systems with impulse radio (IR) modulation, the bandwidth is usually 1GHz or more. To process the received signal digitally, high sampling rate analog-digital-converters (ADC) are required. Due to the high complexity and large power consumption, monobit ADC is appropriate. The optimal monobit receiver has been derived. But it is not efficient to combat intersymbol interference (ISI). Decision feedback equalization (DFE) is an effect way dealing with ISI. In this paper, we proposed a algorithm that combines Viterbi decoding and DFE together for monobit receivers. In this way, we suppress the impact of ISI effectively, thus improving the bit error rate (BER) performance. By state expansion, we achieve better performance. The simulation results show that the algorithm has about 1dB SNR gain compared to separate demodulation and decoding method and 1dB loss compared to the BER performance in the channel without ISI. Compare to the full resolution detection in fading channel without ISI, it has 3dB SNR loss after state expansion.
Feedback Allocation For OFDMA Systems With Slow Frequency-domain Scheduling
Venue: arXiv cs.IT 2012
Year: 2012

We study the problem of allocating limited feedback resources across multiple users in an orthogonal-frequency-division-multiple-access downlink system with slow frequency-domain scheduling. Many flavors of slow frequency-domain scheduling (e.g., persistent scheduling, semi-persistent scheduling), that adapt user-sub-band assignments on a slower time-scale, are being considered in standards such as 3GPP Long-Term Evolution. In this paper, we develop a feedback allocation algorithm that operates in conjunction with any arbitrary slow frequency-domain scheduler with the goal of improving the throughput of the system. Given a user-sub-band assignment chosen by the scheduler, the feedback allocation algorithm involves solving a weighted sum-rate maximization at each (slow) scheduling instant. We first develop an optimal dynamic-programming-based algorithm to solve the feedback allocation problem with pseudo-polynomial complexity in the number of users and in the total feedback bit budget. We then propose two approximation algorithms with complexity further reduced, for scenarios where the problem exhibits additional structure.
Study on the Availability Prediction of the Reconfigurable Networked Software System
Venue: arXiv cs.MA 2012
Year: 2012

This paper describes multi-agent based availability prediction approach for the reconfigurable networked software system.
List-coloring embedded graphs
Venue: arXiv cs.DS 2012
Year: 2012

For any fixed surface Sigma of genus g, we give an algorithm to decide whether a graph G of girth at least five embedded in Sigma is colorable from an assignment of lists of size three in time O(|V(G)|). Furthermore, we can allow a subgraph (of any size) with at most s components to be precolored, at the expense of increasing the time complexity of the algorithm to O(|V(G)|^{K(g+s)+1}) for some absolute constant K; in both cases, the multiplicative constant hidden in the O-notation depends on g and s. This also enables us to find such a coloring when it exists. The idea of the algorithm can be applied to other similar problems, e.g., 5-list-coloring of graphs on surfaces.
The fortresses of Ejin: an example of outlining a site from satellite images
Venue: arXiv cs.CV 2012
Year: 2012

From 1960's to 1970's, the Chinese Army built some fortified artificial hills. Some of them are located in the Inner Mongolia, Western China. These large fortresses are surrounded by moats. For some of them it is still possible to see earthworks, trenches and ditches, the planning of which could have a symbolic meaning. We can argue this result form their digital outlining, obtained after an image processing of satellite images, based on edge detection.
Computing Petaflops over Terabytes of Data: The Case of Genome-Wide Association Studies
Venue: arXiv cs.MS 2012
Year: 2012

In many scientific and engineering applications, one has to solve not one but a sequence of instances of the same problem. Often times, the problems in the sequence are linked in a way that allows intermediate results to be reused. A characteristic example for this class of applications is given by the Genome-Wide Association Studies (GWAS), a widely spread tool in computational biology. GWAS entails the solution of up to trillions ($10^{12}$) of correlated generalized least-squares problems, posing a daunting challenge: the performance of petaflops ($10^{15}$ floating-point operations) over terabytes of data. In this paper, we design an algorithm for performing GWAS on multi-core architectures. This is accomplished in three steps. First, we show how to exploit the relation among successive problems, thus reducing the overall computational complexity. Then, through an analysis of the required data transfers, we identify how to eliminate any overhead due to input/output operations. Finally, we study how to decompose computation into tasks to be distributed among the available cores, to attain high performance and scalability. With our algorithm, a GWAS that currently requires the use of a supercomputer may now be performed in matter of hours on a single multi-core node. The discussion centers around the methodology to develop the algorithm rather than the specific application. We believe the paper contributes valuable guidelines of general applicability for computational scientists on how to develop and optimize numerical algorithms.
Square-Root Finding Problem In Graphs, A Complete Dichotomy Theorem
Venue: arXiv cs.DM 2012
Year: 2012

Graph G is the square of graph H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Given H it is easy to compute its square H^2. Determining if a given graph G is the square of some graph is not easy in general. Motwani and Sudan proved that it is NP-complete to determine if a given graph G is the square of some graph. The graph introduced in their reduction is a graph that contains many triangles and is relatively dense. Farzad et al. proved the NP-completeness for finding a square root for girth 4 while they gave a polynomial time algorithm for computing a square root of girth at least six. Adamaszek and Adamaszek proved that if a graph has a square root of girth six then this square root is unique up to isomorphism. In this paper we consider the characterization and recognition problem of graphs that are square of graphs of girth at least five. We introduce a family of graphs with exponentially many non-isomorphic square roots, and as the main result of this paper we prove that the square root finding problem is NP-complete for square roots of girth five. This proof is providing the complete dichotomy theorem for square root problem in terms of the girth of the square roots.