OpenRaiser/Intern-Atlas huggingface dataset:
Capacity Bounds for Broadcast Channels with Confidential Messages
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we study capacity bounds for discrete memoryless broadcast channels with confidential messages. Two private messages as well as a common message are transmitted; the common message is to be decoded by both receivers, while each private message is only for its intended receiver. In addition, each private message is to be kept secret from the unintended receiver where secrecy is measured by equivocation. We propose both inner and outer bounds to the rate equivocation region for broadcast channels with confidential messages. The proposed inner bound generalizes Csiszár and Körner's rate equivocation region for broadcast channels with a single confidential message, Liu {\em et al}'s achievable rate region for broadcast channels with perfect secrecy, Marton's and Gel'fand and Pinsker's achievable rate region for general broadcast channels. Our proposed outer bounds, together with the inner bound, helps establish the rate equivocation region of several classes of discrete memoryless broadcast channels with confidential messages, including less noisy, deterministic, and semi-deterministic channels. Furthermore, specializing to the general broadcast channel by removing the confidentiality constraint, our proposed outer bounds reduce to new capacity outer bounds for the discrete memory broadcast channel.
Confidentiality, Integrity and High Availability with Open Source IT green
Venue: arXiv cs.CR 2008
Year: 2008

This paper presents elements that form the structure of a network of data using secure stable and mature technologies that meet the requirement of having code free. The principle would be conflicting code open Tuesday where he wants to keep maximum control over the data but is already evidence that open source does not hide the famous backdoor possible in closed systems code. Basearemos this work experience gained in a real environment and using paravirtualization to show a situation more critical and now real in most companies, the virtualization of servers.
Modeling Loosely Annotated Images with Imagined Annotations
Venue: arXiv cs.IR 2008
Year: 2008

In this paper, we present an approach to learning latent semantic analysis models from loosely annotated images for automatic image annotation and indexing. The given annotation in training images is loose due to: (1) ambiguous correspondences between visual features and annotated keywords; (2) incomplete lists of annotated keywords. The second reason motivates us to enrich the incomplete annotation in a simple way before learning topic models. In particular, some imagined keywords are poured into the incomplete annotation through measuring similarity between keywords. Then, both given and imagined annotations are used to learning probabilistic topic models for automatically annotating new images. We conduct experiments on a typical Corel dataset of images and loose annotations, and compare the proposed method with state-of-the-art discrete annotation methods (using a set of discrete blobs to represent an image). The proposed method improves word-driven probability Latent Semantic Analysis (PLSA-words) up to a comparable performance with the best discrete annotation method, while a merit of PLSA-words is still kept, i.e., a wider semantic range.
Textual Entailment Recognizing by Theorem Proving Approach
Venue: arXiv cs.CL 2008
Year: 2008

In this paper we present two original methods for recognizing textual inference. First one is a modified resolution method such that some linguistic considerations are introduced in the unification of two atoms. The approach is possible due to the recent methods of transforming texts in logic formulas. Second one is based on semantic relations in text, as presented in WordNet. Some similarities between these two methods are remarked.
Community Detection using a Measure of Global Influence
Venue: arXiv cs.CY 2008
Year: 2008

The growing popularity of online social networks has provided researchers with access to large amount of social network data. This, coupled with the ever increasing computation speed, storage capacity and data mining capabilities, led to the renewal of interest in automatic community detection methods. Surprisingly, there is no universally accepted definition of the community. One frequently used definition states that ``communities, that have more and/or better-connected `internal edges' connecting members of the set than `cut edges' connecting the set to the rest of the world''[Leskovec et al. 20008]. This definition inspired the modularity-maximization class of community detection algorithms, which look for regions of the network that have higher than expected density of edges within them. We introduce an alternative definition which states that a community is composed of individuals who have more influence on others within the community than on those outside of it. We present a mathematical formulation of influence, define an influence-based modularity metric, and show how to use it to partition the network into communities. We evaluated our approach on the standard data sets used in literature, and found that it often outperforms the edge-based modularity algorithm.
An Experimental Investigation of XML Compression Tools
Venue: arXiv cs.DB 2008
Year: 2008

This paper presents an extensive experimental study of the state-of-the-art of XML compression tools. The study reports the behavior of nine XML compressors using a large corpus of XML documents which covers the different natures and scales of XML documents. In addition to assessing and comparing the performance characteristics of the evaluated XML compression tools, the study tries to assess the effectiveness and practicality of using these tools in the real world. Finally, we provide some guidelines and recommen- dations which are useful for helping developers and users for making an effective decision for selecting the most suitable XML compression tool for their needs.
Outer Bounds for Multiple Access Channels with Feedback using Dependence Balance
Venue: arXiv cs.IT 2008
Year: 2008

