OpenRaiser/Intern-Atlas huggingface dataset:
TCHR: a framework for tabled CLP
Venue: arXiv cs.PL 2007
Year: 2007

Tabled Constraint Logic Programming is a powerful execution mechanism for dealing with Constraint Logic Programming without worrying about fixpoint computation. Various applications, e.g in the fields of program analysis and model checking, have been proposed. Unfortunately, a high-level system for developing new applications is lacking, and programmers are forced to resort to complicated ad hoc solutions. This papers presents TCHR, a high-level framework for tabled Constraint Logic Programming. It integrates in a light-weight manner Constraint Handling Rules (CHR), a high-level language for constraint solvers, with tabled Logic Programming. The framework is easily instantiated with new application-specific constraint domains. Various high-level operations can be instantiated to control performance. In particular, we propose a novel, generalized technique for compacting answer sets.
A Fast Hierarchical Multilevel Image Segmentation Method using Unbiased Estimators
Venue: arXiv cs.CV 2007
Year: 2007

This paper proposes a novel method for segmentation of images by hierarchical multilevel thresholding. The method is global, agglomerative in nature and disregards pixel locations. It involves the optimization of the ratio of the unbiased estimators of within class to between class variances. We obtain a recursive relation at each step for the variances which expedites the process. The efficacy of the method is shown in a comparison with some well-known methods.
Developing an Efficient DMCIS with Next-Generation Wireless Networks
Venue: arXiv cs.NI 2007
Year: 2007

The impact of extreme events across the globe is extraordinary which continues to handicap the advancement of the struggling developing societies and threatens most of the industrialized countries in the globe. Various fields of Information and Communication Technology have widely been used for efficient disaster management; but only to a limited extent though, there is a tremendous potential for increasing efficiency and effectiveness in coping with disasters with the utilization of emerging wireless network technologies. Early warning, response to the particular situation and proper recovery are among the main focuses of an efficient disaster management system today. Considering these aspects, in this paper we propose a framework for developing an efficient Disaster Management Communications and Information System (DMCIS) which is basically benefited by the exploitation of the emerging wireless network technologies combined with other networking and data processing technologies.
Probabilistic Visual Secret Sharing Schemes for Gray-scale images and Color images
Venue: arXiv cs.CR 2007
Year: 2007

Visual secrete sharing (VSS) is an encryption technique that utilizes human visual system in the recovering of the secret image and it does not require any complex calculation. Pixel expansion has been a major issue of VSS schemes. A number of probabilistic VSS schemes with minimum pixel expansion have been proposed for binary secret images. This paper presents a general probabilistic (k, n)-VSS scheme for gray-scale images and another scheme for color images. With our schemes, the pixel expansion can be set to a user-defined value. When this value is 1, there is no pixel expansion at all. The quality of reconstructed secret images, measured by Average Relative Difference, is equivalent to Relative Difference of existing deterministic schemes. Previous probabilistic VSS schemes for black-and-white images with respect to pixel expansion can be viewed as special cases of the schemes proposed here
Finite Automata Based on Quantum Logic and Their Determinization
Venue: arXiv cs.LO 2007
Year: 2007

We give the quantum subset construction of orthomodular lattice-valued finite automata, then we show the equivalence between orthomodular lattice-valued finite automata, orthomodular lattice-valued deterministic finite automata and orthomodular lattice-valued finite automata with empty string-moves. Based on these equivalences, we study the algebraic operations on orthomodular lattice-valued regular languages, then we establish Kleene theorem in the frame of quantum logic.
Two-Level Concept-Oriented Data Model
Venue: arXiv cs.DB 2007
Year: 2007

