OpenRaiser/Intern-Atlas huggingface dataset:
xPerm: fast index canonicalization for tensor computer algebra
Venue: arXiv cs.SC 2008
Year: 2008

We present a very fast implementation of the Butler-Portugal algorithm for index canonicalization with respect to permutation symmetries. It is called xPerm, and has been written as a combination of a Mathematica package and a C subroutine. The latter performs the most demanding parts of the computations and can be linked from any other program or computer algebra system. We demonstrate with tests and timings the effectively polynomial performance of the Butler-Portugal algorithm with respect to the number of indices, though we also show a case in which it is exponential. Our implementation handles generic tensorial expressions with several dozen indices in hundredths of a second, or one hundred indices in a few seconds, clearly outperforming all other current canonicalizers. The code has been already under intensive testing for several years and has been essential in recent investigations in large-scale tensor computer algebra.
Characterizing path graphs by forbidden induced subgraphs
Venue: arXiv cs.DM 2008
Year: 2008

A graph is a path graph if it is the intersection graph of a family of subpaths of a tree. In 1970, Renz asked for a characterizaton of path graphs by forbidden induced subgraphs. Here we answer this question by listing all graphs that are not path graphs and are minimal with this property.
Secure Lossless Compression with Side Information
Venue: arXiv cs.IT 2008
Year: 2008

Secure data compression in the presence of side information at both a legitimate receiver and an eavesdropper is explored. A noise-free, limited rate link between the source and the receiver, whose output can be perfectly observed by the eavesdropper, is assumed. As opposed to the wiretap channel model, in which secure communication can be established by exploiting the noise in the channel, here the existence of side information at the receiver is used. Both coded and uncoded side information are considered. In the coded side information scenario, inner and outer bounds on the compression-equivocation rate region are given. In the uncoded side information scenario, the availability of the legitimate receiver's and the eavesdropper's side information at the encoder is considered, and the compression-equivocation rate region is characterized for these cases. It is shown that the side information at the encoder can increase the equivocation rate at the eavesdropper. Hence, the side information at the encoder is shown to be useful in terms of security; this is in contrast with the pure lossless data compression case where side information at the encoder would not help.
Hsiao-Code Check Matrices and Recursively Balanced Matrices
Venue: arXiv cs.DM 2008
Year: 2008

The key step of generating the well-known Hsiao code is to construct a {0,1}-check-matrix in which each column contains the same odd-number of 1's and each row contains the same number of 1's or differs at most by one for the number of 1's. We also require that no two columns are identical in the matrix. The author solved this problem in 1986 by introducing a type of recursively balanced matrices. However, since the paper was published in Chinese, the solution for such an important problem was not known by international researchers in coding theory. In this note, we focus on how to practically generate the check matrix of Hsiao codes. We have modified the original algorithm to be more efficient and effective. We have also corrected an error in algorithm analysis presented in the earlier paper. The result shows that the algorithm attained optimum in average cases if a divide-and-conquer technique must be involved in the algorithm.
Linear programming bounds for unitary space time codes
Venue: arXiv cs.IT 2008
Year: 2008

The linear programming method is applied to the space $\U_n(\C)$ of unitary matrices in order to obtain bounds for codes relative to the diversity sum and the diversity product. Theoretical and numerical results improving previously known bounds are derived.
Proactive Service Migration for Long-Running Byzantine Fault Tolerant Systems
Venue: arXiv cs.DC 2008
Year: 2008

In this paper, we describe a novel proactive recovery scheme based on service migration for long-running Byzantine fault tolerant systems. Proactive recovery is an essential method for ensuring long term reliability of fault tolerant systems that are under continuous threats from malicious adversaries. The primary benefit of our proactive recovery scheme is a reduced vulnerability window. This is achieved by removing the time-consuming reboot step from the critical path of proactive recovery. Our migration-based proactive recovery is coordinated among the replicas, therefore, it can automatically adjust to different system loads and avoid the problem of excessive concurrent proactive recoveries that may occur in previous work with fixed watchdog timeouts. Moreover, the fast proactive recovery also significantly improves the system availability in the presence of faults.
Minimum-Delay Decoding of Turbo-Codes for Upper-Layer FEC
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we investigate the decoding of parallel turbo codes over the binary erasure channel suited for upper-layer error correction. The proposed algorithm performs on-the-fly decoding, i.e. it starts decoding as soon as the first symbols are received. This algorithm compares with the iterative decoding of codes defined on graphs, in that it propagates in the trellises of the turbo code by removing transitions in the same way edges are removed in a bipartite graph under message-passing decoding. Performance comparison with LDPC codes for different coding rates is shown.
On the Topological Complexity of Infinitary Rational Relations
Venue: arXiv cs.LO 2008
Year: 2008

