OpenRaiser/Intern-Atlas huggingface dataset:
Stabilizing Maximal Independent Set in Unidirectional Networks is Hard
Venue: arXiv cs.DS 2009
Year: 2009

A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the system recovers from this catastrophic situation without external intervention in finite time. In this paper, we consider the problem of constructing self-stabilizingly a \emph{maximal independent set} in uniform unidirectional networks of arbitrary shape. On the negative side, we present evidence that in uniform networks, \emph{deterministic} self-stabilization of this problem is \emph{impossible}. Also, the \emph{silence} property (\emph{i.e.} having communication fixed from some point in every execution) is impossible to guarantee, either for deterministic or for probabilistic variants of protocols. On the positive side, we present a deterministic protocol for networks with arbitrary unidirectional networks with unique identifiers that exhibits polynomial space and time complexity in asynchronous scheduling. We complement the study with probabilistic protocols for the uniform case: the first probabilistic protocol requires infinite memory but copes with asynchronous scheduling, while the second probabilistic protocol has polynomial space complexity but can only handle synchronous scheduling. Both probabilistic solutions have expected polynomial time complexity.
Discovering Matching Dependencies
Venue: arXiv cs.DB 2009
Year: 2009

The concept of matching dependencies (mds) is recently pro- posed for specifying matching rules for object identification. Similar to the functional dependencies (with conditions), mds can also be applied to various data quality applications such as violation detection. In this paper, we study the problem of discovering matching dependencies from a given database instance. First, we formally define the measures, support and confidence, for evaluating utility of mds in the given database instance. Then, we study the discovery of mds with certain utility requirements of support and confidence. Exact algorithms are developed, together with pruning strategies to improve the time performance. Since the exact algorithm has to traverse all the data during the computation, we propose an approximate solution which only use some of the data. A bound of relative errors introduced by the approximation is also developed. Finally, our experimental evaluation demonstrates the efficiency of the proposed methods.
Optimal Policies Search for Sensor Management
Venue: arXiv cs.LG 2009
Year: 2009

This paper introduces a new approach to solve sensor management problems. Classically sensor management problems can be well formalized as Partially-Observed Markov Decision Processes (POMPD). The original approach developped here consists in deriving the optimal parameterized policy based on a stochastic gradient estimation. We assume in this work that it is possible to learn the optimal policy off-line (in simulation) using models of the environement and of the sensor(s). The learned policy can then be used to manage the sensor(s). In order to approximate the gradient in a stochastic context, we introduce a new method to approximate the gradient, based on Infinitesimal Perturbation Approximation (IPA). The effectiveness of this general framework is illustrated by the managing of an Electronically Scanned Array Radar. First simulations results are finally proposed.
Sending a Bivariate Gaussian Source over a Gaussian MAC with Feedback
Venue: arXiv cs.IT 2009
Year: 2009

We study the power-versus-distortion trade-off for the transmission of a memoryless bivariate Gaussian source over a two-to-one Gaussian multiple-access channel with perfect causal feedback. In this problem, each of two separate transmitters observes a different component of a memoryless bivariate Gaussian source as well as the feedback from the channel output of the previous time-instants. Based on the observed source sequence and the feedback, each transmitter then describes its source component to the common receiver via an average-power constrained Gaussian multiple-access channel. From the resulting channel output, the receiver wishes to reconstruct both source components with the least possible expected squared-error distortion. We study the set of distortion pairs that can be achieved by the receiver on the two source components. We present sufficient conditions and necessary conditions for the achievability of a distortion pair. These conditions are expressed in terms of the source correlation and of the signal-to-noise ratio (SNR) of the channel. In several cases the necessary conditions and sufficient conditions coincide. This allows us to show that if the channel SNR is below a certain threshold, then an uncoded transmission scheme that ignores the feedback is optimal. Thus, below this SNR-threshold feedback is useless. We also derive the precise high-SNR asymptotics of optimal schemes.
Visual Conceptualizations and Models of Science
Venue: arXiv cs.DL 2009
Year: 2009

This Journal of Informetrics special issue aims to improve our understanding of the structure and dynamics of science by reviewing and advancing existing conceptualizations and models of scholarly activity. Several of these conceptualizations and models have visual manifestations supporting the combination and comparison of theories and approaches developed in different disciplines of science. Subsequently, we discuss challenges towards a theoretically grounded and practically useful science of science and provide a brief chronological review of relevant work. Then, we exemplarily present three conceptualizations of science that attempt to provide frameworks for the comparison and combination of existing approaches, theories, laws, and measurements. Finally, we discuss the contributions of and interlinkages among the eight papers included in this issue. Each paper makes a unique contribution towards conceptualizations and models of science and roots this contribution in a review and comparison with existing work.
Optimized Implementation of Elliptic Curve Based Additive Homomorphic Encryption for Wireless Sensor Networks
Venue: arXiv cs.CR 2009
Year: 2009