In this paper we describe a new approach to data modelling called the concept-oriented model (CoM). This model is based on the formalism of nested ordered sets which uses inclusion relation to produce hierarchical structure of sets and ordering relation to produce multi-dimensional structure among its elements. Nested ordered set is defined as an ordered set where an each element can be itself an ordered set. Ordering relation in CoM is used to define data semantics and operations with data such as projection and de-projection. This data model can be applied to very different problems and the paper describes some its uses such grouping with aggregation and multi-dimensional analysis.
Pseudocodewords of Tanner graphs
Venue: arXiv cs.IT 2007
Year: 2007

This papers presents a detailed analysis of pseudocodewords of Tanner graphs. Pseudocodewords arising on the iterative decoder's computation tree are distinguished from pseudocodewords arising on finite degree lifts. Lower bounds on the minimum pseudocodeword weight are presented for the BEC, BSC, and AWGN channel. Some structural properties of pseudocodewords are examined, and pseudocodewords and graph properties that are potentially problematic with min-sum iterative decoding are identified. An upper bound on the minimum degree lift needed to realize a particular irreducible lift-realizable pseudocodeword is given in terms of its maximal component, and it is shown that all irreducible lift-realizable pseudocodewords have components upper bounded by a finite value $t$ that is dependent on the graph structure. Examples and different Tanner graph representations of individual codes are examined and the resulting pseudocodeword distributions and iterative decoding performances are analyzed. The results obtained provide some insights in relating the structure of the Tanner graph to the pseudocodeword distribution and suggest ways of designing Tanner graphs with good minimum pseudocodeword weight.
Sufficient conditions for convergence of the Sum-Product Algorithm
Venue: arXiv cs.IT 2007
Year: 2007

We derive novel conditions that guarantee convergence of the Sum-Product algorithm (also known as Loopy Belief Propagation or simply Belief Propagation) to a unique fixed point, irrespective of the initial messages. The computational complexity of the conditions is polynomial in the number of variables. In contrast with previously existing conditions, our results are directly applicable to arbitrary factor graphs (with discrete variables) and are shown to be valid also in the case of factors containing zeros, under some additional conditions. We compare our bounds with existing ones, numerically and, if possible, analytically. For binary variables with pairwise interactions, we derive sufficient conditions that take into account local evidence (i.e., single variable factors) and the type of pair interactions (attractive or repulsive). It is shown empirically that this bound outperforms existing bounds.
Distant generalization by feedforward neural networks
Venue: arXiv cs.NE 2007
Year: 2007

This paper discusses the notion of generalization of training samples over long distances in the input space of a feedforward neural network. Such a generalization might occur in various ways, that differ in how great the contribution of different training features should be. The structure of a neuron in a feedforward neural network is analyzed and it is concluded, that the actual performance of the discussed generalization in such neural networks may be problematic -- while such neural networks might be capable for such a distant generalization, a random and spurious generalization may occur as well. To illustrate the differences in generalizing of the same function by different learning machines, results given by the support vector machines are also presented.
Distributed Selfish Load Balancing
Venue: arXiv cs.GT 2007
Year: 2007

Suppose that a set of $m$ tasks are to be shared as equally as possible amongst a set of $n$ resources. A game-theoretic mechanism to find a suitable allocation is to associate each task with a ``selfish agent'', and require each agent to select a resource, with the cost of a resource being the number of agents to select it. Agents would then be expected to migrate from overloaded to underloaded resources, until the allocation becomes balanced. Recent work has studied the question of how this can take place within a distributed setting in which agents migrate selfishly without any centralized control. In this paper we discuss a natural protocol for the agents which combines the following desirable features: It can be implemented in a strongly distributed setting, uses no central control, and has good convergence properties. For $m\gg n$, the system becomes approximately balanced (an $ε$-Nash equilibrium) in expected time $O(\log\log m)$. We show using a martingale technique that the process converges to a perfectly balanced allocation in expected time $O(\log\log m+n^4)$. We also give a lower bound of $Ω(\max\{\log\log m,n\})$ for the convergence time.
Maximum Weight Matching via Max-Product Belief Propagation
Venue: arXiv cs.IT 2007
Year: 2007

