OpenRaiser/Intern-Atlas huggingface dataset:
Models for CSP with availability information
Venue: arXiv cs.LO 2010
Year: 2010

We consider models of CSP based on recording what events are available as possible alternatives to the events that are actually performed. We present many different varieties of such models. For each, we give a compositional semantics, congruent to the operational semantics, and prove full abstraction and no-junk results. We compare the expressiveness of the different models.
Process Behaviour: Formulae vs. Tests (Extended Abstract)
Venue: arXiv cs.LO 2010
Year: 2010

Process behaviour is often defined either in terms of the tests they satisfy, or in terms of the logical properties they enjoy. Here we compare these two approaches, using extensional testing in the style of DeNicola, Hennessy, and a recursive version of the property logic HML. We first characterise subsets of this property logic which can be captured by tests. Then we show that those subsets of the property logic capture precisely the power of tests.
Ethical Dilemma of Governmental Wiretapping
Venue: arXiv cs.CY 2010
Year: 2010

USA Government wiretapping activities is a very controversial issue. Undoubtedly this technology can assist law enforced authority to detect / identify unlawful or hostile activities; however, this task raises severe privacy concerns. In this paper, we have discussed this complex information technology issue of governmental wiretapping and how it effects both public and private liberties. Legislation has had a major impact on the uses and the stigma of wiretapping for the war on terrorism. This paper also analyzes the ethical and legal concerns inherent when discussing the benefits and concerns of wiretapping. The analysis has concluded with the effects of wiretapping laws as they relate to future government actions in their fight against terrorists.
Dependability in Aggregation by Averaging
Venue: arXiv cs.DC 2010
Year: 2010

Aggregation is an important building block of modern distributed applications, allowing the determination of meaningful properties (e.g. network size, total storage capacity, average load, majorities, etc.) that are used to direct the execution of the system. However, the majority of the existing aggregation algorithms exhibit relevant dependability issues, when prospecting their use in real application environments. In this paper, we reveal some dependability issues of aggregation algorithms based on iterative averaging techniques, giving some directions to solve them. This class of algorithms is considered robust (when compared to common tree-based approaches), being independent from the used routing topology and providing an aggregation result at all nodes. However, their robustness is strongly challenged and their correctness often compromised, when changing the assumptions of their working environment to more realistic ones. The correctness of this class of algorithms relies on the maintenance of a fundamental invariant, commonly designated as "mass conservation". We will argue that this main invariant is often broken in practical settings, and that additional mechanisms and modifications are required to maintain it, incurring in some degradation of the algorithms performance. In particular, we discuss the behavior of three representative algorithms Push-Sum Protocol, Push-Pull Gossip protocol and Distributed Random Grouping under asynchronous and faulty (with message loss and node crashes) environments. More specifically, we propose and evaluate two new versions of the Push-Pull Gossip protocol, which solve its message interleaving problem (evidenced even in a synchronous operation mode).
Avoidance of multicast incapable branching nodes for multicast routing in WDM networks
Venue: arXiv cs.NI 2010
Year: 2010

In this articlewestudy themulticast routing problem in all-opticalWDMnetworks under the spare light splitting constraint. To implement a multicast session, several light-trees may have to be used due to the limited fanouts of network nodes. Although many multicast routing algorithms have been proposed in order to reduce the total number of wavelength channels used (total cost) for a multicast session, the maximum number of wavelengths required in one fiber link (link stress) and the end-to-end delay are two parameters which are not always taken into consideration. It is known that the shortest path tree (SPT) results in the optimal end-to-end delay, but it can not be employed directly for multicast routing in sparse light splitting WDM networks. Hence, we propose a novel wavelength routing algorithm which tries to avoid the multicast incapable branching nodes (MIBs, branching nodes without splitting capability) in the shortest-path-based multicast tree to diminish the link stress. Good parts of the shortest-path-tree are retained by the algorithm to reduce the end-to-end delay. The algorithm consists of tree steps: (1) aDijkstraPro algorithmwith priority assignment and node adoption is introduced to produce a SPT with up to 38% fewer MIB nodes in the NSF topology and 46% fewerMIB nodes in the USA Longhaul topology, (2) critical articulation and deepest branch heuristics are used to process the MIB nodes, (3) a distance-based light-tree reconnection algorithm is proposed to create the multicast light-trees. Extensive simulations demonstrate the algorithm's efficiency in terms of link stress and end-to-end delay.
Isomorphisms of Algebraic Number Fields
Venue: arXiv cs.SC 2010
Year: 2010

