OpenRaiser/Intern-Atlas huggingface dataset:
Clique Separator Decomposition of Hole- and Diamond-Free Graphs and Algorithmic Consequences
Venue: arXiv cs.DM 2011
Year: 2011

Clique separator decomposition introduced by Tarjan and Whitesides is one of the most important graph decompositions. A graph is an {\em atom} if it has no clique separator. A {\em hole} is a chordless cycle with at least five vertices, and an {\em antihole} is the complement graph of a hole. A graph is {\em weakly chordal} if it is hole- and antihole-free. $K_4-e$ is also called {\em diamond}. {\em Paraglider} has five vertices four of which induce a diamond, and the fifth vertex sees exactly the two vertices of degree two in the diamond. In this paper we show that atoms of hole- and diamond-free graphs (of hole- and paraglider-free graphs, respectively) are either weakly chordal or of a very specific structure. Hole- and paraglider-free graphs are perfect graphs. The structure of their atoms leads to efficient algorithms for various problems.
Spectrum Sensing for Cognitive Radio Using Kernel-Based Learning
Venue: arXiv cs.NI 2011
Year: 2011

Kernel method is a very powerful tool in machine learning. The trick of kernel has been effectively and extensively applied in many areas of machine learning, such as support vector machine (SVM) and kernel principal component analysis (kernel PCA). Kernel trick is to define a kernel function which relies on the inner-product of data in the feature space without knowing these feature space data. In this paper, the kernel trick will be employed to extend the algorithm of spectrum sensing with leading eigenvector under the framework of PCA to a higher dimensional feature space. Namely, the leading eigenvector of the sample covariance matrix in the feature space is used for spectrum sensing without knowing the leading eigenvector explicitly. Spectrum sensing with leading eigenvector under the framework of kernel PCA is proposed with the inner-product as a measure of similarity. A modified kernel GLRT algorithm based on matched subspace model will be the first time applied to spectrum sensing. The experimental results on simulated sinusoidal signal show that spectrum sensing with kernel PCA is about 4 dB better than PCA, besides, kernel GLRT is also better than GLRT. The proposed algorithms are also tested on the measured DTV signal. The simulation results show that kernel methods are 4 dB better than the corresponding linear methods. The leading eigenvector of the sample covariance matrix learned by kernel PCA is more stable than that learned by PCA for different segments of DTV signal.
Worst-Case Robust Distributed Power Allocation in Shared Unlicensed Spectrum
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers non-cooperative and fully-distributed power-allocation for selfish transmitter-receiver pairs in shared unlicensed spectrum when normalized-interference to each receiver is uncertain. We model each uncertain parameter by the sum of its nominal (estimated) value and a bounded additive error in a convex set, and show that the allocated power always converges to its equilibrium, called robust Nash equilibrium (RNE). In the case of a bounded and symmetric uncertainty region, we show that the power allocation problem for each user is simplified, and can be solved in a distributed manner. We derive the conditions for RNE's uniqueness and for convergence of the distributed algorithm; and show that the total throughput (social utility) is less than that at NE when RNE is unique. We also show that for multiple RNEs, the social utility may be higher at a RNE as compared to that at the corresponding NE, and demonstrate that this is caused by users' orthogonal utilization of bandwidth at RNE. Simulations confirm our analysis.
The approximate maximum-likelihood certificate
Venue: arXiv cs.IT 2011
Year: 2011

A new property which relies on the linear programming (LP) decoder, the approximate maximum-likelihood certificate (AMLC), is introduced. When using the belief propagation decoder, this property is a measure of how close the decoded codeword is to the LP solution. Using upper bounding techniques, it is demonstrated that the conditional frame error probability given that the AMLC holds is, with some degree of confidence, below a threshold. In channels with low noise, this threshold is several orders of magnitude lower than the simulated frame error rate, and our bound holds with very high degree of confidence. In contrast, showing this error performance by simulation would require very long Monte Carlo runs. When the AMLC holds, our approach thus provides the decoder with extra error detection capability, which is especially important in applications requiring high data integrity.
On the Capacity of Noisy Computations
Venue: arXiv cs.IT 2011
Year: 2011