Max-product "belief propagation" is an iterative, local, message-passing algorithm for finding the maximum a posteriori (MAP) assignment of a discrete probability distribution specified by a graphical model. Despite the spectacular success of the algorithm in many application areas such as iterative decoding, computer vision and combinatorial optimization which involve graphs with many cycles, theoretical results about both correctness and convergence of the algorithm are known in few cases (Weiss-Freeman Wainwright, Yeddidia-Weiss-Freeman, Richardson-Urbanke}. In this paper we consider the problem of finding the Maximum Weight Matching (MWM) in a weighted complete bipartite graph. We define a probability distribution on the bipartite graph whose MAP assignment corresponds to the MWM. We use the max-product algorithm for finding the MAP of this distribution or equivalently, the MWM on the bipartite graph. Even though the underlying bipartite graph has many short cycles, we find that surprisingly, the max-product algorithm always converges to the correct MAP assignment as long as the MAP assignment is unique. We provide a bound on the number of iterations required by the algorithm and evaluate the computational cost of the algorithm. We find that for a graph of size $n$, the computational cost of the algorithm scales as $O(n^3)$, which is the same as the computational cost of the best known algorithm. Finally, we establish the precise relation between the max-product algorithm and the celebrated {\em auction} algorithm proposed by Bertsekas. This suggests possible connections between dual algorithm and max-product algorithm for discrete optimization problems.
Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners
Venue: arXiv cs.DS 2007
Year: 2007

In the year 1876 the mathematician Charles Dodgson, who wrote fiction under the now more famous name of Lewis Carroll, devised a beautiful voting system that has long fascinated political scientists. However, determining the winner of a Dodgson election is known to be complete for the Θ_2^p level of the polynomial hierarchy. This implies that unless P=NP no polynomial-time solution to this problem exists, and unless the polynomial hierarchy collapses to NP the problem is not even in NP. Nonetheless, we prove that when the number of voters is much greater than the number of candidates--although the number of voters may still be polynomial in the number of candidates--a simple greedy algorithm very frequently finds the Dodgson winners in such a way that it ``knows'' that it has found them, and furthermore the algorithm never incorrectly declares a nonwinner to be a winner.
Product Multicommodity Flow in Wireless Networks
Venue: arXiv cs.IT 2007
Year: 2007

We provide a tight approximate characterization of the $n$-dimensional product multicommodity flow (PMF) region for a wireless network of $n$ nodes. Separate characterizations in terms of the spectral properties of appropriate network graphs are obtained in both an information theoretic sense and for a combinatorial interference model (e.g., Protocol model). These provide an inner approximation to the $n^2$ dimensional capacity region. These results answer the following questions which arise naturally from previous work: (a) What is the significance of $1/\sqrt{n}$ in the scaling laws for the Protocol interference model obtained by Gupta and Kumar (2000)? (b) Can we obtain a tight approximation to the "maximum supportable flow" for node distributions more general than the geometric random distribution, traffic models other than randomly chosen source-destination pairs, and under very general assumptions on the channel fading model? We first establish that the random source-destination model is essentially a one-dimensional approximation to the capacity region, and a special case of product multi-commodity flow. Building on previous results, for a combinatorial interference model given by a network and a conflict graph, we relate the product multicommodity flow to the spectral properties of the underlying graphs resulting in computational upper and lower bounds. For the more interesting random fading model with additive white Gaussian noise (AWGN), we show that the scaling laws for PMF can again be tightly characterized by the spectral properties of appropriately defined graphs. As an implication, we obtain computationally efficient upper and lower bounds on the PMF for any wireless network with a guaranteed approximation factor.
Does the arXiv lead to higher citations and reduced publisher downloads for mathematics articles?
Venue: arXiv cs.DL 2007
Year: 2007