We use the idea of dependence balance to obtain a new outer bound for the capacity region of the discrete memoryless multiple access channel with noiseless feedback (MAC-FB). We consider a binary additive noisy MAC-FB whose feedback capacity is not known. The binary additive noisy MAC considered in this paper can be viewed as the discrete counterpart of the Gaussian MAC-FB. Ozarow established that the capacity region of the two-user Gaussian MAC-FB is given by the cut-set bound. Our result shows that for the discrete version of the channel considered by Ozarow, this is not the case. Direct evaluation of our outer bound is intractable due to an involved auxiliary random variable whose large cardinality prohibits an exhaustive search. We overcome this difficulty by using functional analysis to explicitly evaluate our outer bound. Our outer bound is strictly less than the cut-set bound at all points on the capacity region where feedback increases capacity. In addition, we explicitly evaluate the Cover-Leung achievable rate region for the binary additive noisy MAC-FB in consideration. Furthermore, using the tools developed for the evaluation of our outer bound, we also explicitly characterize the boundary of the feedback capacity region of the binary erasure MAC, for which the Cover-Leung achievable rate region is known to be tight. This last result confirms that the feedback strategies developed by Kramer for the binary erasure MAC are capacity achieving.
QoS Challenges and Opportunities in Wireless Sensor/Actuator Networks
Venue: arXiv cs.NI 2008
Year: 2008

A wireless sensor/actuator network (WSAN) is a group of sensors and actuators that are geographically distributed and interconnected by wireless networks. Sensors gather information about the state of physical world. Actuators react to this information by performing appropriate actions. WSANs thus enable cyber systems to monitor and manipulate the behavior of the physical world. WSANs are growing at a tremendous pace, just like the exploding evolution of Internet. Supporting quality of service (QoS) will be of critical importance for pervasive WSANs that serve as the network infrastructure of diverse applications. To spark new research and development interests in this field, this paper examines and discusses the requirements, critical challenges, and open research issues on QoS management in WSANs. A brief overview of recent progress is given.
Feedback Scheduling of Priority-Driven Control Networks
Venue: arXiv cs.NI 2008
Year: 2008

With traditional open-loop scheduling of network resources, the quality-of-control (QoC) of networked control systems (NCSs) may degrade significantly in the presence of limited bandwidth and variable workload. The goal of this work is to maximize the overall QoC of NCSs through dynamically allocating available network bandwidth. Based on codesign of control and scheduling, an integrated feedback scheduler is developed to enable flexible QoC management in dynamic environments. It encompasses a cascaded feedback scheduling module for sampling period adjustment and a direct feedback scheduling module for priority modification. The inherent characteristics of priority-driven control networks make it feasible to implement the proposed feedback scheduler in real-world systems. Extensive simulations show that the proposed approach leads to significant QoC improvement over the traditional open-loop scheduling scheme under both underloaded and overloaded network conditions.
Fuzzy Logic Control Based QoS Management in Wireless Sensor/Actuator Networks
Venue: arXiv cs.NI 2008
Year: 2008

Wireless sensor/actuator networks (WSANs) are emerging rapidly as a new generation of sensor networks. Despite intensive research in wireless sensor networks (WSNs), limited work has been found in the open literature in the field of WSANs. In particular, quality-of-service (QoS) management in WSANs remains an important issue yet to be investigated. As an attempt in this direction, this paper develops a fuzzy logic control based QoS management (FLC-QM) scheme for WSANs with constrained resources and in dynamic and unpredictable environments. Taking advantage of the feedback control technology, this scheme deals with the impact of unpredictable changes in traffic load on the QoS of WSANs. It utilizes a fuzzy logic controller inside each source sensor node to adapt sampling period to the deadline miss ratio associated with data transmission from the sensor to the actuator. The deadline miss ratio is maintained at a pre-determined desired level so that the required QoS can be achieved. The FLC-QM has the advantages of generality, scalability, and simplicity. Simulation results show that the FLC-QM can provide WSANs with QoS support.
On the Probability of the Existence of Fixed-Size Components in Random Geometric Graphs
Venue: arXiv cs.DM 2008
Year: 2008

In this work we give precise asymptotic expressions on the probability of the existence of fixed-size components at the threshold of connectivity for random geometric graphs.
Multirate Synchronous Sampling of Sparse Multiband Signals
Venue: arXiv cs.IT 2008
Year: 2008

