OpenRaiser/Intern-Atlas huggingface dataset:
Verified Null-Move Pruning
Venue: arXiv cs.AI 2008
Year: 2008

In this article we review standard null-move pruning and introduce our extended version of it, which we call verified null-move pruning. In verified null-move pruning, whenever the shallow null-move search indicates a fail-high, instead of cutting off the search from the current node, the search is continued with reduced depth. Our experiments with verified null-move pruning show that on average, it constructs a smaller search tree with greater tactical strength in comparison to standard null-move pruning. Moreover, unlike standard null-move pruning, which fails badly in zugzwang positions, verified null-move pruning manages to detect most zugzwangs and in such cases conducts a re-search to obtain the correct result. In addition, verified null-move pruning is very easy to implement, and any standard null-move pruning program can use verified null-move pruning by modifying only a few lines of code.
On some deterministic dictionaries supporting sparsity
Venue: arXiv cs.IT 2008
Year: 2008

We describe a new construction of an incoherent dictionary, referred to as the oscillator dictionary, which is based on considerations in the representation theory of finite groups. The oscillator dictionary consists of order of p^5 unit vectors in a Hilbert space of dimension p, where p is an odd prime, whose pairwise inner products have magnitude of at most 4/sqrt(p). An explicit algorithm to construct a large portion of the oscillator dictionary is presented.
Comparison between CPBPV, ESC/Java, CBMC, Blast, EUREKA and Why for Bounded Program Verification
Venue: arXiv cs.SE 2008
Year: 2008

This report describes experimental results for a set of benchmarks on program verification. It compares the capabilities of CPBVP "Constraint Programming framework for Bounded Program Verification" [4] with the following frameworks: ESC/Java, CBMC, Blast, EUREKA and Why.
Medical robotics: where we come from, where we are and where we could go
Venue: arXiv cs.RO 2008
Year: 2008

This short note presents a viewpoint about medical robotics.
Compute and Storage Clouds Using Wide Area High Performance Networks
Venue: arXiv cs.DC 2008
Year: 2008

We describe a cloud based infrastructure that we have developed that is optimized for wide area, high performance networks and designed to support data mining applications. The infrastructure consists of a storage cloud called Sector and a compute cloud called Sphere. We describe two applications that we have built using the cloud and some experimental studies.
Decision Problems For Convex Languages
Venue: arXiv cs.CC 2008
Year: 2008

In this paper we examine decision problems associated with various classes of convex languages, studied by Ang and Brzozowski (under the name "continuous languages"). We show that we can decide whether a given language L is prefix-, suffix-, factor-, or subword-convex in polynomial time if L is represented by a DFA, but that the problem is PSPACE-hard if L is represented by an NFA. In the case that a regular language is not convex, we prove tight upper bounds on the length of the shortest words demonstrating this fact, in terms of the number of states of an accepting DFA. Similar results are proved for some subclasses of convex languages: the prefix-, suffix-, factor-, and subword-closed languages, and the prefix-, suffix-, factor-, and subword-free languages.
Diversity-Multiplexing Tradeoffs in MIMO Relay Channels
Venue: arXiv cs.IT 2008
Year: 2008

A multi-hop relay channel with multiple antenna terminals in a quasi-static slow fading environment is considered. For both full-duplex and half-duplex relays the fundamental diversity-multiplexing tradeoff (DMT) is analyzed. It is shown that, while decode-and-forward (DF) relaying achieves the optimal DMT in the full-duplex relay scenario, the dynamic decode-and-forward (DDF) protocol is needed to achieve the optimal DMT if the relay is constrained to half-duplex operation. For the latter case, static protocols are considered as well, and the corresponding achievable DMT performance is characterized.
Concurrent Imitation Dynamics in Congestion Games
Venue: arXiv cs.GT 2008
Year: 2008

Imitating successful behavior is a natural and frequently applied approach to trust in when facing scenarios for which we have little or no experience upon which we can base our decision. In this paper, we consider such behavior in atomic congestion games. We propose to study concurrent imitation dynamics that emerge when each player samples another player and possibly imitates this agents' strategy if the anticipated latency gain is sufficiently large. Our main focus is on convergence properties. Using a potential function argument, we show that our dynamics converge in a monotonic fashion to stable states. In such a state none of the players can improve its latency by imitating somebody else. As our main result, we show rapid convergence to approximate equilibria. At an approximate equilibrium only a small fraction of agents sustains a latency significantly above or below average. In particular, imitation dynamics behave like fully polynomial time approximation schemes (FPTAS). Fixing all other parameters, the convergence time depends only in a logarithmic fashion on the number of agents. Since imitation processes are not innovative they cannot discover unused strategies. Furthermore, strategies may become extinct with non-zero probability. For the case of singleton games, we show that the probability of this event occurring is negligible. Additionally, we prove that the social cost of a stable state reached by our dynamics is not much worse than an optimal state in singleton congestion games with linear latency function. Finally, we discuss how the protocol can be extended such that, in the long run, dynamics converge to a Nash equilibrium.
Higher Order Moments Generation by Mellin Transform for Compound Models of Clutter
Venue: arXiv cs.CV 2008
Year: 2008