An analysis of 2,765 articles published in four math journals from 1997 to 2005 indicate that articles deposited in the arXiv received 35% more citations on average than non-deposited articles (an advantage of about 1.1 citations per article), and that this difference was most pronounced for highly-cited articles. Open Access, Early View, and Quality Differential were examined as three non-exclusive postulates for explaining the citation advantage. There was little support for a universal Open Access explanation, and no empirical support for Early View. There was some inferential support for a Quality Differential brought about by more highly-citable articles being deposited in the arXiv. In spite of their citation advantage, arXiv-deposited articles received 23% fewer downloads from the publisher's website (about 10 fewer downloads per article) in all but the most recent two years after publication. The data suggest that arXiv and the publisher's website may be fulfilling distinct functional needs of the reader.
Consensus Propagation
Venue: arXiv cs.IT 2007
Year: 2007

We propose consensus propagation, an asynchronous distributed protocol for averaging numbers across a network. We establish convergence, characterize the convergence rate for regular graphs, and demonstrate that the protocol exhibits better scaling properties than pairwise averaging, an alternative that has received much recent attention. Consensus propagation can be viewed as a special case of belief propagation, and our results contribute to the belief propagation literature. In particular, beyond singly-connected graphs, there are very few classes of relevant problems for which belief propagation is known to converge.
Order-Optimal Data Aggregation in Wireless Sensor Networks - Part I: Regular Networks
Venue: arXiv cs.IT 2007
Year: 2007

The predominate traffic patterns in a wireless sensor network are many-to-one and one-to-many communication. Hence, the performance of wireless sensor networks is characterized by the rate at which data can be disseminated from or aggregated to a data sink. In this paper, we consider the data aggregation problem. We demonstrate that a data aggregation rate of O(log(n)/n) is optimal and that this rate can be achieved in wireless sensor networks using a generalization of cooperative beamforming called cooperative time-reversal communication.
Naming Games in Spatially-Embedded Random Networks
Venue: arXiv cs.MA 2007
Year: 2007

We investigate a prototypical agent-based model, the Naming Game, on random geometric networks. The Naming Game is a minimal model, employing local communications that captures the emergence of shared communication schemes (languages) in a population of autonomous semiotic agents. Implementing the Naming Games on random geometric graphs, local communications being local broadcasts, serves as a model for agreement dynamics in large-scale, autonomously operating wireless sensor networks. Further, it captures essential features of the scaling properties of the agreement process for spatially-embedded autonomous agents. We also present results for the case when a small density of long-range communication links are added on top of the random geometric graph, resulting in a "small-world"-like network and yielding a significantly reduced time to reach global agreement.
Generalized Entropy Power Inequalities and Monotonicity Properties of Information
Venue: arXiv cs.IT 2007
Year: 2007

New families of Fisher information and entropy power inequalities for sums of independent random variables are presented. These inequalities relate the information in the sum of $n$ independent random variables to the information contained in sums over subsets of the random variables, for an arbitrary collection of subsets. As a consequence, a simple proof of the monotonicity of information in central limit theorems is obtained, both in the setting of i.i.d. summands as well as in the more general setting of independent summands with variance-standardized sums.
Node-Based Optimal Power Control, Routing, and Congestion Control in Wireless Networks
Venue: arXiv cs.NI 2007
Year: 2007

We present a unified analytical framework within which power control, rate allocation, routing, and congestion control for wireless networks can be optimized in a coherent and integrated manner. We consider a multi-commodity flow model with an interference-limited physical-layer scheme in which power control and routing variables are chosen to minimize the sum of convex link costs reflecting, for instance, queuing delay. Distributed network algorithms where joint power control and routing are performed on a node-by-node basis are presented. We show that with appropriately chosen parameters, these algorithms iteratively converge to the global optimum from any initial point with finite cost. Next, we study refinements of the algorithms for more accurate link capacity models, and extend the results to wireless networks where the physical-layer achievable rate region is given by an arbitrary convex set, and the link costs are strictly quasiconvex. Finally, we demonstrate that congestion control can be seamlessly incorporated into our framework, so that algorithms developed for power control and routing can naturally be extended to optimize user input rates.
Frugality ratios and improved truthful mechanisms for vertex cover
Venue: arXiv cs.GT 2007
Year: 2007