Let $\mathbb{Q}(α)$ and $\mathbb{Q}(β)$ be algebraic number fields. We describe a new method to find (if they exist) all isomorphisms, $\mathbb{Q}(β) \rightarrow \mathbb{Q}(α)$. The algorithm is particularly efficient if the number of isomorphisms is one.
A Joint Initiative to Support the Semantic Interoperability within the GIIDA Project
Venue: arXiv cs.DL 2010
Year: 2010

The GIIDA project aims to develop a digital infrastructure for the spatial information within CNR. It is foreseen to use semantic-oriented technologies to ease information modeling and connecting, according to international standards like the ISO/IEC 11179. Complex information management systems, like GIIDA, will take benefit from the use of terminological tools like thesauri that make available a reference lexicon for the indexing and retrieval of information. Within GIIDA the goal is to make available the EARTh thesaurus (Environmental Applications Reference Thesaurus), developed by the CNR-IIA-EKOLab. A web-based software, developed by the CNR-Water Research Institute (IRSA) was implemented to allow consultation and utilization of thesaurus through the web. This service is a useful tool to ensure interoperability between thesaurus and other systems of the indexing, with, the idea of cooperating to develop a comprehensive system of knowledge organization, that could be defined integrated, open, multi-functional and multilingual. Currently the system is available in multiple languages mode (Italian - English) and navigation can be done in the following ways: Alphabetical, Hierarchical and for Themes. A full search allows to find any term by searching for the whole term or a part of it and as well as allows to filter the results by themes. Within a collaborative initiative with the CNR-Institute of Applied Mathematics and Information Technology (IMATI) a SKOS (Simple Knowledge Organization System) version of EARTh was developed. This will ensure the possibility to support the use of the thesaurus within the framework of the Semantic Web in order to be used in decentralized metadata applications
String Matching with Inversions and Translocations in Linear Average Time (Most of the Time)
Venue: arXiv cs.DS 2010
Year: 2010

We present an efficient algorithm for finding all approximate occurrences of a given pattern $p$ of length $m$ in a text $t$ of length $n$ allowing for translocations of equal length adjacent factors and inversions of factors. The algorithm is based on an efficient filtering method and has an $\bigO(nm\max(α, β))$-time complexity in the worst case and $\bigO(\max(α, β))$-space complexity, where $α$ and $β$ are respectively the maximum length of the factors involved in any translocation and inversion. Moreover we show that under the assumptions of equiprobability and independence of characters our algorithm has a $\bigO(n)$ average time complexity, whenever $σ= Ω(\log m / \log\log^{1-ε} m)$, where $ε> 0$ and $σ$ is the dimension of the alphabet. Experiments show that the new proposed algorithm achieves very good results in practical cases.
Faster Query Answering in Probabilistic Databases using Read-Once Functions
Venue: arXiv cs.DB 2010
Year: 2010

