OpenRaiser/Intern-Atlas huggingface dataset:
An Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulas
Venue: arXiv cs.CC 2009
Year: 2009

Haken proved that every resolution refutation of the pigeonhole formula has at least exponential size. Groote and Zantema proved that a particular OBDD computation of the pigeonhole formula has an exponential size. Here we show that any arbitrary OBDD refutation of the pigeonhole formula has an exponential size, too: we prove that the size of one of the intermediate OBDDs is at least $Ω(1.025^n)$.
Towards maintainer script modernization in FOSS distributions
Venue: arXiv cs.SE 2009
Year: 2009

Free and Open Source Software (FOSS) distributions are complex software systems, made of thousands packages that evolve rapidly, independently, and without centralized coordination. During packages upgrades, corner case failures can be encountered and are hard to deal with, especially when they are due to misbehaving maintainer scripts: executable code snippets used to finalize package configuration. In this paper we report a software modernization experience, the process of representing existing legacy systems in terms of models, applied to FOSS distributions. We present a process to define meta-models that enable dealing with upgrade failures and help rolling back from them, taking into account maintainer scripts. The process has been applied to widely used FOSS distributions and we report about such experiences.
An Algorithm for Mining Multidimensional Fuzzy Association Rules
Venue: arXiv cs.IR 2009
Year: 2009

Multidimensional association rule mining searches for interesting relationship among the values from different dimensions or attributes in a relational database. In this method the correlation is among set of dimensions i.e., the items forming a rule come from different dimensions. Therefore each dimension should be partitioned at the fuzzy set level. This paper proposes a new algorithm for generating multidimensional association rules by utilizing fuzzy sets. A database consisting of fuzzy transactions, the Apriory property is employed to prune the useless candidates, itemsets.
Wiretapping a hidden network
Venue: arXiv cs.GT 2009
Year: 2009

We consider the problem of maximizing the probability of hitting a strategically chosen hidden virtual network by placing a wiretap on a single link of a communication network. This can be seen as a two-player win-lose (zero-sum) game that we call the wiretap game. The value of this game is the greatest probability that the wiretapper can secure for hitting the virtual network. The value is shown to equal the reciprocal of the strength of the underlying graph. We efficiently compute a unique partition of the edges of the graph, called the prime-partition, and find the set of pure strategies of the hider that are best responses against every maxmin strategy of the wiretapper. Using these special pure strategies of the hider, which we call omni-connected-spanning-subgraphs, we define a partial order on the elements of the prime-partition. From the partial order, we obtain a linear number of simple two-variable inequalities that define the maxmin-polytope, and a characterization of its extreme points. Our definition of the partial order allows us to find all equilibrium strategies of the wiretapper that minimize the number of pure best responses of the hider. Among these strategies, we efficiently compute the unique strategy that maximizes the least punishment that the hider incurs for playing a pure strategy that is not a best response. Finally, we show that this unique strategy is the nucleolus of the recently studied simple cooperative spanning connectivity game.
A Universal Crease Pattern for Folding Orthogonal Shapes
Venue: arXiv cs.CG 2009
Year: 2009

We present a universal crease pattern--known in geometry as the tetrakis tiling and in origami as box pleating--that can fold into any object made up of unit cubes joined face-to-face (polycubes). More precisely, there is one universal finite crease pattern for each number n of unit cubes that need to be folded. This result contrasts previous universality results for origami, which require a different crease pattern for each target object, and confirms intuition in the origami community that box pleating is a powerful design technique.
Linear Complementarity Algorithms for Infinite Games
Venue: arXiv cs.GT 2009
Year: 2009

The performance of two pivoting algorithms, due to Lemke and Cottle and Dantzig, is studied on linear complementarity problems (LCPs) that arise from infinite games, such as parity, average-reward, and discounted games. The algorithms have not been previously studied in the context of infinite games, and they offer alternatives to the classical strategy-improvement algorithms. The two algorithms are described purely in terms of discounted games, thus bypassing the reduction from the games to LCPs, and hence facilitating a better understanding of the algorithms when applied to games. A family of parity games is given, on which both algorithms run in exponential time, indicating that in the worst case they perform no better for parity, average-reward, or discounted games than they do for general P-matrix LCPs.
Approximating Loops in a Shortest Homology Basis from Point Data
Venue: arXiv cs.CG 2009
Year: 2009

Inference of topological and geometric attributes of a hidden manifold from its point data is a fundamental problem arising in many scientific studies and engineering applications. In this paper we present an algorithm to compute a set of loops from a point data that presumably sample a smooth manifold $M\subset \mathbb{R}^d$. These loops approximate a {\em shortest} basis of the one dimensional homology group $H_1(M)$ over coefficients in finite field $\mathbb{Z}_2$. Previous results addressed the issue of computing the rank of the homology groups from point data, but there is no result on approximating the shortest basis of a manifold from its point sample. In arriving our result, we also present a polynomial time algorithm for computing a shortest basis of $H_1(K)$ for any finite {\em simplicial complex} $K$ whose edges have non-negative weights.
Criticisms of modelling packet traffic using long-range dependence
Venue: arXiv cs.NI 2009
Year: 2009