The compound models of clutter statistics are found suitable to describe the nonstationary nature of radar backscattering from high-resolution observations. In this letter, we show that the properties of Mellin transform can be utilized to generate higher order moments of simple and compound models of clutter statistics in a compact manner.
Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games
Venue: arXiv cs.GT 2008
Year: 2008

We show that there is a polynomial-time approximation scheme for computing Nash equilibria in anonymous games with any fixed number of strategies (a very broad and important class of games), extending the two-strategy result of Daskalakis and Papadimitriou 2007. The approximation guarantee follows from a probabilistic result of more general interest: The distribution of the sum of n independent unit vectors with values ranging over {e1, e2, ...,ek}, where ei is the unit vector along dimension i of the k-dimensional Euclidean space, can be approximated by the distribution of the sum of another set of independent unit vectors whose probabilities of obtaining each value are multiples of 1/z for some integer z, and so that the variational distance of the two distributions is at most eps, where eps is bounded by an inverse polynomial in z and a function of k, but with no dependence on n. Our probabilistic result specifies the construction of a surprisingly sparse eps-cover -- under the total variation distance -- of the set of distributions of sums of independent unit vectors, which is of interest on its own right.
Estimating the Lengths of Memory Words
Venue: arXiv cs.IT 2008
Year: 2008

For a stationary stochastic process $\{X_n\}$ with values in some set $A$, a finite word $w \in A^K$ is called a memory word if the conditional probability of $X_0$ given the past is constant on the cylinder set defined by $X_{-K}^{-1}=w$. It is a called a minimal memory word if no proper suffix of $w$ is also a memory word. For example in a $K$-step Markov processes all words of length $K$ are memory words but not necessarily minimal. We consider the problem of determining the lengths of the longest minimal memory words and the shortest memory words of an unknown process $\{X_n\}$ based on sequentially observing the outputs of a single sample $\{ξ_1,ξ_2,...ξ_n\}$. We will give a universal estimator which converges almost surely to the length of the longest minimal memory word and show that no such universal estimator exists for the length of the shortest memory word. The alphabet $A$ may be finite or countable.
Data Mining Using High Performance Data Clouds: Experimental Studies Using Sector and Sphere
Venue: arXiv cs.DC 2008
Year: 2008

We describe the design and implementation of a high performance cloud that we have used to archive, analyze and mine large distributed data sets. By a cloud, we mean an infrastructure that provides resources and/or services over the Internet. A storage cloud provides storage services, while a compute cloud provides compute services. We describe the design of the Sector storage cloud and how it provides the storage services required by the Sphere compute cloud. We also describe the programming paradigm supported by the Sphere compute cloud. Sector and Sphere are designed for analyzing large data sets using computer clusters connected with wide area high performance networks (for example, 10+ Gb/s). We describe a distributed data mining application that we have developed using Sector and Sphere. Finally, we describe some experimental studies comparing Sector/Sphere to Hadoop.
Privacy Preserving Association Rule Mining Revisited
Venue: arXiv cs.CR 2008
Year: 2008

The privacy preserving data mining (PPDM) has been one of the most interesting, yet challenging, research issues. In the PPDM, we seek to outsource our data for data mining tasks to a third party while maintaining its privacy. In this paper, we revise one of the recent PPDM schemes (i.e., FS) which is designed for privacy preserving association rule mining (PP-ARM). Our analysis shows some limitations of the FS scheme in term of its storage requirements guaranteeing a reasonable privacy standard and the high computation as well. On the other hand, we introduce a robust definition of privacy that considers the average case privacy and motivates the study of a weakness in the structure of FS (i.e., fake transactions filtering). In order to overcome this limit, we introduce a hybrid scheme that considers both privacy and resources guidelines. Experimental results show the efficiency of our proposed scheme over the previously introduced one and opens directions for further development.
Jamming in Fixed-Rate Wireless Systems with Power Constraints - Part II: Parallel Slow Fading Channels
Venue: arXiv cs.IT 2008
Year: 2008

