OpenRaiser/Intern-Atlas huggingface dataset:
Single-solution Random 3-SAT Instances
Venue: arXiv cs.AI 2005
Year: 2005

We study a class of random 3-SAT instances having exactly one solution. The properties of this ensemble considerably differ from those of a random 3-SAT ensemble. It is numerically shown that the running time of several complete and stochastic local search algorithms monotonically increases as the clause density is decreased. Therefore, there is no easy-hard-easy pattern of hardness as for standard random 3-SAT ensemble. Furthermore, the running time for short single-solution formulas increases with the problem size much faster than for random 3-SAT formulas from the phase transition region.
Modelling investment in artificial stock markets: Analytical and Numerical Results
Venue: arXiv cs.CE 2005
Year: 2005

In this article we study the behavior of a group of economic agents in the context of cooperative game theory, interacting according to rules based on the Potts Model with suitable modifications. Each agent can be thought of as belonging to a chain, where agents can only interact with their nearest neighbors (periodic boundary conditions are imposed). Each agent can invest an amount σ_{i}=0,...,q-1. Using the transfer matrix method we study analytically, among other things, the behavior of the investment as a function of a control parameter (denoted β) for the cases q=2 and 3. For q>3 numerical evaluation of eigenvalues and high precision numerical derivatives are used in order to assess this information.
On the Shannon cipher system with a capacity-limited key-distribution channel
Venue: arXiv cs.IT 2005
Year: 2005

We consider the Shannon cipher system in a setting where the secret key is delivered to the legitimate receiver via a channel with limited capacity. For this setting, we characterize the achievable region in the space of three figures of merit: the security (measured in terms of the equivocation), the compressibility of the cryptogram, and the distortion associated with the reconstruction of the plaintext source. Although lossy reconstruction of the plaintext does not rule out the option that the (noisy) decryption key would differ, to a certain extent, from the encryption key, we show, nevertheless, that the best strategy is to strive for perfect match between the two keys, by applying reliable channel coding to the key bits, and to control the distortion solely via rate-distortion coding of the plaintext source before the encryption. In this sense, our result has a flavor similar to that of the classical source-channel separation theorem. Some variations and extensions of this model are discussed as well.
Visual Character Recognition using Artificial Neural Networks
Venue: arXiv cs.NE 2005
Year: 2005

The recognition of optical characters is known to be one of the earliest applications of Artificial Neural Networks, which partially emulate human thinking in the domain of artificial intelligence. In this paper, a simplified neural approach to recognition of optical or visual characters is portrayed and discussed. The document is expected to serve as a resource for learners and amateur investigators in pattern recognition, neural networking and related disciplines.
Artificial Neural Networks and their Applications
Venue: arXiv cs.NE 2005
Year: 2005

The Artificial Neural network is a functional imitation of simplified model of the biological neurons and their goal is to construct useful computers for real world problems. The ANN applications have increased dramatically in the last few years fired by both theoretical and practical applications in a wide variety of applications. A brief theory of ANN is presented and potential areas are identified and future trends are discussed.
Estudo e Implementacao de Algoritmos de Roteamento sobre Grafos em um Sistema de Informacoes Geograficas
Venue: arXiv cs.MS 2005
Year: 2005

This article presents an implementation of a graphical software with various algorithms in Operations research, like minimum path, minimum tree, chinese postman problem and travelling salesman.
Minimal Eulerian trail in a labeled digraph
Venue: arXiv cs.DM 2005
Year: 2005

Let $G$ be an Eulerian directed graph with an arc-labeling such that arcs going out from the same vertex have different labels. In this work, we present an algorithm to construct the Eulerian trail starting at an arbitrary vertex $v$ of minimum lexicographical label among labels of all Eulerian trails starting at this vertex. We also show an application of this algorithm to construct the minimal de Bruijn sequence of a language.
Methods for comparing rankings of search engine results
Venue: arXiv cs.IR 2005
Year: 2005