This paper criticises the notion that long-range dependence is an important contributor to the queuing behaviour of real Internet traffic. The idea is questioned in two different ways. Firstly, a class of models used to simulate Internet traffic is shown to have important theoretical flaws. It is shown that this behaviour is inconsistent with the behaviour of real traffic traces. Secondly, the notion that long-range correlations significantly affects the queuing performance of traffic is investigated by destroying those correlations in real traffic traces (by reordering). It is shown that the longer ranges of correlations are not important except in one case with an extremely high load.
An Analysis of Energy Consumption on ACK plus Rate Packet in Rate Based Transport Protocol
Venue: arXiv cs.NI 2009
Year: 2009

Rate based transport protocol determines the rate of data transmission between the sender and receiver and then sends the data according to that rate. To notify the rate to the sender, the receiver sends ACKplusRate packet based on epoch timer expiry. In this paper, through detailed arguments and simulation it is shown that the transmission of ACKplusRate packet based on epoch timer expiry consumes more energy in network with low mobility. To overcome this problem, a new technique called Dynamic Rate Feedback (DRF) is proposed. DRF sends ACKplusRate whenever there is a change in rate of (plus or minus) 25 percent than the previous rate. Based on ns2 simulation DRF is compared with a reliable transport protocol for ad hoc network (ATP)
Post-Processing of Discovered Association Rules Using Ontologies
Venue: arXiv cs.LG 2009
Year: 2009

In Data Mining, the usefulness of association rules is strongly limited by the huge amount of delivered rules. In this paper we propose a new approach to prune and filter discovered rules. Using Domain Ontologies, we strengthen the integration of user knowledge in the post-processing task. Furthermore, an interactive and iterative framework is designed to assist the user along the analyzing task. On the one hand, we represent user domain knowledge using a Domain Ontology over database. On the other hand, a novel technique is suggested to prune and to filter discovered rules. The proposed framework was applied successfully over the client database provided by Nantes Habitat.
Hard Data on Soft Errors: A Large-Scale Assessment of Real-World Error Rates in GPGPU
Venue: arXiv cs.AR 2009
Year: 2009

Graphics processing units (GPUs) are gaining widespread use in computational chemistry and other scientific simulation contexts because of their huge performance advantages relative to conventional CPUs. However, the reliability of GPUs in error-intolerant applications is largely unproven. In particular, a lack of error checking and correcting (ECC) capability in the memory subsystems of graphics cards has been cited as a hindrance to the acceptance of GPUs as high-performance coprocessors, but the impact of this design has not been previously quantified. In this article we present MemtestG80, our software for assessing memory error rates on NVIDIA G80 and GT200-architecture-based graphics cards. Furthermore, we present the results of a large-scale assessment of GPU error rate, conducted by running MemtestG80 on over 20,000 hosts on the Folding@home distributed computing network. Our control experiments on consumer-grade and dedicated-GPGPU hardware in a controlled environment found no errors. However, our survey over cards on Folding@home finds that, in their installed environments, two-thirds of tested GPUs exhibit a detectable, pattern-sensitive rate of memory soft errors. We demonstrate that these errors persist after controlling for overclocking and environmental proxies for temperature, but depend strongly on board architecture.
Pre-processing in AI based Prediction of QSARs
Venue: arXiv cs.AI 2009
Year: 2009

Machine learning, data mining and artificial intelligence (AI) based methods have been used to determine the relations between chemical structure and biological activity, called quantitative structure activity relationships (QSARs) for the compounds. Pre-processing of the dataset, which includes the mapping from a large number of molecular descriptors in the original high dimensional space to a small number of components in the lower dimensional space while retaining the features of the original data, is the first step in this process. A common practice is to use a mapping method for a dataset without prior analysis. This pre-analysis has been stressed in our work by applying it to two important classes of QSAR prediction problems: drug design (predicting anti-HIV-1 activity) and predictive toxicology (estimating hepatocarcinogenicity of chemicals). We apply one linear and two nonlinear mapping methods on each of the datasets. Based on this analysis, we conclude the nature of the inherent relationships between the elements of each dataset, and hence, the mapping method best suited for it. We also show that proper preprocessing can help us in choosing the right feature extraction tool as well as give an insight about the type of classifier pertinent for the given problem.
Exploiting Channel Correlations - Simple Interference Alignment Schemes with no CSIT
Venue: arXiv cs.IT 2009
Year: 2009