We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [Automates et Théorie Descriptive, Ph. D. Thesis, Université Paris 7, March 1992].
Comparison of the Discriminatory Processor Sharing Policies
Venue: arXiv cs.NI 2008
Year: 2008

Discriminatory Processor Sharing policy introduced by Kleinrock is of a great interest in many application areas, including telecommunications, web applications and TCP flow modelling. Under the DPS policy the job priority is controlled by the vector of weights. Verifying the vector of weights it is possible to modify the service rates of the jobs and optimize system characteristics. In the present paper we present the results concerning the comparison of two DPS policies with different weight vectors. We show the monotonicity of the expected sojourn time of the system depending on the weight vector under certain condition on the system. Namely, the system has to consist of classes with means which are quite different from each other. The classes with similar means can be organized together and considered as one class, so the given restriction can be overcame.
A Practical Attack on the MIFARE Classic
Venue: arXiv cs.CR 2008
Year: 2008

The MIFARE Classic is the most widely used contactless smart card in the market. Its design and implementation details are kept secret by its manufacturer. This paper studies the architecture of the card and the communication protocol between card and reader. Then it gives a practical, low-cost, attack that recovers secret information from the memory of the card. Due to a weakness in the pseudo-random generator, we are able to recover the keystream generated by the CRYPTO1 stream cipher. We exploit the malleability of the stream cipher to read all memory blocks of the first sector of the card. Moreover, we are able to read any sector of the memory of the card, provided that we know one memory block within this sector. Finally, and perhaps more damaging, the same holds for modifying memory blocks.
SAFIUS - A secure and accountable filesystem over untrusted storage
Venue: arXiv cs.OS 2008
Year: 2008

We describe SAFIUS, a secure accountable file system that resides over an untrusted storage. SAFIUS provides strong security guarantees like confidentiality, integrity, prevention from rollback attacks, and accountability. SAFIUS also enables read/write sharing of data and provides the standard UNIX-like interface for applications. To achieve accountability with good performance, it uses asynchronous signatures; to reduce the space required for storing these signatures, a novel signature pruning mechanism is used. SAFIUS has been implemented on a GNU/Linux based system modifying OpenGFS. Preliminary performance studies show that SAFIUS has a tolerable overhead for providing secure storage: while it has an overhead of about 50% of OpenGFS in data intensive workloads (due to the overhead of performing encryption/decryption in software), it is comparable (or better in some cases) to OpenGFS in metadata intensive workloads.
Controlling the Information Flow in Spreadsheets
Venue: arXiv cs.HC 2008
Year: 2008

There is no denying that spreadsheets have become critical for all operational processes including financial reporting, budgeting, forecasting, and analysis. Microsoft Excel has essentially become a scratch pad and a data browser that can quickly be put to use for information gathering and decision-making. However, there is little control in how data comes into Excel, and how it gets updated. The information supply chain feeding into Excel remains ad hoc and without any centralized IT control. This paper discusses some of the pitfalls of the data collection and maintenance process in Excel. It then suggests service-oriented architecture (SOA) based information gathering and control techniques to ameliorate the pitfalls of this scratch pad while improving the integrity of data, boosting the productivity of the business users, and building controls to satisfy the requirements of Section 404 of the Sarbanes-Oxley Act.
Enhanced Direct and Indirect Genetic Algorithm Approaches for a Mall Layout and Tenant Selection Problem
Venue: arXiv cs.NE 2008
Year: 2008

During our earlier research, it was recognised that in order to be successful with an indirect genetic algorithm approach using a decoder, the decoder has to strike a balance between being an optimiser in its own right and finding feasible solutions. Previously this balance was achieved manually. Here we extend this by presenting an automated approach where the genetic algorithm itself, simultaneously to solving the problem, sets weights to balance the components out. Subsequently we were able to solve a complex and non-linear scheduling problem better than with a standard direct genetic algorithm implementation.
An Estimation of Distribution Algorithm for Nurse Scheduling
Venue: arXiv cs.NE 2008
Year: 2008

Schedules can be built in a similar way to a human scheduler by using a set of rules that involve domain knowledge. This paper presents an Estimation of Distribution Algorithm (eda) for the nurse scheduling problem, which involves choosing a suitable scheduling rule from a set for the assignment of each nurse. Unlike previous work that used Genetic Algorithms (ga) to implement implicit learning, the learning in the proposed algorithm is explicit, i.e. we identify and mix building blocks directly. The eda is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated by using the corresponding conditional probabilities, until all variables have been generated, i.e. in our case, a new rule string has been obtained. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed approach might be suitable for other scheduling problems.
Twenty-Five Moves Suffice for Rubik's Cube
Venue: arXiv cs.SC 2008
Year: 2008