When deploying wireless sensor networks (WSNs) in public environments it may become necessary to secure their data storage and transmission against possible attacks such as node-compromise and eavesdropping. The nodes feature only small computational and energy resources, thus requiring efficient algorithms. As a solution for this problem the TinyPEDS approach was proposed in [7], which utilizes the Elliptic Curve ElGamal (EC-ElGamal) cryptosystem for additive homomorphic encryption allowing concealed data aggregation. This work presents an optimized implementation of EC-ElGamal on a MicaZ mote, which is a typical sensor node platform with 8-bit processor for WSNs. Compared to the best previous result, our implementation is at least 44% faster for fixed-point multiplication. Because most parts of the algorithm are similar to standard Elliptic Curve algorithms, the results may be reused in other realizations on constrained devices as well.
Designing a GUI for Proofs - Evaluation of an HCI Experiment
Venue: arXiv cs.AI 2009
Year: 2009

Often user interfaces of theorem proving systems focus on assisting particularly trained and skilled users, i.e., proof experts. As a result, the systems are difficult to use for non-expert users. This paper describes a paper and pencil HCI experiment, in which (non-expert) students were asked to make suggestions for a GUI for an interactive system for mathematical proofs. They had to explain the usage of the GUI by applying it to construct a proof sketch for a given theorem. The evaluation of the experiment provides insights for the interaction design for non-expert users and the needs and wants of this user group.
Overlay Structure for Large Scale Content Sharing: Leveraging Geography as the Basis for Routing Locality
Venue: arXiv cs.NI 2009
Year: 2009

In this paper we place our arguments on two related issues in the design of generalized structured peer-to-peer overlays. First, we argue that for the large-scale content-sharing applications, lookup and content transport functions need to be treated separately. Second, to create a location-based routing overlay suitable for content sharing and other applications, we argue that off-the-shelf geographic coordinates of Internet-connected hosts can be used as a basis. We then outline the design principles and present a design for the generalized routing overlay based on adaptive hierarchical partitioning of the geographical space.
Conditional Probability Tree Estimation Analysis and Algorithms
Venue: arXiv cs.LG 2009
Year: 2009

We consider the problem of estimating the conditional probability of a label in time $O(\log n)$, where $n$ is the number of possible labels. We analyze a natural reduction of this problem to a set of binary regression problems organized in a tree structure, proving a regret bound that scales with the depth of the tree. Motivated by this analysis, we propose the first online algorithm which provably constructs a logarithmic depth tree on the set of labels to solve this problem. We test the algorithm empirically, showing that it works succesfully on a dataset with roughly $10^6$ labels.
Non linear system become linear system
Venue: arXiv cs.DM 2009
Year: 2009

The present paper refers to the theory and the practice of the systems regarding non-linear systems and their applications. We aimed the integration of these systems to elaborate their response as well as to highlight some outstanding features.
Evaluation d'une requete en SQL
Venue: arXiv cs.DB 2009
Year: 2009

The objective of this paper is to show how the interrogation processor responds to SQL interrogation. The interrogation processor is split into two parts. The first, called the interrogation compiler translates an SQL query into a plan of physical execution. The second, called evaluation query runs the execution plan.
Capacity Scaling Laws for Underwater Networks
Venue: arXiv cs.IT 2009
Year: 2009

The underwater acoustic channel is characterized by a path loss that depends not only on the transmission distance, but also on the signal frequency. Signals transmitted from one user to another over a distance $l$ are subject to a power loss of $l^{-α}{a(f)}^{-l}$. Although a terrestrial radio channel can be modeled similarly, the underwater acoustic channel has different characteristics. The spreading factor $α$, related to the geometry of propagation, has values in the range $1 \leq α\leq 2$. The absorption coefficient $a(f)$ is a rapidly increasing function of frequency: it is three orders of magnitude greater at 100 kHz than at a few Hz. Existing results for capacity of wireless networks correspond to scenarios for which $a(f) = 1$, or a constant greater than one, and $α\geq 2$. These results cannot be applied to underwater acoustic networks in which the attenuation varies over the system bandwidth. We use a water-filling argument to assess the minimum transmission power and optimum transmission band as functions of the link distance and desired data rate, and study the capacity scaling laws under this model.
Graph polynomials and approximation of partition functions with Loopy Belief Propagation
Venue: arXiv cs.DM 2009
Year: 2009