In this paper we present a number of measures that compare rankings of search engine results. We apply these measures to five queries that were monitored daily for two periods of about 21 days each. Rankings of the different search engines (Google, Yahoo and Teoma for text searches and Google, Yahoo and Picsearch for image searches) are compared on a daily basis, in addition to longitudinal comparisons of the same engine for the same query over time. The results and rankings of the two periods are compared as well.
Relational reasoning in the region connection calculus
Venue: arXiv cs.AI 2005
Year: 2005

This paper is mainly concerned with the relation-algebraical aspects of the well-known Region Connection Calculus (RCC). We show that the contact relation algebra (CRA) of certain RCC model is not atomic complete and hence infinite. So in general an extensional composition table for the RCC cannot be obtained by simply refining the RCC8 relations. After having shown that each RCC model is a consistent model of the RCC11 CT, we give an exhaustive investigation about extensional interpretation of the RCC11 CT. More important, we show the complemented closed disk algebra is a representation for the relation algebra determined by the RCC11 table. The domain of this algebra contains two classes of regions, the closed disks and closures of their complements in the real plane.
Optimum Signal Linear Detector in the Discrete Wavelet Transform-Domain
Venue: arXiv cs.IT 2005
Year: 2005

The problem of known signal detection in Additive White Gaussian Noise is considered. In this paper a new detection algorithm based on Discrete Wavelet Transform pre-processing and threshold comparison is introduced. Current approaches described in [7] use the maximum value obtained in the wavelet domain for decision. Here, we use all available information in the wavelet domain with excellent results. Detector performance is presented in Probability of detection curves for a fixed probability of false alarm.
The QDF file format: an electronic system to describe ancient andean khipus
Venue: arXiv cs.CY 2005
Year: 2005

With the goal of bringing to reseachers of the ancient andean khipus with a tool to share and process electronically the current corpus of these ancient information devices, I present on this paper a proposal for a Quipu Description Format (QDF), a XML based file format designed to describe such documents in a systematic and computer standard way.
EAH: A New Encoder based on Adaptive Variable-length Codes
Venue: arXiv cs.DS 2005
Year: 2005

Adaptive variable-length codes associate a variable-length codeword to the symbol being encoded depending on the previous symbols in the input string. This class of codes has been recently presented in [Dragos Trinca, arXiv:cs.DS/0505007] as a new class of non-standard variable-length codes. New algorithms for data compression, based on adaptive variable-length codes of order one and Huffman's algorithm, have been recently presented in [Dragos Trinca, ITCC 2004]. In this paper, we extend the work done so far by the following contributions: first, we propose an improved generalization of these algorithms, called EAHn. Second, we compute the entropy bounds for EAHn, using the well-known bounds for Huffman's algorithm. Third, we discuss implementation details and give reports of experimental results obtained on some well-known corpora. Finally, we describe a parallel version of EAHn using the PRAM model of computation.
Gossip Codes for Fingerprinting: Construction, Erasure Analysis and Pirate Tracing
Venue: arXiv cs.CR 2005
Year: 2005

This work presents two new construction techniques for q-ary Gossip codes from tdesigns and Traceability schemes. These Gossip codes achieve the shortest code length specified in terms of code parameters and can withstand erasures in digital fingerprinting applications. This work presents the construction of embedded Gossip codes for extending an existing Gossip code into a bigger code. It discusses the construction of concatenated codes and realisation of erasure model through concatenated codes.
Decision Sort and its Parallel Implementation
Venue: arXiv cs.DS 2005
Year: 2005

In this paper, a sorting technique is presented that takes as input a data set whose primary key domain is known to the sorting algorithm, and works with an time efficiency of O(n+k), where k is the primary key domain. It is shown that the algorithm has applicability over a wide range of data sets. Later, a parallel formulation of the same is proposed and its effectiveness is argued. Though this algorithm is applicable over a wide range of general data sets, it finds special application (much superior to others) in places where sorting information that arrives in parts and in cases where input data is huge in size.
Handling boundary constraints for numerical optimization by particle swarm flying in periodic search space
Venue: arXiv cs.NE 2005
Year: 2005