How many moves does it take to solve Rubik's Cube? Positions are known that require 20 moves, and it has already been shown that there are no positions that require 27 or more moves; this is a surprisingly large gap. This paper describes a program that is able to find solutions of length 20 or less at a rate of more than 16 million positions a second. We use this program, along with some new ideas and incremental improvements in other techniques, to show that there is no position that requires 26 moves.
Diversity of Online Community Activities
Venue: arXiv cs.CY 2008
Year: 2008

Web sites where users create and rate content as well as form networks with other users display long-tailed distributions in many aspects of behavior. Using behavior on one such community site, Essembly, we propose and evaluate plausible mechanisms to explain these behaviors. Unlike purely descriptive models, these mechanisms rely on user behaviors based on information available locally to each user. For Essembly, we find the long-tails arise from large differences among user activity rates and qualities of the rated content, as well as the extensive variability in the time users devote to the site. We show that the models not only explain overall behavior but also allow estimating the quality of content from their early behaviors.
Multiagent Approach for the Representation of Information in a Decision Support System
Venue: arXiv cs.AI 2008
Year: 2008

In an emergency situation, the actors need an assistance allowing them to react swiftly and efficiently. In this prospect, we present in this paper a decision support system that aims to prepare actors in a crisis situation thanks to a decision-making support. The global architecture of this system is presented in the first part. Then we focus on a part of this system which is designed to represent the information of the current situation. This part is composed of a multiagent system that is made of factual agents. Each agent carries a semantic feature and aims to represent a partial part of a situation. The agents develop thanks to their interactions by comparing their semantic features using proximity measures and according to specific ontologies.
A New Upper Bound for Max-2-Sat: A Graph-Theoretic Approach
Venue: arXiv cs.DS 2008
Year: 2008

In {\sc MaxSat}, we ask for an assignment which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of $O^*(2^{\frac{1}{6.2158}})$ for {\sc Max-2-Sat} (each clause contains at most 2 literals), where $K$ is the number of clauses. The run time has been achieved by using heuristic priorities on the choice of the variable on which we branch. The implementation of these heuristic priorities is rather simple, though they have a significant effect on the run time. The analysis is done using a tailored non-standard measure.
Reinforcement Learning by Value Gradients
Venue: arXiv cs.NE 2008
Year: 2008

The concept of the value-gradient is introduced and developed in the context of reinforcement learning. It is shown that by learning the value-gradients exploration or stochastic behaviour is no longer needed to find locally optimal trajectories. This is the main motivation for using value-gradients, and it is argued that learning value-gradients is the actual objective of any value-function learning algorithm for control problems. It is also argued that learning value-gradients is significantly more efficient than learning just the values, and this argument is supported in experiments by efficiency gains of several orders of magnitude, in several problem domains. Once value-gradients are introduced into learning, several analyses become possible. For example, a surprising equivalence between a value-gradient learning algorithm and a policy-gradient learning algorithm is proven, and this provides a robust convergence proof for control problems using a value function with a general function approximator.
New Families of Triple Error Correcting Codes with BCH Parameters
Venue: arXiv cs.IT 2008
Year: 2008

Discovered by Bose, Chaudhuri and Hocquenghem, the BCH family of error correcting codes are one of the most studied families in coding theory. They are also among the best performing codes, particularly when the number of errors being corrected is small relative to the code length. In this article we consider binary codes with minimum distance of 7. We construct new families of codes with these BCH parameters via a generalisation of the Kasami-Welch Theorem.
Improved Lower Bounds for Constant GC-Content DNA Codes
Venue: arXiv cs.IT 2008
Year: 2008

The design of large libraries of oligonucleotides having constant GC-content and satisfying Hamming distance constraints between oligonucleotides and their Watson-Crick complements is important in reducing hybridization errors in DNA computing, DNA microarray technologies, and molecular bar coding. Various techniques have been studied for the construction of such oligonucleotide libraries, ranging from algorithmic constructions via stochastic local search to theoretical constructions via coding theory. We introduce a new stochastic local search method which yields improvements up to more than one third of the benchmark lower bounds of Gaborit and King (2005) for n-mer oligonucleotide libraries when n <= 14. We also found several optimal libraries by computing maximum cliques on certain graphs.
Network protocol scalability via a topological Kadanoff transformation
Venue: arXiv cs.NI 2008
Year: 2008