A boolean expression is in read-once form if each of its variables appears exactly once. When the variables denote independent events in a probability space, the probability of the event denoted by the whole expression in read-once form can be computed in polynomial time (whereas the general problem for arbitrary expressions is #P-complete). Known approaches to checking read-once property seem to require putting these expressions in disjunctive normal form. In this paper, we tell a better story for a large subclass of boolean event expressions: those that are generated by conjunctive queries without self-joins and on tuple-independent probabilistic databases. We first show that given a tuple-independent representation and the provenance graph of an SPJ query plan without self-joins, we can, without using the DNF of a result event expression, efficiently compute its co-occurrence graph. From this, the read-once form can already, if it exists, be computed efficiently using existing techniques. Our second and key contribution is a complete, efficient, and simple to implement algorithm for computing the read-once forms (whenever they exist) directly, using a new concept, that of co-table graph, which can be significantly smaller than the co-occurrence graph.
Fractional counting of citations in research evaluation: An option for cross- and interdisciplinary assessments
Venue: arXiv cs.DL 2010
Year: 2010

In the case of the scientometric evaluation of multi- or interdisciplinary units one risks to compare apples with oranges: each paper has to assessed in comparison to an appropriate reference set. We suggest that the set of citing papers first can be considered as the relevant representation of the field of impact. In order to normalize for differences in citation behavior among fields, citations can be fractionally counted proportionately to the length of the reference lists in the citing papers. This new method enables us to compare among units with different disciplinary affiliations at the paper level and also to assess the statistical significance of differences among sets. Twenty-seven departments of the Tsinghua University in Beijing are thus compared. Among them, the Department of Chinese Language and Linguistics is upgraded from the 19th to the second position in the ranking. The overall impact of 19 of the 27 departments is not significantly different at the 5% level when thus normalized for different citation potentials.
Entropy power inequality for a family of discrete random variables
Venue: arXiv cs.IT 2010
Year: 2010

It is known that the Entropy Power Inequality (EPI) always holds if the random variables have density. Not much work has been done to identify discrete distributions for which the inequality holds with the differential entropy replaced by the discrete entropy. Harremoës and Vignat showed that it holds for the pair (B(m,p), B(n,p)), m,n \in \mathbb{N}, (where B(n,p) is a Binomial distribution with n trials each with success probability p) for p = 0.5. In this paper, we considerably expand the set of Binomial distributions for which the inequality holds and, in particular, identify n_0(p) such that for all m,n \geq n_0(p), the EPI holds for (B(m,p), B(n,p)). We further show that the EPI holds for the discrete random variables that can be expressed as the sum of n independent identical distributed (IID) discrete random variables for large n.
Compressive Sensing Over Networks
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we demonstrate some applications of compressive sensing over networks. We make a connection between compressive sensing and traditional information theoretic techniques in source coding and channel coding. Our results provide an explicit trade-off between the rate and the decoding complexity. The key difference of compressive sensing and traditional information theoretic approaches is at their decoding side. Although optimal decoders to recover the original signal, compressed by source coding have high complexity, the compressive sensing decoder is a linear or convex optimization. First, we investigate applications of compressive sensing on distributed compression of correlated sources. Here, by using compressive sensing, we propose a compression scheme for a family of correlated sources with a modularized decoder, providing a trade-off between the compression rate and the decoding complexity. We call this scheme Sparse Distributed Compression. We use this compression scheme for a general multicast network with correlated sources. Here, we first decode some of the sources by a network decoding technique and then, we use a compressive sensing decoder to obtain the whole sources. Then, we investigate applications of compressive sensing on channel coding. We propose a coding scheme that combines compressive sensing and random channel coding for a high-SNR point-to-point Gaussian channel. We call this scheme Sparse Channel Coding. We propose a modularized decoder providing a trade-off between the capacity loss and the decoding complexity. At the receiver side, first, we use a compressive sensing decoder on a noisy signal to obtain a noisy estimate of the original signal and then, we apply a traditional channel coding decoder to find the original signal.
Lower Bounds for the Smoothed Number of Pareto optimal Solutions
Venue: arXiv cs.DS 2010
Year: 2010

In 2009, Roeglin and Teng showed that the smoothed number of Pareto optimal solutions of linear multi-criteria optimization problems is polynomially bounded in the number $n$ of variables and the maximum density $ϕ$ of the semi-random input model for any fixed number of objective functions. Their bound is, however, not very practical because the exponents grow exponentially in the number $d+1$ of objective functions. In a recent breakthrough, Moitra and O'Donnell improved this bound significantly to $O(n^{2d} ϕ^{d(d+1)/2})$. An "intriguing problem", which Moitra and O'Donnell formulate in their paper, is how much further this bound can be improved. The previous lower bounds do not exclude the possibility of a polynomial upper bound whose degree does not depend on $d$. In this paper we resolve this question by constructing a class of instances with $Ω((n ϕ)^{(d-\log{d}) \cdot (1-Θ{1/ϕ})})$ Pareto optimal solutions in expectation. For the bi-criteria case we present a higher lower bound of $Ω(n^2 ϕ^{1 - Θ{1/ϕ}})$, which almost matches the known upper bound of $O(n^2 ϕ)$.
Image Deblurring and Super-resolution by Adaptive Sparse Domain Selection and Adaptive Regularization
Venue: arXiv cs.CV 2010
Year: 2010

As a powerful statistical image modeling technique, sparse representation has been successfully used in various image restoration applications. The success of sparse representation owes to the development of l1-norm optimization techniques, and the fact that natural images are intrinsically sparse in some domain. The image restoration quality largely depends on whether the employed sparse domain can represent well the underlying image. Considering that the contents can vary significantly across different images or different patches in a single image, we propose to learn various sets of bases from a pre-collected dataset of example image patches, and then for a given patch to be processed, one set of bases are adaptively selected to characterize the local sparse domain. We further introduce two adaptive regularization terms into the sparse representation framework. First, a set of autoregressive (AR) models are learned from the dataset of example image patches. The best fitted AR models to a given patch are adaptively selected to regularize the image local structures. Second, the image non-local self-similarity is introduced as another regularization term. In addition, the sparsity regularization parameter is adaptively estimated for better image restoration performance. Extensive experiments on image deblurring and super-resolution validate that by using adaptive sparse domain selection and adaptive regularization, the proposed method achieves much better results than many state-of-the-art algorithms in terms of both PSNR and visual perception.
Tight lower bounds for the size of epsilon-nets
Venue: arXiv cs.DM 2010
Year: 2010

According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an $\eps$-net of size $O\left(\frac{1}{\eps}\log\frac1{\eps}\right)$. Using probabilistic techniques, Pach and Woeginger (1990) showed that there exist range spaces of VC-dimension 2, for which the above bound can be attained. The only known range spaces of small VC-dimension, in which the ranges are geometric objects in some Euclidean space and the size of the smallest $\eps$-nets is superlinear in $\frac1{\eps}$, were found by Alon (2010). In his examples, the size of the smallest $\eps$-nets is $Ω\left(\frac{1}{\eps}g(\frac{1}{\eps})\right)$, where $g$ is an extremely slowly growing function, closely related to the inverse Ackermann function. \smallskip We show that there exist geometrically defined range spaces, already of VC-dimension $2$, in which the size of the smallest $\eps$-nets is $Ω\left(\frac{1}{\eps}\log\frac{1}{\eps}\right)$. We also construct range spaces induced by axis-parallel rectangles in the plane, in which the size of the smallest $\eps$-nets is $Ω\left(\frac{1}{\eps}\log\log\frac{1}{\eps}\right)$. By a theorem of Aronov, Ezra, and Sharir (2010), this bound is tight.
Simultaneous Sequential Detection of Multiple Interacting Faults
Venue: arXiv cs.IT 2010
Year: 2010

Single fault sequential change point problems have become important in modeling for various phenomena in large distributed systems, such as sensor networks. But such systems in many situations present multiple interacting faults. For example, individual sensors in a network may fail and detection is performed by comparing measurements between sensors, resulting in statistical dependency among faults. We present a new formulation for multiple interacting faults in a distributed system. The formulation includes specifications of how individual subsystems composing the large system may fail, the information that can be shared among these subsystems and the interaction pattern between faults. We then specify a new sequential algorithm for detecting these faults. The main feature of the algorithm is that it uses composite stopping rules for a subsystem that depend on the decision of other subsystems. We provide asymptotic false alarm and detection delay analysis for this algorithm in the Bayesian setting and show that under certain conditions the algorithm is optimal. The analysis methodology relies on novel detailed comparison techniques between stopping times. We validate the approach with some simulations.
Decomposition Complexity
Venue: arXiv cs.FL 2010
Year: 2010

We consider a problem of decomposition of a ternary function into a composition of binary ones from the viewpoint of communication complexity and algorithmic information theory as well as some applications to cellular automata.
1D Effectively Closed Subshifts and 2D Tilings
Venue: arXiv cs.DM 2010
Year: 2010

Michael Hochman showed that every 1D effectively closed subshift can be simulated by a 3D subshift of finite type and asked whether the same can be done in 2D. It turned out that the answer is positive and necessary tools were already developed in tilings theory. We discuss two alternative approaches: first, developed by N. Aubrun and M. Sablik, goes back to Leonid Levin; the second one, developed by the authors, goes back to Peter Gacs.
Slopes of Tilings
Venue: arXiv cs.DM 2010
Year: 2010

We study here slopes of periodicity of tilings. A tiling is of slope if it is periodic along direction but has no other direction of periodicity. We characterize in this paper the set of slopes we can achieve with tilings, and prove they coincide with recursively enumerable sets of rationals.
Time-Symmetric Cellular Automata
Venue: arXiv cs.DM 2010
Year: 2010

Together with the concept of reversibility, another relevant physical notion is time-symmetry, which expresses that there is no way of distinguishing between backward and forward time directions. This notion, found in physical theories, has been neglected in the area of discrete dynamical systems. Here we formalize it in the context of cellular automata and establish some basic facts and relations. We also state some open problems that may encourage further research on the topic.
An Approximation Algorithm for the Euclidean Bottleneck Steiner Tree Problem
Venue: arXiv cs.CG 2010
Year: 2010

Given two sets of points in the plane, $P$ of $n$ terminals and $S$ of $m$ Steiner points, a Steiner tree of $P$ is a tree spanning all points of $P$ and some (or none or all) points of $S$. A Steiner tree with length of longest edge minimized is called a bottleneck Steiner tree. In this paper, we study the Euclidean bottleneck Steiner tree problem: given two sets, $P$ and $S$, and a positive integer $k \le m$, find a bottleneck Steiner tree of $P$ with at most $k$ Steiner points. The problem has application in the design of wireless communication networks. We first show that the problem is NP-hard and cannot be approximated within factor $\sqrt{2}$, unless $P=NP$. Then, we present a polynomial-time approximation algorithm with performance ratio 2.
User Centered and Ontology Based Information Retrieval System for Life Sciences
Venue: arXiv cs.IR 2010
Year: 2010

Because of the increasing number of electronic data, designing efficient tools to retrieve and exploit documents is a major challenge. Current search engines suffer from two main drawbacks: there is limited interaction with the list of retrieved documents and no explanation for their adequacy to the query. Users may thus be confused by the selection and have no idea how to adapt their query so that the results match their expectations. This paper describes a request method and an environment based on aggregating models to assess the relevance of documents annotated by concepts of ontology. The selection of documents is then displayed in a semantic map to provide graphical indications that make explicit to what extent they match the user's query; this man/machine interface favors a more interactive exploration of data corpus.
Fundamentals of Semantic Web Technologies in Medical Environments: a case in breast cancer risk estimation
Venue: arXiv cs.OH 2010
Year: 2010

Risk estimation of developing breast cancer poses as the first prevention method for early diagnosis. Furthermore, data integration from different departments involved in the process plays a key role. In order to guarantee patient safety, the whole process should be orchestrated and monitored automatically. Support for the solution will be a linked data cloud, composed by all the departments that take part in the process, combined with rule engines.