Recent advances in optical systems make them ideal for undersampling multiband signals that have high bandwidths. In this paper we propose a new scheme for reconstructing multiband sparse signals using a small number of sampling channels. The scheme, which we call synchronous multirate sampling (SMRS), entails gathering samples synchronously at few different rates whose sum is significantly lower than the Nyquist sampling rate. The signals are reconstructed by solving a system of linear equations. We have demonstrated an accurate and robust reconstruction of signals using a small number of sampling channels that operate at relatively high rates. Sampling at higher rates increases the signal to noise ratio in samples. The SMRS scheme enables a significant reduction in the number of channels required when the sampling rate increases. We have demonstrated, using only three sampling channels, an accurate sampling and reconstruction of 4 real signals (8 bands). The matrices that are used to reconstruct the signals in the SMRS scheme also have low condition numbers. This indicates that the SMRS scheme is robust to noise in signals. The success of the SMRS scheme relies on the assumption that the sampled signals are sparse. As a result most of the sampled spectrum may be unaliased in at least one of the sampling channels. This is in contrast to multicoset sampling schemes in which an alias in one channel is equivalent to an alias in all channels. We have demonstrated that the SMRS scheme obtains similar performance using 3 sampling channels and a total sampling rate 8 times the Landau rate to an implementation of a multicoset sampling scheme that uses 6 sampling channels with a total sampling rate of 13 times the Landau rate.
Channel Capacity Limits of Cognitive Radio in Asymmetric Fading Environments
Venue: arXiv cs.IT 2008
Year: 2008

Cognitive radio technology is an innovative radio design concept which aims to increase spectrum utilization by exploiting unused spectrum in dynamically changing environments. By extending previous results, we investigate the capacity gains achievable with this dynamic spectrum approach in asymmetric fading channels. More specifically, we allow the secondary-to-primary and secondary-to-secondary user channels to undergo Rayleigh or Rician fading, with arbitrary link power. In order to compute the capacity, we derive the distributions of ratios of Rayleigh and Rician variables. Compared to the symmetric fading scenario, our results indicate several interesting features of the capacity behaviour under both average and peak received power constraints. Finally, the impact of multiple primary users on the capacity under asymmetric fading has also been studied.
Belief Propagation and Beyond for Particle Tracking
Venue: arXiv cs.IT 2008
Year: 2008

We describe a novel approach to statistical learning from particles tracked while moving in a random environment. The problem consists in inferring properties of the environment from recorded snapshots. We consider here the case of a fluid seeded with identical passive particles that diffuse and are advected by a flow. Our approach rests on efficient algorithms to estimate the weighted number of possible matchings among particles in two consecutive snapshots, the partition function of the underlying graphical model. The partition function is then maximized over the model parameters, namely diffusivity and velocity gradient. A Belief Propagation (BP) scheme is the backbone of our algorithm, providing accurate results for the flow parameters we want to learn. The BP estimate is additionally improved by incorporating Loop Series (LS) contributions. For the weighted matching problem, LS is compactly expressed as a Cauchy integral, accurately estimated by a saddle point approximation. Numerical experiments show that the quality of our improved BP algorithm is comparable to the one of a fully polynomial randomized approximation scheme, based on the Markov Chain Monte Carlo (MCMC) method, while the BP-based scheme is substantially faster than the MCMC scheme.
Data-Complexity of the Two-Variable Fragment with Counting Quantifiers
Venue: arXiv cs.LO 2008
Year: 2008

The data-complexity of both satisfiability and finite satisfiability for the two-variable fragment with counting is NP-complete; the data-complexity of both query-answering and finite query-answering for the two-variable guarded fragment with counting is co-NP-complete.
Bounded Budget Connection (BBC) Games or How to make friends and influence people, on a budget
Venue: arXiv cs.GT 2008
Year: 2008

Motivated by applications in social networks, peer-to-peer and overlay networks, we define and study the Bounded Budget Connection (BBC) game - we have a collection of n players or nodes each of whom has a budget for purchasing links; each link has a cost as well as a length and each node has a set of preference weights for each of the remaining nodes; the objective of each node is to use its budget to buy a set of outgoing links so as to minimize its sum of preference-weighted distances to the remaining nodes. We study the structural and complexity-theoretic properties of pure Nash equilibria in BBC games. We show that determining the existence of a pure Nash equilibrium in general BBC games is NP-hard. However, in a natural variant, fractional BBC games - where it is permitted to buy fractions of links - a pure Nash equilibrium always exists. A major focus is the study of (n,k)-uniform BBC games - those in which all link costs, link lengths and preference weights are equal (to 1) and all budgets are equal (to k). We show that a pure Nash equilibrium or stable graph exists for all (n,k)-uniform BBC games and that all stable graphs are essentially fair (i.e. all nodes have similar costs). We provide an explicit construction of a family of stable graphs that spans the spectrum from minimum total social cost to maximum total social cost. We also study a special family of regular graphs in which all nodes imitate the "same" buying pattern, and show that if n is sufficiently large no such regular graph can be a pure Nash equilibrium. We analyze best-response walks on the configuration defined by the uniform game. Lastly, we extend our results to the case where each node seeks to minimize its maximum distance to the other nodes.
Une nouvelle règle de combinaison répartissant le conflit - Applications en imagerie Sonar et classification de cibles Radar
Venue: arXiv cs.AI 2008
Year: 2008