The Bethe approximation, or loopy belief propagation algorithm is a successful method for approximating partition functions of probabilistic models associated with a graph. Chertkov and Chernyak derived an interesting formula called Loop Series Expansion, which is an expansion of the partition function. The main term of the series is the Bethe approximation while other terms are labeled by subgraphs called generalized loops. In our recent paper, we derive the loop series expansion in form of a polynomial with coefficients positive integers, and extend the result to the expansion of marginals. In this paper, we give more clear derivation for the results and discuss the properties of the polynomial which is introduced in the paper.
Nonnegative approximations of nonnegative tensors
Venue: arXiv cs.NA 2009
Year: 2009

We study the decomposition of a nonnegative tensor into a minimal sum of outer product of nonnegative vectors and the associated parsimonious naive Bayes probabilistic model. We show that the corresponding approximation problem, which is central to nonnegative PARAFAC, will always have optimal solutions. The result holds for any choice of norms and, under a mild assumption, even Bregman divergences.
Multidimensional Online Robot Motion
Venue: arXiv cs.CG 2009
Year: 2009

We consider three related problems of robot movement in arbitrary dimensions: coverage, search, and navigation. For each problem, a spherical robot is asked to accomplish a motion-related task in an unknown environment whose geometry is learned by the robot during navigation. The robot is assumed to have tactile and global positioning sensors. We view these problems from the perspective of (non-linear) competitiveness as defined by Gabriely and Rimon. We first show that in 3 dimensions and higher, there is no upper bound on competitiveness: every online algorithm can do arbitrarily badly compared to the optimal. We then modify the problems by assuming a fixed clearance parameter. We are able to give optimally competitive algorithms under this assumption.
Act of CVT and EVT In The Formation of Number-Theoretic Fractals
Venue: arXiv cs.DM 2009
Year: 2009

In this paper we have defined two functions that have been used to construct different fractals having fractal dimensions between 1 and 2. More precisely, we can say that one of our defined functions produce the fractals whose fractal dimension lies in [1.58, 2) and rest function produce the fractals whose fractal dimension lies in (1, 1.58]. Also we tried to calculate the amount of increment of fractal dimension in accordance with base of the number systems. And in switching of fractals from one base to another, the increment of fractal dimension is constant, which is 1.58, its quite surprising!
Delocalization transition for the Google matrix
Venue: arXiv cs.IR 2009
Year: 2009

We study the localization properties of eigenvectors of the Google matrix, generated both from the World Wide Web and from the Albert-Barabasi model of networks. We establish the emergence of a delocalization phase for the PageRank vector when network parameters are changed. In the phase of localized PageRank, a delocalization takes place in the complex plane of eigenvalues of the matrix, leading to delocalized relaxation modes. We argue that the efficiency of information retrieval by Google-type search is strongly affected in the phase of delocalized PageRank.
Stochastic Models of User-Contributory Web Sites
Venue: arXiv cs.CY 2009
Year: 2009

We describe a general stochastic processes-based approach to modeling user-contributory web sites, where users create, rate and share content. These models describe aggregate measures of activity and how they arise from simple models of individual users. This approach provides a tractable method to understand user activity on the web site and how this activity depends on web site design choices, especially the choice of what information about other users' behaviors is shown to each user. We illustrate this modeling approach in the context of user-created content on the news rating site Digg.
Faith in the Algorithm, Part 2: Computational Eudaemonics
Venue: arXiv cs.CY 2009
Year: 2009

Eudaemonics is the study of the nature, causes, and conditions of human well-being. According to the ethical theory of eudaemonia, reaping satisfaction and fulfillment from life is not only a desirable end, but a moral responsibility. However, in modern society, many individuals struggle to meet this responsibility. Computational mechanisms could better enable individuals to achieve eudaemonia by yielding practical real-world systems that embody algorithms that promote human flourishing. This article presents eudaemonic systems as the evolutionary goal of the present day recommender system.
CCS-Based Dynamic Logics for Communicating Concurrent Programs
Venue: arXiv cs.LO 2009
Year: 2009

This work presents three increasingly expressive Dynamic Logics in which the programs are CCS processes (sCCS-PDL, CCS-PDL and XCCS-PDL). Their goal is to reason about properties of concurrent programs and systems described using CCS. In order to accomplish that, CCS's operators and constructions are added to a basic modal logic in order to create dynamic logics that are suitable for the description and verification of properties of communicating, concurrent and non-deterministic programs and systems, in a similar way as PDL is used for the sequential case. We provide complete axiomatizations for the three logics. Unlike Peleg's Concurrent PDL with Channels, our logics have a simple Kripke semantics, complete axiomatizations and the finite model property.
The mdt algorithm
Venue: arXiv cs.NI 2009
Year: 2009