The periodic mode is analyzed together with two conventional boundary handling modes for particle swarm. By providing an infinite space that comprises periodic copies of original search space, it avoids possible disorganizing of particle swarm that is induced by the undesired mutations at the boundary. The results on benchmark functions show that particle swarm with periodic mode is capable of improving the search performance significantly, by compared with that of conventional modes and other algorithms.
Steganographic Codes -- a New Problem of Coding Theory
Venue: arXiv cs.CR 2005
Year: 2005

To study how to design steganographic algorithm more efficiently, a new coding problem -- steganographic codes (abbreviated stego-codes) -- is presented in this paper. The stego-codes are defined over the field with $q(q\ge2)$ elements. Firstly a method of constructing linear stego-codes is proposed by using the direct sum of vector subspaces. And then the problem of linear stego-codes is converted to an algebraic problem by introducing the concept of $t$th dimension of vector space. And some bounds on the length of stego-codes are obtained, from which the maximum length embeddable (MLE) code is brought up. It is shown that there is a corresponding relation between MLE codes and perfect error-correcting codes. Furthermore the classification of all MLE codes and a lower bound on the number of binary MLE codes are obtained based on the corresponding results on perfect codes. Finally hiding redundancy is defined to value the performance of stego-codes.
Instance-Independent View Serializability for Semistructured Databases
Venue: arXiv cs.DB 2005
Year: 2005

Semistructured databases require tailor-made concurrency control mechanisms since traditional solutions for the relational model have been shown to be inadequate. Such mechanisms need to take full advantage of the hierarchical structure of semistructured data, for instance allowing concurrent updates of subtrees of, or even individual elements in, XML documents. We present an approach for concurrency control which is document-independent in the sense that two schedules of semistructured transactions are considered equivalent if they are equivalent on all possible documents. We prove that it is decidable in polynomial time whether two given schedules in this framework are equivalent. This also solves the view serializability for semistructured schedules polynomially in the size of the schedule and exponentially in the number of transactions.
On the Parity-Check Density and Achievable Rates of LDPC Codes
Venue: arXiv cs.IT 2005
Year: 2005

The paper introduces new bounds on the asymptotic density of parity-check matrices and the achievable rates under ML decoding of binary linear block codes transmitted over memoryless binary-input output-symmetric channels. The lower bounds on the parity-check density are expressed in terms of the gap between the channel capacity and the rate of the codes for which reliable communication is achievable, and are valid for every sequence of binary linear block codes. The bounds address the question, previously considered by Sason and Urbanke, of how sparse can parity-check matrices of binary linear block codes be as a function of the gap to capacity. The new upper bounds on the achievable rates of binary linear block codes tighten previously reported bounds by Burshtein et al., and therefore enable to obtain tighter upper bounds on the thresholds of sequences of binary linear block codes under ML decoding. The bounds are applied to low-density parity-check (LDPC) codes, and the improvement in their tightness is exemplified numerically.
Defensive forecasting
Venue: arXiv cs.LG 2005
Year: 2005

We consider how to make probability forecasts of binary labels. Our main mathematical result is that for any continuous gambling strategy used for detecting disagreement between the forecasts and the actual labels, there exists a forecasting strategy whose forecasts are ideal as far as this gambling strategy is concerned. A forecasting strategy obtained in this way from a gambling strategy demonstrating a strong law of large numbers is simplified and studied empirically.
Bounds on the Automata Size for Presburger Arithmetic
Venue: arXiv cs.LO 2005
Year: 2005