In {\em set-system auctions}, there are several overlapping teams of agents, and a task that can be completed by any of these teams. The buyer's goal is to hire a team and pay as little as possible. Recently, Karlin, Kempe and Tamir introduced a new definition of {\em frugality ratio} for this setting. Informally, the frugality ratio is the ratio of the total payment of a mechanism to perceived fair cost. In this paper, we study this together with alternative notions of fair cost, and how the resulting frugality ratios relate to each other for various kinds of set systems. We propose a new truthful polynomial-time auction for the vertex cover problem (where the feasible sets correspond to the vertex covers of a given graph), based on the {\em local ratio} algorithm of Bar-Yehuda and Even. The mechanism guarantees to find a winning set whose cost is at most twice the optimal. In this situation, even though it is NP-hard to find a lowest-cost feasible set, we show that {\em local optimality} of a solution can be used to derive frugality bounds that are within a constant factor of best possible. To prove this result, we use our alternative notions of frugality via a bootstrapping technique, which may be of independent interest.
Dimension Extractors and Optimal Decompression
Venue: arXiv cs.CC 2007
Year: 2007

A *dimension extractor* is an algorithm designed to increase the effective dimension -- i.e., the amount of computational randomness -- of an infinite binary sequence, in order to turn a "partially random" sequence into a "more random" sequence. Extractors are exhibited for various effective dimensions, including constructive, computable, space-bounded, time-bounded, and finite-state dimension. Using similar techniques, the Kucera-Gacs theorem is examined from the perspective of decompression, by showing that every infinite sequence S is Turing reducible to a Martin-Loef random sequence R such that the asymptotic number of bits of R needed to compute n bits of S, divided by n, is precisely the constructive dimension of S, which is shown to be the optimal ratio of query bits to computed bits achievable with Turing reductions. The extractors and decompressors that are developed lead directly to new characterizations of some effective dimensions in terms of optimal decompression by Turing reductions.
Self-orthogonality of $q$-ary Images of $q^m$-ary Codes and Quantum Code Construction
Venue: arXiv cs.IT 2007
Year: 2007

A code over GF$(q^m)$ can be imaged or expanded into a code over GF$(q)$ using a basis for the extension field over the base field. The properties of such an image depend on the original code and the basis chosen for imaging. Problems relating the properties of a code and its image with respect to a basis have been of great interest in the field of coding theory. In this work, a generalized version of the problem of self-orthogonality of the $q$-ary image of a $q^m$-ary code has been considered. Given an inner product (more generally, a biadditive form), necessary and sufficient conditions have been derived for a code over a field extension and an expansion basis so that an image of that code is self-orthogonal. The conditions require that the original code be self-orthogonal with respect to several related biadditive forms whenever certain power sums of the dual basis elements do not vanish. Numerous interesting corollaries have been derived by specializing the general conditions. An interesting result for the canonical or regular inner product in fields of characteristic two is that only self-orthogonal codes result in self-orthogonal images. Another result is that image of a code is self-orthogonal for all bases if and only if trace of the code is self-orthogonal, except for the case of binary images of 4-ary codes. The conditions are particularly simple to state and apply for cyclic codes. To illustrate a possible application, new quantum error-correcting codes have been constructed with larger minimum distance than previously known.
The Haar Wavelet Transform of a Dendrogram
Venue: arXiv cs.IR 2007
Year: 2007

We describe a new wavelet transform, for use on hierarchies or binary rooted trees. The theoretical framework of this approach to data analysis is described. Case studies are used to further exemplify this approach. A first set of application studies deals with data array smoothing, or filtering. A second set of application studies relates to hierarchical tree condensation. Finally, a third study explores the wavelet decomposition, and the reproducibility of data sets such as text, including a new perspective on the generation or computability of such data objects.