This is the second part of a two-part paper that studies the problem of jamming in a fixed-rate transmission system with fading. In the first part, we studied the scenario with a fast fading channel, and found Nash equilibria of mixed strategies for short term power constraints, and for average power constraints with and without channel state information (CSI) feedback. We also solved the equally important maximin and minimax problems with pure strategies. Whenever we dealt with average power constraints, we decomposed the problem into two levels of power control, which we solved individually. In this second part of the paper, we study the scenario with a parallel, slow fading channel, which usually models multi-carrier transmissions, such as OFDM. Although the framework is similar as the one in Part I \cite{myself3}, dealing with the slow fading requires more intricate techniques. Unlike in the fast fading scenario, where the frames supporting the transmission of the codewords were equivalent and completely characterized by the channel statistics, in our present scenario the frames are unique, and characterized by a specific set of channel realizations. This leads to more involved inter-frame power allocation strategies, and in some cases even to the need for a third level of power control. We also show that for parallel slow fading channels, the CSI feedback helps in the battle against jamming, as evidenced by the significant degradation to system performance when CSI is not sent back. We expect this degradation to decrease as the number of parallel channels $M$ increases, until it becomes marginal for $M\to \infty$ (which can be considered as the case in Part I).
Adaptive Dynamic Congestion Avoidance with Master Equation
Venue: arXiv cs.NI 2008
Year: 2008

This paper proposes an adaptive variant of Random Early Detection (RED) gateway queue management for packet-switched networks via a discrete state analog of the non-stationary Master Equation i.e. Markov process. The computation of average queue size, which appeared in the original RED algorithm, is altered by introducing a probability $P(l,t)$, which defines the probability of having $l$ number of packets in the queue at the given time $t$, and depends upon the previous state of the queue. This brings the advantage of eliminating a free parameter: queue weight, completely. Computation of transition rates and probabilities are carried out on the fly, and determined by the algorithm automatically. Simulations with unstructured packets illustrate the method, the performance of the adaptive variant of RED algorithm, and the comparison with the standard RED.
Flow-level Characteristics of Spam and Ham
Venue: arXiv cs.NI 2008
Year: 2008

Despite a large amount of effort devoted in the past years trying to limit unsolicited mail, spam is still a major global concern. Content-analysis techniques and blacklists, the most popular methods used to identify and block spam, are beginning to lose their edge in the battle. We argue here that one not only needs to look into the network-related characteristics of spam traffic, as has been recently suggested, but also to look deeper into the network core, in order to counter the increasing sophistication of spam-ing methods. Yet, at the same time, local knowledge available at a given server can often be irreplaceable in identifying specific spammers. To this end, in this paper we show how the local intelligence of mail servers can be gathered and correlated pas- sively at the ISP-level providing valuable network-wide information. Specifically, we use first a large network flow trace from a medium size, national ISP, to demonstrate that the pre-filtering decisions of individual mail servers can be tracked and combined at the flow level. Then, we argue that such aggregated knowledge not only can allow ISPs to develop and evaluate powerful new methods for fighting spam, but also to monitor remotely what their own servers are doing.
Simultaneous Modular Reduction and Kronecker Substitution for Small Finite Fields
Venue: arXiv cs.SC 2008
Year: 2008

We present algorithms to perform modular polynomial multiplication or modular dot product efficiently in a single machine word. We pack polynomials into integers and perform several modular operations with machine integer or floating point arithmetic. The modular polynomials are converted into integers using Kronecker substitution (evaluation at a sufficiently large integer). With some control on the sizes and degrees, arithmetic operations on the polynomials can be performed directly with machine integers or floating point numbers and the number of conversions can be reduced. We also present efficient ways to recover the modular values of the coefficients. This leads to practical gains of quite large constant factors for polynomial multiplication, prime field linear algebra and small extension field arithmetic.
Randomised Variable Neighbourhood Search for Multi Objective Optimisation
Venue: arXiv cs.AI 2008
Year: 2008

Various local search approaches have recently been applied to machine scheduling problems under multiple objectives. Their foremost consideration is the identification of the set of Pareto optimal alternatives. An important aspect of successfully solving these problems lies in the definition of an appropriate neighbourhood structure. Unclear in this context remains, how interdependencies within the fitness landscape affect the resolution of the problem. The paper presents a study of neighbourhood search operators for multiple objective flow shop scheduling. Experiments have been carried out with twelve different combinations of criteria. To derive exact conclusions, small problem instances, for which the optimal solutions are known, have been chosen. Statistical tests show that no single neighbourhood operator is able to equally identify all Pareto optimal alternatives. Significant improvements however have been obtained by hybridising the solution algorithm using a randomised variable neighbourhood search technique.
Simulations between triangular and hexagonal number-conserving cellular automata
Venue: arXiv cs.DM 2008
Year: 2008