Automata provide a decision procedure for Presburger arithmetic. However, until now only crude lower and upper bounds were known on the sizes of the automata produced by this approach. In this paper, we prove an upper bound on the the number of states of the minimal deterministic automaton for a Presburger arithmetic formula. This bound depends on the length of the formula and the quantifiers occurring in the formula. The upper bound is established by comparing the automata for Presburger arithmetic formulas with the formulas produced by a quantifier elimination method. We also show that our bound is tight, even for nondeterministic automata. Moreover, we provide optimal automata constructions for linear equations and inequations.
On the Achievable Diversity-Multiplexing Tradeoffs in Half-Duplex Cooperative Channels
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we propose novel cooperative transmission protocols for delay limited coherent fading channels consisting of N (half-duplex and single-antenna) partners and one cell site. In our work, we differentiate between the relay, cooperative broadcast (down-link), and cooperative multiple-access (up-link) channels. For the relay channel, we investigate two classes of cooperation schemes; namely, Amplify and Forward (AF) protocols and Decode and Forward (DF) protocols. For the first class, we establish an upper bound on the achievable diversity-multiplexing tradeoff with a single relay. We then construct a new AF protocol that achieves this upper bound. The proposed algorithm is then extended to the general case with N-1 relays where it is shown to outperform the space-time coded protocol of Laneman and Worenell without requiring decoding/encoding at the relays. For the class of DF protocols, we develop a dynamic decode and forward (DDF) protocol that achieves the optimal tradeoff for multiplexing gains 0 < r < 1/N. Furthermore, with a single relay, the DDF protocol is shown to dominate the class of AF protocols for all multiplexing gains. The superiority of the DDF protocol is shown to be more significant in the cooperative broadcast channel. The situation is reversed in the cooperative multiple-access channel where we propose a new AF protocol that achieves the optimal tradeoff for all multiplexing gains. A distinguishing feature of the proposed protocols in the three scenarios is that they do not rely on orthogonal subspaces, allowing for a more efficient use of resources. In fact, using our results one can argue that the sub-optimality of previously proposed protocols stems from their use of orthogonal subspaces rather than the half-duplex constraint.
Sparse Covariance Selection via Robust Maximum Likelihood Estimation
Venue: arXiv cs.CE 2005
Year: 2005

We address a problem of covariance selection, where we seek a trade-off between a high likelihood against the number of non-zero elements in the inverse covariance matrix. We solve a maximum likelihood problem with a penalty term given by the sum of absolute values of the elements of the inverse covariance matrix, and allow for imposing bounds on the condition number of the solution. The problem is directly amenable to now standard interior-point algorithms for convex optimization, but remains challenging due to its size. We first give some results on the theoretical computational complexity of the problem, by showing that a recent methodology for non-smooth convex optimization due to Nesterov can be applied to this problem, to greatly improve on the complexity estimate given by interior-point algorithms. We then examine two practical algorithms aimed at solving large-scale, noisy (hence dense) instances: one is based on a block-coordinate descent approach, where columns and rows are updated sequentially, another applies a dual version of Nesterov's method.
Framework for Hopfield Network based Adaptive routing - A design level approach for adaptive routing phenomena with Artificial Neural Network
Venue: arXiv cs.NE 2005
Year: 2005

Routing, as a basic phenomena, by itself, has got umpteen scopes to analyse, discuss and arrive at an optimal solution for the technocrats over years. Routing is analysed based on many factors; few key constraints that decide the factors are communication medium, time dependency, information source nature. Parametric routing has become the requirement of the day, with some kind of adaptation to the underlying network environment. Satellite constellations, particularly LEO satellite constellations have become a reality in operational to have a non-breaking voice/data communication around the world.Routing in these constellations has to be treated in a non conventional way, taking their network geometry into consideration. One of the efficient methods of optimization is putting Neural Networks to use. Few Artificial Neural Network models are very much suitable for the adaptive control mechanism, by their nature of network arrangement. One such efficient model is Hopfield Network model. This paper is an attempt to design a framework for the Hopfield Network based adaptive routing phenomena in satellite constellations.
Existentially Restricted Quantified Constraint Satisfaction
Venue: arXiv cs.CC 2005
Year: 2005