Link state routing protocols such as OSPF or IS-IS currently use only best paths to forward IP packets throughout a domain. The optimality of sub-paths ensures consistency of hop by hop forwarding although paths, calculated using Dijkstra algorithm, are recursively composed. According to the link metric, the diversity of existing paths can be underestimated using only best paths. Hence, it reduces potential benefits of multipath applications such as load balancing and fast rerouting. In this paper, we propose a low time complexity multipath computation algorithm able to calculate at least two paths with a different first hop between all pairs of nodes in the network if such next hops exist. Using real and generated topologies, we evaluate and compare the complexity of our proposition with several techniques. Simulation results suggest that the path diversity achieved with our proposition is approximatively the same that the one obtained using consecutive Dijsktra computations, but with a lower time complexity.
Interference Alignment with Asymmetric Complex Signaling - Settling the Host-Madsen-Nosratinia Conjecture
Venue: arXiv cs.IT 2009
Year: 2009

It has been conjectured by Host-Madsen and Nosratinia that complex Gaussian interference channels with constant channel coefficients have only one degree-of-freedom regardless of the number of users. While several examples are known of constant channels that achieve more than 1 degree of freedom, these special cases only span a subset of measure zero. In other words, for almost all channel coefficient values, it is not known if more than 1 degree-of-freedom is achievable. In this paper, we settle the Host-Madsen-Nosratinia conjecture in the negative. We show that at least 1.2 degrees-of-freedom are achievable for all values of complex channel coefficients except for a subset of measure zero. For the class of linear beamforming and interference alignment schemes considered in this paper, it is also shown that 1.2 is the maximum number of degrees of freedom achievable on the complex Gaussian 3 user interference channel with constant channel coefficients, for almost all values of channel coefficients. To establish the achievability of 1.2 degrees of freedom we introduce the novel idea of asymmetric complex signaling - i.e., the inputs are chosen to be complex but not circularly symmetric. It is shown that unlike Gaussian point-to-point, multiple-access and broadcast channels where circularly symmetric complex Gaussian inputs are optimal, for interference channels optimal inputs are in general asymmetric. With asymmetric complex signaling, we also show that the 2 user complex Gaussian X channel with constant channel coefficients achieves the outer bound of 4/3 degrees-of-freedom, i.e., the assumption of time-variations/frequency-selectivity used in prior work to establish the same result, is not needed.
Design, development and implementation of a tool for construction of declarative functional descriptions of semantic web services based on WSMO methodology
Venue: arXiv cs.AI 2009
Year: 2009

Semantic web services (SWS) are self-contained, self-describing, semantically marked-up software resources that can be published, discovered, composed and executed across the Web in a semi-automatic way. They are a key component of the future Semantic Web, in which networked computer programs become providers and users of information at the same time. This work focuses on developing a full-life-cycle software toolset for creating and maintaining Semantic Web Services (SWSs) based on the Web Service Modelling Ontology (WSMO) framework. A main part of WSMO-based SWS is service capability - a declarative description of Web service functionality. A formal syntax and semantics for such a description is provided by Web Service Modeling Language (WSML), which is based on different logical formalisms, namely, Description Logics, First-Order Logic and Logic Programming. A WSML description of a Web service capability is represented as a set of complex logical expressions (axioms). We develop a specialized user-friendly tool for constructing and editing WSMO-based SWS capabilities. Since the users of this tool are not specialists in first-order logic, a graphical way for constricting and editing axioms is proposed. The designed process for constructing logical expressions is ontology-driven, which abstracts away as much as possible from any concrete syntax of logical language. We propose several mechanisms to guarantees the semantic consistency of the produced logical expressions. The tool is implemented in Java using Eclipse for IDE and GEF (Graphical Editing Framework) for visualization.
Theory of Carry Value Transformation (CVT) and its Application in Fractal formation
Venue: arXiv cs.DM 2009
Year: 2009

In this paper the theory of Carry Value Transformation (CVT) is designed and developed on a pair of n-bit strings and is used to produce many interesting patterns. One of them is found to be a self-similar fractal whose dimension is same as the dimension of the Sierpinski triangle. Different construction procedures like L-system, Cellular Automata rule, Tilling for this fractal are obtained which signifies that like other tools CVT can also be used for the formation of self-similar fractals. It is shown that CVT can be used for the production of periodic as well as chaotic patterns. Also, the analytical and algebraic properties of CVT are discussed. The definition of CVT in two-dimension is slightly modified and its mathematical properties are highlighted. Finally, the extension of CVT and modified CVT (MCVT) are done in higher dimensions.
Eligibility Propagation to Speed up Time Hopping for Reinforcement Learning
Venue: arXiv cs.AI 2009
Year: 2009

A mechanism called Eligibility Propagation is proposed to speed up the Time Hopping technique used for faster Reinforcement Learning in simulations. Eligibility Propagation provides for Time Hopping similar abilities to what eligibility traces provide for conventional Reinforcement Learning. It propagates values from one state to all of its temporal predecessors using a state transitions graph. Experiments on a simulated biped crawling robot confirm that Eligibility Propagation accelerates the learning process more than 3 times.