A natural hierarchical framework for network topology abstraction is presented based on an analogy with the Kadanoff transformation and renormalisation group in theoretical physics. Some properties of the renormalisation group bear similarities to the scalability properties of network routing protocols (interactions). Central to our abstraction are two intimately connected and complementary path diversity units: simple cycles, and cycle adjacencies. A recursive network abstraction procedure is presented, together with an associated generic recursive routing protocol family that offers many desirable features.
Cluster Approach to the Domains Formation
Venue: arXiv cs.NE 2008
Year: 2008

As a rule, a quadratic functional depending on a great number of binary variables has a lot of local minima. One of approaches allowing one to find in averaged deeper local minima is aggregation of binary variables into larger blocks/domains. To minimize the functional one has to change the states of aggregated variables (domains). In the present publication we discuss methods of domains formation. It is shown that the best results are obtained when domains are formed by variables that are strongly connected with each other.
Human dynamics revealed through Web analytics
Venue: arXiv cs.HC 2008
Year: 2008

When the World Wide Web was first conceived as a way to facilitate the sharing of scientific information at the CERN (European Center for Nuclear Research) few could have imagined the role it would come to play in the following decades. Since then, the increasing ubiquity of Internet access and the frequency with which people interact with it raise the possibility of using the Web to better observe, understand, and monitor several aspects of human social behavior. Web sites with large numbers of frequently returning users are ideal for this task. If these sites belong to companies or universities, their usage patterns can furnish information about the working habits of entire populations. In this work, we analyze the properly anonymized logs detailing the access history to Emory University's Web site. Emory is a medium size university located in Atlanta, Georgia. We find interesting structure in the activity patterns of the domain and study in a systematic way the main forces behind the dynamics of the traffic. In particular, we show that both linear preferential linking and priority based queuing are essential ingredients to understand the way users navigate the Web.
Learning Sequences
Venue: arXiv cs.DM 2008
Year: 2008

We describe the algorithms used by the ALEKS computer learning system for manipulating combinatorial descriptions of human learners' states of knowledge, generating all states that are possible according to a description of a learning space in terms of a partial order, and using Bayesian statistics to determine the most likely state of a student. As we describe, a representation of a knowledge space using learning sequences (basic words of an antimatroid) allows more general learning spaces to be implemented with similar algorithmic complexity. We show how to define a learning space from a set of learning sequences, find a set of learning sequences that concisely represents a given learning space, generate all states of a learning space represented in this way, and integrate this state generation procedure into a knowledge assessment algorithm. We also describe some related theoretical results concerning projections of learning spaces, decomposition and dimension of learning spaces, and algebraic representation of learning spaces.
Neutral Fitness Landscape in the Cellular Automata Majority Problem
Venue: arXiv cs.NE 2008
Year: 2008

We study in detail the fitness landscape of a difficult cellular automata computational task: the majority problem. Our results show why this problem landscape is so hard to search, and we quantify the large degree of neutrality found in various ways. We show that a particular subspace of the solution space, called the "Olympus", is where good solutions concentrate, and give measures to quantitatively characterize this subspace.
From Cells to Islands: An unified Model of Cellular Parallel Genetic Algorithms
Venue: arXiv cs.NE 2008
Year: 2008

This paper presents the Anisotropic selection scheme for cellular Genetic Algorithms (cGA). This new scheme allows to enhance diversity and to control the selective pressure which are two important issues in Genetic Algorithms, especially when trying to solve difficult optimization problems. Varying the anisotropic degree of selection allows swapping from a cellular to an island model of parallel genetic algorithm. Measures of performances and diversity have been performed on one well-known problem: the Quadratic Assignment Problem which is known to be difficult to optimize. Experiences show that, tuning the anisotropic degree, we can find the accurate trade-off between cGA and island models to optimize performances of parallel evolutionary algorithms. This trade-off can be interpreted as the suitable degree of migration among subpopulations in a parallel Genetic Algorithm.
How good is the Warnsdorff's knight's tour heuristic?
Venue: arXiv cs.DM 2008
Year: 2008

Warnsdorffs rule for a knights tour is a heuristic, i.e., it is a rule that does not produce the desired result all the time. It is a classic example of a greedy method in that it is based on a series of locally optimal choices. This note describes an analysis that determines how good the heuristic is on an 8 X 8 chessboard. The order of appearance in a permutation of the eight possible moves a knight can make determines the path the knight takes. A computer analysis is done of the 8! permutations of the order of a knights moves in Warnsdorffs rule on an 8 X 8 chessboard for tours starting on each of the 64 squares. Whenever a tie occurs for moves to vertices that have the lowest degree, the first of these vertices encountered in the programming loop is chosen. The number of permutations of the 8! total that yield non-Hamiltonian paths is tallied. This will be the same value if we consistently choose the last of these vertices encountered.