The quantified constraint satisfaction problem (QCSP) is a powerful framework for modelling computational problems. The general intractability of the QCSP has motivated the pursuit of restricted cases that avoid its maximal complexity. In this paper, we introduce and study a new model for investigating QCSP complexity in which the types of constraints given by the existentially quantified variables, is restricted. Our primary technical contribution is the development and application of a general technology for proving positive results on parameterizations of the model, of inclusion in the complexity class coNP.
Yet another normalisation proof for Martin-Lof's logical framework--Terms with correct arities are strongly normalising
Venue: arXiv cs.LO 2005
Year: 2005

In this paper, we prove the strong normalisation for Martin-Löf's Logical Framework, and suggest that {}``correct arity'', a condition weaker than well-typedness, will also guarantee the strong normalisation.
Open Questions in the Theory of Semifeasible Computation
Venue: arXiv cs.CC 2005
Year: 2005

The study of semifeasible algorithms was initiated by Selman's work a quarter of century ago [Sel79,Sel81,Sel82]. Informally put, this research stream studies the power of those sets L for which there is a deterministic (or in some cases, the function may belong to one of various nondeterministic function classes) polynomial-time function f such that when at least one of x and y belongs to L, then f(x,y) \in L \cap \{x,y\}. The intuition here is that it is saying: ``Regarding membership in L, if you put a gun to my head and forced me to bet on one of x or y as belonging to L, my money would be on f(x,y).'' In this article, we present a number of open problems from the theory of semifeasible algorithms. For each we present its background and review what partial results, if any, are known.
The One Page Model Checker
Venue: arXiv cs.LO 2005
Year: 2005

We show how standard IPC mechanisms can be used with the fork() system call to perform explicit state model checking on all interleavings of a multithreaded application. We specifically show how to check for deadlock and race conditions in programs with two threads. Our techniques are easy to apply to other languages, and require only the most rudimentary parsing of the target language. Our fundamental system fits in one page of C code.
On the Job Training
Venue: arXiv cs.LG 2005
Year: 2005

We propose a new framework for building and evaluating machine learning algorithms. We argue that many real-world problems require an agent which must quickly learn to respond to demands, yet can continue to perform and respond to new training throughout its useful life. We give a framework for how such agents can be built, describe several metrics for evaluating them, and show that subtle changes in system construction can significantly affect agent performance.
An Exact 2.9416^n Algorithm for the Three Domatic Number Problem
Venue: arXiv cs.CC 2005
Year: 2005

The three domatic number problem asks whether a given undirected graph can be partitioned into at least three dominating sets, i.e., sets whose closed neighborhood equals the vertex set of the graph. Since this problem is NP-complete, no polynomial-time algorithm is known for it. The naive deterministic algorithm for this problem runs in time 3^n, up to polynomial factors. In this paper, we design an exact deterministic algorithm for this problem running in time 2.9416^n. Thus, our algorithm can handle problem instances of larger size than the naive algorithm in the same amount of time. We also present another deterministic and a randomized algorithm for this problem that both have an even better performance for graphs with small maximum degree.
A New Construction for LDPC Codes using Permutation Polynomials over Integer Rings
Venue: arXiv cs.IT 2005
Year: 2005

A new construction is proposed for low density parity check (LDPC) codes using quadratic permutation polynomials over finite integer rings. The associated graphs for the new codes have both algebraic and pseudo-random nature, and the new codes are quasi-cyclic. Graph isomorphisms and automorphisms are identified and used in an efficient search for good codes. Graphs with girth as large as 12 were found. Upper bounds on the minimum Hamming distance are found both analytically and algorithmically. The bounds indicate that the minimum distance grows with block length. Near-codewords are one of the causes for error floors in LDPC codes; the new construction provides a good framework for studying near-codewords in LDPC codes. Nine example codes are given, and computer simulation results show the excellent error performance of these codes. Finally, connections are made between this new LDPC construction and turbo codes using interleavers generated by quadratic permutation polynomials.