We explore 5 network communication problems where the possibility of interference alignment, and consequently the total number of degrees of freedom (DoF) with channel uncertainty at the transmitters are unknown. These problems share the common property that in each case the best known outer bounds are essentially robust to channel uncertainty and represent the outcome with interference alignment, but the best inner bounds -- in some cases conjectured to be optimal -- predict a total collapse of DoF, thus indicating the infeasibility of interference alignment under channel uncertainty at transmitters. Our main contribution is to show that even with no knowledge of channel coefficient values at the transmitters, the knowledge of the channels' correlation structure can be exploited to achieve interference alignment. In each case, we show that under a staggered block fading model, the transmitters are able to align interference without the knowledge of channel coefficient values. The alignment schemes are based on linear beamforming -- which can be seen as a repetition code over a small number of symbols -- and involve delays of only a few coherence intervals.
Digital Business Ecosystems: Natural Science Paradigms
Venue: arXiv cs.NE 2009
Year: 2009

A primary motivation for research in Digital Ecosystems is the desire to exploit the self-organising properties of natural ecosystems. Ecosystems arc thought to be robust, scalable architectures that can automatically solve complex, dynamic problems. However, the biological processes that contribute to these properties have not been made explicit in Digital Ecosystem research. Here, we introduce how biological properties contribute to the self-organising features of natural ecosystems. These properties include populations of evolving agents, a complex dynamic environment, and spatial distributions which generate local interactions. The potential for exploiting these properties in artificial systems is then considered.
Computing of Applied Digital Ecosystems
Venue: arXiv cs.NE 2009
Year: 2009

A primary motivation for our research in digital ecosystems is the desire to exploit the self-organising properties of biological ecosystems. Ecosystems are thought to be robust, scalable architectures that can automatically solve complex, dynamic problems. However, the computing technologies that contribute to these properties have not been made explicit in digital ecosystems research. Here, we discuss how different computing technologies can contribute to providing the necessary self-organising features, including Multi-Agent Systems, Service-Oriented Architectures, and distributed evolutionary computing. The potential for exploiting these properties in digital ecosystems is considered, suggesting how several key features of biological ecosystems can be exploited in Digital Ecosystems, and discussing how mimicking these features may assist in developing robust, scalable self-organising architectures. An example architecture, the Digital Ecosystem, is considered in detail. The Digital Ecosystem is then measured experimentally through simulations, considering the self-organised diversity of its evolving agent populations relative to the user request behaviour.
Robust Failure Detection Architecture for Large Scale Distributed Systems
Venue: arXiv cs.DC 2009
Year: 2009

Failure detection is a fundamental building block for ensuring fault tolerance in large scale distributed systems. There are lots of approaches and implementations in failure detectors. Providing flexible failure detection in off-the-shelf distributed systems is difficult. In this paper we present an innovative solution to this problem. Our approach is based on adaptive, decentralized failure detectors, capable of working asynchronous and independent on the application flow. The proposed solution considers an architecture for the failure detectors, based on clustering, the use of a gossip-based algorithm for detection at local level and the use of a hierarchical structure among clusters of detectors along which traffic is channeled. The solution can scale to a large number of nodes, considers the QoS requirements of both applications and resources, and includes fault tolerance and system orchestration mechanisms, added in order to asses the reliability and availability of distributed systems.
Local negative circuits and fixed points in Boolean networks
Venue: arXiv cs.DM 2009
Year: 2009

To each Boolean function F from {0,1}^n to itself and each point x in {0,1}^n, we associate the signed directed graph G_F(x) of order n that contains a positive (resp. negative) arc from j to i if the partial derivative of f_i with respect of x_j is positive (resp. negative) at point x. We then focus on the following open problem: Is the absence of a negative circuit in G_F(x) for all x in {0,1}^n a sufficient condition for F to have at least one fixed point? As main result, we settle this problem under the additional condition that, for all x in {0,1}^n, the out-degree of each vertex of G_F(x) is at most one.
Low-rank Matrix Completion with Noisy Observations: a Quantitative Comparison
Venue: arXiv cs.LG 2009
Year: 2009

We consider a problem of significant practical importance, namely, the reconstruction of a low-rank data matrix from a small subset of its entries. This problem appears in many areas such as collaborative filtering, computer vision and wireless sensor networks. In this paper, we focus on the matrix completion problem in the case when the observed samples are corrupted by noise. We compare the performance of three state-of-the-art matrix completion algorithms (OptSpace, ADMiRA and FPCA) on a single simulation platform and present numerical results. We show that in practice these efficient algorithms can be used to reconstruct real data matrices, as well as randomly generated matrices, accurately.
LP Decoding meets LP Decoding: A Connection between Channel Coding and Compressed Sensing
Venue: arXiv cs.IT 2009
Year: 2009