This paper presents an analysis of the concept of capacity for noisy computations, i.e. algorithms implemented by unreliable computing devices (e.g. noisy Turing Machines). The capacity of a noisy computation is defined and justified by companion coding theorems. Under some constraints on the encoding process, capacity is the upper bound of input rates allowing reliable computation, i.e. decodability of noisy outputs into expected outputs. A model of noisy computation of a perfect function f thanks to an unreliable device F is given together with a model of reliable computation based on input encoding and output decoding. A coding lemma (extending the Feinstein's theorem to noisy computations), a joint source-computation coding theorem and its converse are proved. They apply if the input source, the function f, the noisy device F and the cascade f^{-1}F induce AMS and ergodic one-sided random processes.
Optimal Camera Placement to measure Distances Conservativly Regarding Static and Dynamic Obstacles
Venue: arXiv cs.CV 2011
Year: 2011

In modern production facilities industrial robots and humans are supposed to interact sharing a common working area. In order to avoid collisions, the distances between objects need to be measured conservatively which can be done by a camera network. To estimate the acquired distance, unmodelled objects, e.g., an interacting human, need to be modelled and distinguished from premodelled objects like workbenches or robots by image processing such as the background subtraction method. The quality of such an approach massively depends on the settings of the camera network, that is the positions and orientations of the individual cameras. Of particular interest in this context is the minimization of the error of the distance using the objects modelled by the background subtraction method instead of the real objects. Here, we show how this minimization can be formulated as an abstract optimization problem. Moreover, we state various aspects on the implementation as well as reasons for the selection of a suitable optimization method, analyze the complexity of the proposed method and present a basic version used for extensive experiments.
Randomly Roving Agents in Wireless Sensor Networks
Venue: arXiv cs.DM 2011
Year: 2011

Quantitative characterization of randomly roving agents in wireless sensor networks (WSN) is studied. Below the formula simplifications, regarding the known results and publications, it is shown that the basic agent model is probabilistically equivalent to a similar simpler model and then a formula for frequencies is achieved in terms of combinatorial second kind Stirling numbers. Stirling numbers are well studied and different estimates are known for them letting to justify the roving agents quantitative characteristics.
The block cipher NSABC (public domain)
Venue: arXiv cs.CR 2011
Year: 2011

We introduce NSABC/w -- Nice-Structured Algebraic Block Cipher using w-bit word arithmetic, a 4w-bit analogous of Skipjack [NSA98] with 5w-bit key. The Skipjack's internal 4-round Feistel structure is replaced with a w-bit, 2-round cascade of a binary operation (x,z)\mapsto(x\boxdot z)\lll(w/2) that permutes a text word x under control of a key word z. The operation \boxdot, similarly to the multiplication in IDEA [LM91, LMM91], bases on an algebraic group over w-bit words, so it is also capable of decrypting by means of the inverse element of z in the group. The cipher utilizes a secret 4w-bit tweak -- an easily changeable parameter with unique value for each block encrypted under the same key [LRW02] -- that is derived from the block index and an additional 4w -bit key. A software implementation for w=64 takes circa 9 clock cycles per byte on x86-64 processors.
The Exact Schema Theorem
Venue: arXiv cs.NE 2011
Year: 2011

A schema is a naturally defined subset of the space of fixed-length binary strings. The Holland Schema Theorem gives a lower bound on the expected fraction of a population in a schema after one generation of a simple genetic algorithm. This paper gives formulas for the exact expected fraction of a population in a schema after one generation of the simple genetic algorithm. Holland's schema theorem has three parts, one for selection, one for crossover, and one for mutation. The selection part is exact, whereas the crossover and mutation parts are approximations. This paper shows how the crossover and mutation parts can be made exact. Holland's schema theorem follows naturally as a corollary. There is a close relationship between schemata and the representation of the population in the Walsh basis. This relationship is used in the derivation of the results, and can also make computation of the schema averages more efficient. This paper gives a version of the Vose infinite population model where crossover and mutation are separated into two functions rather than a single "mixing" function.
Fast Distributed Process Creation with the XMOS XS1 Architecture
Venue: arXiv cs.DC 2011
Year: 2011

The provision of mechanisms for processor allocation in current distributed parallel programming models is very limited. This makes difficult, or even prohibits, the expression of a large class of programs which require a run-time assessment of their required resources. This includes programs whose structure is irregular, composite or unbounded. Efficient allocation of processors requires a process creation mechanism able to initiate and terminate remote computations quickly. This paper presents the design, demonstration and analysis of an explicit mechanism to do this, implemented on the XMOS XS1 architecture, as a foundation for a more dynamic scheme. It shows that process creation can be made efficient so that it incurs only a fractional overhead of the total runtime and that it can be combined naturally with recursion to enable rapid distribution of computations over a system.
Component Based Clustering in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

Clustering is an important research topic for wireless sensor networks (WSNs). A large variety of approaches has been presented focusing on different performance metrics. Even though all of them have many practical applications, an extremely limited number of software implementations is available to the research community. Furthermore, these very few techniques are implemented for specific WSN systems or are integrated in complex applications. Thus it is very difficult to comparatively study their performance and almost impossible to reuse them in future applications under a different scope. In this work we study a large body of well established algorithms. We identify their main building blocks and propose a component-based architecture for developing clustering algorithms that (a) promotes exchangeability of algorithms thus enabling the fast prototyping of new approaches, (b) allows cross-layer implementations to realize complex applications, (c) offers a common platform to comparatively study the performance of different approaches, (d) is hardware and OS independent. We implement 5 well known algorithms and discuss how to implement 11 more. We conduct an extended simulation study to demonstrate the faithfulness of our implementations when compared to the original implementations. Our simulations are at very large scale thus also demonstrating the scalability of the original algorithms beyond their original presentations. We also conduct experiments to assess their practicality in real WSNs. We demonstrate how the implemented clustering algorithms can be combined with routing and group key establishment algorithms to construct WSN applications. Our study clearly demonstrates the applicability of our approach and the benefits it offers to both research & development communities.
Logical Modelling of Physarum Polycephalum
Venue: arXiv cs.LO 2011
Year: 2011

We propose a novel model of unconventional computing where a structural part of computation is presented by dynamics of plasmodium of Physarum polycephalum, a large single cell. We sketch a new logical approach combining conventional logic with process calculus to demonstrate how to employ formal methods in design of unconventional computing media presented by Physarum polycephalum.
On 2-Site Voronoi Diagrams under Geometric Distance Functions
Venue: arXiv cs.CG 2011
Year: 2011

We revisit a new type of a Voronoi diagram, in which distance is measured from a point to a pair of points. We consider a few more such distance functions, based on geometric primitives, and analyze the structure and complexity of the nearest- and furthest-neighbor Voronoi diagrams of a point set with respect to these distance functions.
On the poset of computation rules for nonassociative calculus
Venue: arXiv cs.DM 2011
Year: 2011

The symmetric maximum, denoted by v, is an extension of the usual max operation so that 0 is the neutral element, and -x is the symmetric (or inverse) of x, i.e., x v(-x)=0. However, such an extension does not preserve the associativity of max. This fact asks for systematic ways of parenthesing (or bracketing) terms of a sequence (with more than two arguments) when using such an extended maximum. We refer to such systematic (predefined) ways of parenthesing as computation rules. As it turns out there are infinitely many computation rules each of which corresponding to a systematic way of bracketing arguments of sequences. Essentially, computation rules reduce to deleting terms of sequences based on the condition x v(-x)=0. This observation gives raise to a quasi-order on the set of such computation rules: say that rule 1 is below rule 2 if for all sequences of numbers, rule 1 deletes more terms in the sequence than rule 2. In this paper we present a study of this quasi-ordering of computation rules. In particular, we show that the induced poset of all equivalence classes of computation rules is uncountably infinite, has infinitely many maximal elements, has infinitely many atoms, and it embeds the powerset of natural numbers ordered by inclusion.
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
Venue: arXiv cs.CC 2011
Year: 2011

We study the problem of computing the minimum vertex cover on k-uniform k-partite hypergraphs when the k-partition is given. On bipartite graphs (k = 2), the minimum vertex cover can be computed in polynomial time. For general k, the problem was studied by Lovász, who gave a k/2 -approximation based on the standard LP relaxation. Subsequent work by Aharoni, Holzman and Krivelevich showed a tight integrality gap of (k/2 - o(1)) for the LP relaxation. While this problem was known to be NP-hard for k >= 3, the first non-trivial NP-hardness of approximation factor of k/4- \eps was shown in a recent work by Guruswami and Saket. They also showed that assuming Khot's Unique Games Conjecture yields a k/2 - \eps inapproximability for this problem, implying the optimality of Lovász's result. In this work, we show that this problem is NP-hard to approximate within k/2- 1 + 1/2k -\eps. This hardness factor is off from the optimal by an additive constant of at most 1 for k >= 4. Our reduction relies on the Multi-Layered PCP of Dinur et al. and uses a gadget - based on biased Long Codes - adapted from the LP integrality gap of Aharoni et al. The nature of our reduction requires the analysis of several Long Codes with different biases, for which we prove structural properties of the so called cross-intersecting collections of set families - variants of which have been studied in extremal set theory.
Column-Oriented Storage Techniques for MapReduce
Venue: arXiv cs.DB 2011
Year: 2011

Users of MapReduce often run into performance problems when they scale up their workloads. Many of the problems they encounter can be overcome by applying techniques learned from over three decades of research on parallel DBMSs. However, translating these techniques to a MapReduce implementation such as Hadoop presents unique challenges that can lead to new design choices. This paper describes how column-oriented storage techniques can be incorporated in Hadoop in a way that preserves its popular programming APIs. We show that simply using binary storage formats in Hadoop can provide a 3x performance boost over the naive use of text files. We then introduce a column-oriented storage format that is compatible with the replication and scheduling constraints of Hadoop and show that it can speed up MapReduce jobs on real workloads by an order of magnitude. We also show that dealing with complex column types such as arrays, maps, and nested records, which are common in MapReduce jobs, can incur significant CPU overhead. Finally, we introduce a novel skip list column format and lazy record construction strategy that avoids deserializing unwanted records to provide an additional 1.5x performance boost. Experiments on a real intranet crawl are used to show that our column-oriented storage techniques can improve the performance of the map phase in Hadoop by as much as two orders of magnitude.
A Tool for Integer Homology Computation: Lambda-At Model
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, we formalize the notion of lambda-AT-model (where $λ$ is a non-null integer) for a given chain complex, which allows the computation of homological information in the integer domain avoiding using the Smith Normal Form of the boundary matrices. We present an algorithm for computing such a model, obtaining Betti numbers, the prime numbers p involved in the invariant factors of the torsion subgroup of homology, the amount of invariant factors that are a power of p and a set of representative cycles of generators of homology mod p, for each p. Moreover, we establish the minimum valid lambda for such a construction, what cuts down the computational costs related to the torsion subgroup. The tools described here are useful to determine topological information of nD structured objects such as simplicial, cubical or simploidal complexes and are applicable to extract such an information from digital pictures.
Secure Lossy Source-Channel Wiretapping with Side Information at the Receiving Terminals
Venue: arXiv cs.IT 2011
Year: 2011

The problem of secure lossy source-channel wiretapping with arbitrarily correlated side informations at both receivers is investigated. This scenario consists of an encoder (referred to as Alice) that wishes to compress a source and send it through a noisy channel to a legitimate receiver (referred to as Bob). In this context, Alice must simultaneously satisfy the desired requirements on the distortion level at Bob, and the equivocation rate at the eavesdropper (referred to as Eve). This setting can be seen as a generalization of the conventional problems of secure source coding with side information at the decoders, and the wiretap channel. Inner and outer bounds on the rate-distortion-equivocation region for the case of arbitrary channels and side informations are derived. In some special cases of interest, it is shown that separation holds. By means of an appropriate coding, the presence of any statistical difference among the side informations, the channel noises, and the distortion at Bob can be fully exploited in terms of secrecy.
Image Splicing Detection Using Inherent Lens Radial Distortion
Venue: arXiv cs.CV 2011
Year: 2011

Image splicing is a common form of image forgery. Such alterations may leave no visual clues of tampering. In recent works camera characteristics consistency across the image has been used to establish the authenticity and integrity of digital images. Such constant camera characteristic properties are inherent from camera manufacturing processes and are unique. The majority of digital cameras are equipped with spherical lens and this introduces radial distortions on images. This aberration is often disturbed and fails to be consistent across the image, when an image is spliced. This paper describes the detection of splicing operation on images by estimating radial distortion from different portions of the image using line-based calibration. For the first time, the detection of image splicing through the verification of consistency of lens radial distortion has been explored in this paper. The conducted experiments demonstrate the efficacy of our proposed approach for the detection of image splicing on both synthetic and real images.
A Knowledge base model for complex forging die machining
Venue: arXiv cs.OH 2011
Year: 2011

Recent evolutions on forging process induce more complex shape on forging die. These evolutions, combined with High Speed Machining (HSM) process of forging die lead to important increase in time for machining preparation. In this context, an original approach for generating machining process based on machining knowledge is proposed in this paper. The core of this approach is to decompose a CAD model of complex forging die in geometric features. Technological data and topological relations are aggregated to a geometric feature in order to create machining features. Technological data, such as material, surface roughness and form tolerance are defined during forging process and dies design. These data are used to choose cutting tools and machining strategies. Topological relations define relative positions between the surfaces of the die CAD model. After machining features identification cutting tools and machining strategies currently used in HSM of forging die, are associated to them in order to generate machining sequences. A machining process model is proposed to formalize the links between information imbedded in the machining features and the parameters of cutting tools and machining strategies. At last machining sequences are grouped and ordered to generate the complete die machining process. In this paper the identification of geometrical features is detailed. Geometrical features identification is based on machining knowledge formalization which is translated in the generation of maps from STL models. A map based on the contact area between cutting tools and die shape gives basic geometrical features which are connected or not according to the continuity maps. The proposed approach is illustrated by an application on an industrial study case which was accomplished as part of collaboration.
Distributed Evolutionary Computation using REST
Venue: arXiv cs.NE 2011
Year: 2011

This paper analises distributed evolutionary computation based on the Representational State Transfer (REST) protocol, which overlays a farming model on evolutionary computation. An approach to evolutionary distributed optimisation of multilayer perceptrons (MLP) using REST and language Perl has been done. In these experiments, a master-slave based evolutionary algorithm (EA) has been implemented, where slave processes evaluate the costly fitness function (training a MLP to solve a classification problem). Obtained results show that the parallel version of the developed programs obtains similar or better results using much less time than the sequential version, obtaining a good speedup.