A number-conserving cellular automaton is a cellular automaton whose states are integers and whose transition function keeps the sum of all cells constant throughout its evolution. It can be seen as a kind of modelization of the physical conservation laws of mass or energy. In this paper, we first propose a necessary condition for triangular and hexagonal cellular automata to be number-conserving. The local transition function is expressed by the sum of arity two functions which can be regarded as 'flows' of numbers. The sufficiency is obtained through general results on number-conserving cellular automata. Then, using the previous flow functions, we can construct effective number-conserving simulations between hexagonal cellular automata and triangular cellular automata.
The stable configuration in acyclic preference-based systems
Venue: arXiv cs.NI 2008
Year: 2008

Acyclic preferences recently appeared as an elegant way to model many distributed systems. An acyclic instance admits a unique stable configuration, which can reveal the performance of the system. In this paper, we give the statistical properties of the stable configuration for three classes of acyclic preferences: node-based preferences, distance-based preferences, and random acyclic systems. Using random overlay graphs, we prove using mean-field and fluid-limit techniques that these systems have an asymptotically continuous independent rank distribution for a proper scaling, and the analytical solution is compared to simulations. These results provide a theoretical ground for validating the performance of bandwidth-based or proximity-based unstructured systems.
Variable Neighborhood Search for the University Lecturer-Student Assignment Problem
Venue: arXiv cs.AI 2008
Year: 2008

The paper presents a study of local search heuristics in general and variable neighborhood search in particular for the resolution of an assignment problem studied in the practical work of universities. Here, students have to be assigned to scientific topics which are proposed and supported by members of staff. The problem involves the optimization under given preferences of students which may be expressed when applying for certain topics. It is possible to observe that variable neighborhood search leads to superior results for the tested problem instances. One instance is taken from an actual case, while others have been generated based on the real world data to support the analysis with a deeper analysis. An extension of the problem has been formulated by integrating a second objective function that simultaneously balances the workload of the members of staff while maximizing utility of the students. The algorithmic approach has been prototypically implemented in a computer system. One important aspect in this context is the application of the research work to problems of other scientific institutions, and therefore the provision of decision support functionalities.
Maximum Entropy Rate of Markov Sources for Systems With Non-regular Constraints
Venue: arXiv cs.IT 2008
Year: 2008

Using the concept of discrete noiseless channels, it was shown by Shannon in A Mathematical Theory of Communication that the ultimate performance of an encoder for a constrained system is limited by the combinatorial capacity of the system if the constraints define a regular language. In the present work, it is shown that this is not an inherent property of regularity but holds in general. To show this, constrained systems are described by generating functions and random walks on trees.
Low-Complexity Coding and Source-Optimized Clustering for Large-Scale Sensor Networks
Venue: arXiv cs.IT 2008
Year: 2008

We consider the distributed source coding problem in which correlated data picked up by scattered sensors has to be encoded separately and transmitted to a common receiver, subject to a rate-distortion constraint. Although near-tooptimal solutions based on Turbo and LDPC codes exist for this problem, in most cases the proposed techniques do not scale to networks of hundreds of sensors. We present a scalable solution based on the following key elements: (a) distortion-optimized index assignments for low-complexity distributed quantization, (b) source-optimized hierarchical clustering based on the Kullback-Leibler distance and (c) sum-product decoding on specific factor graphs exploiting the correlation of the data.
ECOLANG - Communications Language for Ecological Simulations Network
Venue: arXiv cs.AI 2008
Year: 2008

This document describes the communication language used in one multiagent system environment for ecological simulations, based on EcoDynamo simulator application linked with several intelligent agents and visualisation applications, and extends the initial definition of the language. The agents actions and perceptions are translated into messages exchanged with the simulator application and other agents. The concepts and definitions used follow the BNF notation (Backus et al. 1960) and is inspired in the Coach Unilang language (Reis and Lau 2002).
Multirate Anypath Routing in Wireless Mesh Networks
Venue: arXiv cs.NI 2008
Year: 2008

In this paper, we present a new routing paradigm that generalizes opportunistic routing in wireless mesh networks. In multirate anypath routing, each node uses both a set of next hops and a selected transmission rate to reach a destination. Using this rate, a packet is broadcast to the nodes in the set and one of them forwards the packet on to the destination. To date, there is no theory capable of jointly optimizing both the set of next hops and the transmission rate used by each node. We bridge this gap by introducing a polynomial-time algorithm to this problem and provide the proof of its optimality. The proposed algorithm runs in the same running time as regular shortest-path algorithms and is therefore suitable for deployment in link-state routing protocols. We conducted experiments in a 802.11b testbed network, and our results show that multirate anypath routing performs on average 80% and up to 6.4 times better than anypath routing with a fixed rate of 11 Mbps. If the rate is fixed at 1 Mbps instead, performance improves by up to one order of magnitude.