This is a tale of two linear programming decoders, namely channel coding linear programming decoding (CC-LPD) and compressed sensing linear programming decoding (CS-LPD). So far, they have evolved quite independently. The aim of the present paper is to show that there is a tight connection between, on the one hand, CS-LPD based on a zero-one measurement matrix over the reals and, on the other hand, CC-LPD of the binary linear code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows one to translate performance guarantees from one setup to the other.
Sorting from Noisy Information
Venue: arXiv cs.DS 2009
Year: 2009

This paper studies problems of inferring order given noisy information. In these problems there is an unknown order (permutation) $π$ on $n$ elements denoted by $1,...,n$. We assume that information is generated in a way correlated with $π$. The goal is to find a maximum likelihood $π^*$ given the information observed. We will consider two different types of observations: noisy comparisons and noisy orders. The data in Noisy orders are permutations given from an exponential distribution correlated with π(this is also called the Mallow's model). The data in Noisy Comparisons is a signal given for each pair of elements which is correlated with their true ordering. In this paper we present polynomial time algorithms for solving both problems with high probability. As part of our proof we show that for both models the maximum likelihood solution $π^{\ast}$ is close to the original permutation $π$. Our results are of interest in applications to ranking, such as ranking in sports, or ranking of search items based on comparisons by experts.
Integrating Conflict Driven Clause Learning to Local Search
Venue: arXiv cs.AI 2009
Year: 2009

This article introduces SatHyS (SAT HYbrid Solver), a novel hybrid approach for propositional satisfiability. It combines local search and conflict driven clause learning (CDCL) scheme. Each time the local search part reaches a local minimum, the CDCL is launched. For SAT problems it behaves like a tabu list, whereas for UNSAT ones, the CDCL part tries to focus on minimum unsatisfiable sub-formula (MUS). Experimental results show good performances on many classes of SAT instances from the last SAT competitions.
Sonet Network Design Problems
Venue: arXiv cs.AI 2009
Year: 2009

This paper presents a new method and a constraint-based objective function to solve two problems related to the design of optical telecommunication networks, namely the Synchronous Optical Network Ring Assignment Problem (SRAP) and the Intra-ring Synchronous Optical Network Design Problem (IDP). These network topology problems can be represented as a graph partitioning with capacity constraints as shown in previous works. We present here a new objective function and a new local search algorithm to solve these problems. Experiments conducted in Comet allow us to compare our method to previous ones and show that we obtain better results.
Parallel local search for solving Constraint Problems on the Cell Broadband Engine (Preliminary Results)
Venue: arXiv cs.AI 2009
Year: 2009

We explore the use of the Cell Broadband Engine (Cell/BE for short) for combinatorial optimization applications: we present a parallel version of a constraint-based local search algorithm that has been implemented on a multiprocessor BladeCenter machine with twin Cell/BE processors (total of 16 SPUs per blade). This algorithm was chosen because it fits very well the Cell/BE architecture and requires neither shared memory nor communication between processors, while retaining a compact memory footprint. We study the performance on several large optimization benchmarks and show that this achieves mostly linear time speedups, even sometimes super-linear. This is possible because the parallel implementation might explore simultaneously different parts of the search space and therefore converge faster towards the best sub-space and thus towards a solution. Besides getting speedups, the resulting times exhibit a much smaller variance, which benefits applications where a timely reply is critical.
Prefetching of VoD Programs Based On ART1 Requesting Clustering
Venue: arXiv cs.MM 2009
Year: 2009

In this paper, we propose a novel approach to group users according to the VoD user request pattern. We cluster the user requests based on ART1 neural network algorithm. The knowledge extracted from the cluster is used to prefetch the multimedia object from each cluster before the users request. We have developed an algorithm to cluster users according to the users request patterns based on ART1 neural network algorithm that offers an unsupervised clustering. This approach adapts to changes in user request patterns over period without losing previous information. Each cluster is represented as prototype vector by generalizing the most frequently used URLs that are accessed by all the cluster members. The simulation results of our proposed clustering and prefetching algorithm, shows enormous increase in the performance of streaming server. Our algorithm helps the servers agent to learn user preferences and discover the information about the corresponding sources and other similar interested individuals.
Some Thoughts on Hypercomputation
Venue: arXiv cs.OH 2009
Year: 2009

Hypercomputation is a relatively new branch of computer science that emerged from the idea that the Church--Turing Thesis, which is supposed to describe what is computable and what is noncomputable, cannot possible be true. Because of its apparent validity, the Church--Turing Thesis has been used to investigate the possible limits of intelligence of any imaginable life form, and, consequently, the limits of information processing, since living beings are, among others, information processors. However, in the light of hypercomputation, which seems to be feasibly in our universe, one cannot impose arbitrary limits to what intelligence can achieve unless there are specific physical laws that prohibit the realization of something. In addition, hypercomputation allows us to ponder about aspects of communication between intelligent beings that have not been considered before