These last years, there were many studies on the problem of the conflict coming from information combination, especially in evidence theory. We can summarise the solutions for manage the conflict into three different approaches: first, we can try to suppress or reduce the conflict before the combination step, secondly, we can manage the conflict in order to give no influence of the conflict in the combination step, and then take into account the conflict in the decision step, thirdly, we can take into account the conflict in the combination step. The first approach is certainly the better, but not always feasible. It is difficult to say which approach is the best between the second and the third. However, the most important is the produced results in applications. We propose here a new combination rule that distributes the conflict proportionally on the element given this conflict. We compare these different combination rules on real data in Sonar imagery and Radar target classification.
Évaluation d'une application de transmission d'images médicales avec un réseau sans fil
Venue: arXiv cs.NI 2008
Year: 2008

We offer a platform for database consultations and/or biomedical images exchanges, adapted to the low rate wireless transmission, and intended for general practitioners or specialists. The goal can be preventive, diagnostic and therapeutic. it Concerns specialties such as radiology, ultrasound, the anatomical pathology or endoscopy. The main features required in such a context are to adjust the data compression of both the specific needs of telemedicine and limited capabilities of wireless communication networks. We present our approach in which we have set out criteria on Biomedical images quality, compressed by the wavelet method to retain all the necessary information for an accurate diagnosis, and determined the characteristics of a wireless network with minimal performances for the transmission of these images within constraints related to the modality and the data flow, in this case Wifi based on the IEEE 802.11 standard. Our results will assess the capacity of this standard in terms of speed, to transmit images at a rate of 10 frames per second. It will be necessary to quantify the amount of information to add to the image datas to enable a transmission in good conditions and the appropriate modus operandi.
Defaults and Normality in Causal Structures
Venue: arXiv cs.AI 2008
Year: 2008

A serious defect with the Halpern-Pearl (HP) definition of causality is repaired by combining a theory of causality with a theory of defaults. In addition, it is shown that (despite a claim to the contrary) a cause according to the HP condition need not be a single conjunct. A definition of causality motivated by Wright's NESS test is shown to always hold for a single conjunct. Moreover, conditions that hold for all the examples considered by HP are given that guarantee that causality according to (this version) of the NESS test is equivalent to the HP definition.
Communication-optimal parallel and sequential QR and LU factorizations: theory and practice
Venue: arXiv cs.NA 2008
Year: 2008

We present parallel and sequential dense QR factorization algorithms that are both optimal (up to polylogarithmic factors) in the amount of communication they perform, and just as stable as Householder QR. Our first algorithm, Tall Skinny QR (TSQR), factors m-by-n matrices in a one-dimensional (1-D) block cyclic row layout, and is optimized for m >> n. Our second algorithm, CAQR (Communication-Avoiding QR), factors general rectangular matrices distributed in a two-dimensional block cyclic layout. It invokes TSQR for each block column factorization.
Logical Reasoning for Higher-Order Functions with Local State
Venue: arXiv cs.LO 2008
Year: 2008

We introduce an extension of Hoare logic for call-by-value higher-order functions with ML-like local reference generation. Local references may be generated dynamically and exported outside their scope, may store higher-order functions and may be used to construct complex mutable data structures. This primitive is captured logically using a predicate asserting reachability of a reference name from a possibly higher-order datum and quantifiers over hidden references. We explore the logic's descriptive and reasoning power with non-trivial programming examples combining higher-order procedures and dynamically generated local state. Axioms for reachability and local invariant play a central role for reasoning about the examples.
Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas
Venue: arXiv cs.CC 2008
Year: 2008

We prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-time algorithm. We also study some features of probability weight of correctness with respect to generalizations of Procaccia and Rosenschein's junta distributions [PR07b].
A Process Algebra Software Engineering Environment
Venue: arXiv cs.SE 2008
Year: 2008

In previous work we described how the process algebra based language PSF can be used in software engineering, using the ToolBus, a coordination architecture also based on process algebra, as implementation model. In this article we summarize that work and describe the software development process more formally by presenting the tools we use in this process in a CASE setting, leading to the PSF-ToolBus software engineering environment. We generalize the refine step in this environment towards a process algebra based software engineering workbench of which several instances can be combined to form an environment.
Identification of information tonality based on Bayesian approach and neural networks
Venue: arXiv cs.IT 2008
Year: 2008

A model of the identification of information tonality, based on Bayesian approach and neural networks was described. In the context of this paper tonality means positive or negative tone of both the whole information and its parts which are related to particular concepts. The method, its application is presented in the paper, is based on statistic regularities connected with the presence of definite lexemes in the texts. A distinctive feature of the method is its simplicity and versatility. At present ideologically similar approaches are widely used to control spam.