OpenRaiser/Intern-Atlas huggingface dataset:
Comment on "Some non-conventional ideas about algorithmic complexity"
Venue: arXiv cs.CC 2005
Year: 2005

We comment on a recent paper by D'Abramo [Chaos, Solitons & Fractals, 25 (2005) 29], focusing on the author's statement that an algorithm can produce a list of strings containing at least one string whose algorithmic complexity is greater than that of the entire list. We show that this statement, although perplexing, is not as paradoxical as it seems when the definition of algorithmic complexity is applied correctly.
Soft Handoff and Uplink Capacity in a Two-Tier CDMA System
Venue: arXiv cs.IT 2005
Year: 2005

This paper examines the effect of soft handoff on the uplink user capacity of a CDMA system consisting of a single macrocell in which a single hotspot microcell is embedded. The users of these two base stations operate over the same frequency band. In the soft handoff scenario studied here, both macrocell and microcell base stations serve each system user and the two received copies of a desired user's signal are summed using maximal ratio combining. Exact and approximate analytical methods are developed to compute uplink user capacity. Simulation results demonstrate a 20% increase in user capacity compared to hard handoff. In addition, simple, approximate methods are presented for estimating soft handoff capacity and are shown to be quite accurate.
Hiding Satisfying Assignments: Two are Better than One
Venue: arXiv cs.AI 2005
Year: 2005

The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k-SAT formulas whose clauses are chosen uniformly from among all clauses satisfying some randomly chosen truth assignment A. Unfortunately, instances generated in this manner tend to be relatively easy and can be solved efficiently by practical heuristics. Roughly speaking, as the formula's density increases, for a number of different algorithms, A acts as a stronger and stronger attractor. Motivated by recent results on the geometry of the space of satisfying truth assignments of random k-SAT and NAE-k-SAT formulas, we introduce a simple twist on this basic model, which appears to dramatically increase its hardness. Namely, in addition to forbidding the clauses violated by the hidden assignment A, we also forbid the clauses violated by its complement, so that both A and complement of A are satisfying. It appears that under this "symmetrization'' the effects of the two attractors largely cancel out, making it much harder for algorithms to find any truth assignment. We give theoretical and experimental evidence supporting this assertion.
Randomly Spread CDMA: Asymptotics via Statistical Physics
Venue: arXiv cs.IT 2005
Year: 2005

This paper studies randomly spread code-division multiple access (CDMA) and multiuser detection in the large-system limit using the replica method developed in statistical physics. Arbitrary input distributions and flat fading are considered. A generic multiuser detector in the form of the posterior mean estimator is applied before single-user decoding. The generic detector can be particularized to the matched filter, decorrelator, linear MMSE detector, the jointly or the individually optimal detector, and others. It is found that the detection output for each user, although in general asymptotically non-Gaussian conditioned on the transmitted symbol, converges as the number of users go to infinity to a deterministic function of a "hidden" Gaussian statistic independent of the interferers. Thus the multiuser channel can be decoupled: Each user experiences an equivalent single-user Gaussian channel, whose signal-to-noise ratio suffers a degradation due to the multiple-access interference. The uncoded error performance (e.g., symbol-error-rate) and the mutual information can then be fully characterized using the degradation factor, also known as the multiuser efficiency, which can be obtained by solving a pair of coupled fixed-point equations identified in this paper. Based on a general linear vector channel model, the results are also applicable to MIMO channels such as in multiantenna systems.
Space-time databases modeling global semantic networks
Venue: arXiv cs.IT 2005
Year: 2005

This paper represents an approach to creating global knowledge systems, using new philosophy and infrastructure of global distributed semantic network (frame knowledge representation system) based on the space-time database construction. The main idea of the space-time database environment introduced in the paper is to bind a document (an information frame, a knowledge) to a special kind of entity, that we call permanent entity, -- an object without history and evolution, described by a "point" in the generalized, informational space-time (not an evolving object in the real space having history). For documents (information) it means that document content is unchangeable, and documents are absolutely persistent. This approach leads to new knowledge representation and retreival techniques. We discuss the way of applying the concept to a global distributed scientific library and scientific workspace. Some practical aspects of the work are elaborated by the open IT project at http://sourceforge.net/projects/gil/.
Spines of Random Constraint Satisfaction Problems: Definition and Connection with Computational Complexity
Venue: arXiv cs.CC 2005
Year: 2005

We study the connection between the order of phase transitions in combinatorial problems and the complexity of decision algorithms for such problems. We rigorously show that, for a class of random constraint satisfaction problems, a limited connection between the two phenomena indeed exists. Specifically, we extend the definition of the spine order parameter of Bollobas et al. to random constraint satisfaction problems, rigorously showing that for such problems a discontinuity of the spine is associated with a $2^{Ω(n)}$ resolution complexity (and thus a $2^{Ω(n)}$ complexity of DPLL algorithms) on random instances. The two phenomena have a common underlying cause: the emergence of ``large'' (linear size) minimally unsatisfiable subformulas of a random formula at the satisfiability phase transition. We present several further results that add weight to the intuition that random constraint satisfaction problems with a sharp threshold and a continuous spine are ``qualitatively similar to random 2-SAT''. Finally, we argue that it is the spine rather than the backbone parameter whose continuity has implications for the decision complexity of combinatorial problems, and we provide experimental evidence that the two parameters can behave in a different manner.
Statistical analysis of quality measures for mobile ad hoc networks
Venue: arXiv cs.NI 2005
Year: 2005

How can the quality of a mobile ad hoc network (MANET) be quantified? This work aims at an answer based on the lower network layers, i.e. on connectivity between the wireless nodes, using statistical methods. A number of different quality measures are introduced and classified according to their scaling behaviour. They are analysed in a statistical model of a 1-dimensional MANET system (corresponding e.g. to cars on a road). Neglecting boundary effects, the model turns out to be exactly solvable, so that explicit analytical results for the quality levels can be obtained both at fixed system size and in the limit of large systems. In particular, this improves estimates known in the literature for the probability of connectedness of 1-dimensional MANETs.
Fast Codes for Large Alphabets
Venue: arXiv cs.IT 2005
Year: 2005

We address the problem of constructing a fast lossless code in the case when the source alphabet is large. The main idea of the new scheme may be described as follows. We group letters with small probabilities in subsets (acting as super letters) and use time consuming coding for these subsets only, whereas letters in the subsets have the same code length and therefore can be coded fast. The described scheme can be applied to sources with known and unknown statistics.
Using Information Theory Approach to Randomness Testing
Venue: arXiv cs.IT 2005
Year: 2005

We address the problem of detecting deviations of binary sequence from randomness,which is very important for random number (RNG) and pseudorandom number generators (PRNG). Namely, we consider a null hypothesis $H_0$ that a given bit sequence is generated by Bernoulli source with equal probabilities of 0 and 1 and the alternative hypothesis $H_1$ that the sequence is generated by a stationary and ergodic source which differs from the source under $H_0$. We show that data compression methods can be used as a basis for such testing and describe two new tests for randomness, which are based on ideas of universal coding. Known statistical tests and suggested ones are applied for testing PRNGs. Those experiments show that the power of the new tests is greater than of many known algorithms.
Network Information Flow with Correlated Sources
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we consider a network communications problem in which multiple correlated sources must be delivered to a single data collector node, over a network of noisy independent point-to-point channels. We prove that perfect reconstruction of all the sources at the sink is possible if and only if, for all partitions of the network nodes into two subsets S and S^c such that the sink is always in S^c, we have that H(U_S|U_{S^c}) < \sum_{i\in S,j\in S^c} C_{ij}. Our main finding is that in this setup a general source/channel separation theorem holds, and that Shannon information behaves as a classical network flow, identical in nature to the flow of water in pipes. At first glance, it might seem surprising that separation holds in a fairly general network situation like the one we study. A closer look, however, reveals that the reason for this is that our model allows only for independent point-to-point channels between pairs of nodes, and not multiple-access and/or broadcast channels, for which separation is well known not to hold. This ``information as flow'' view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of implementing codes using a layered protocol stack.
Efficient Authenticated Encryption Schemes with Public Verifiability
Venue: arXiv cs.CR 2005
Year: 2005

An authenticated encryption scheme allows messages to be encrypted and authenticated simultaneously. In 2003, Ma and Chen proposed such a scheme with public verifiability. That is, in their scheme the receiver can efficiently prove to a third party that a message is indeed originated from a specific sender. In this paper, we first identify two security weaknesses in the Ma-Chen authenticated encryption scheme. Then, based on the Schnorr signature, we proposed an efficient and secure improved scheme such that all the desired security requirements are satisfied.
The Bayesian Decision Tree Technique with a Sweeping Strategy
Venue: arXiv cs.AI 2005
Year: 2005

The uncertainty of classification outcomes is of crucial importance for many safety critical applications including, for example, medical diagnostics. In such applications the uncertainty of classification can be reliably estimated within a Bayesian model averaging technique that allows the use of prior information. Decision Tree (DT) classification models used within such a technique gives experts additional information by making this classification scheme observable. The use of the Markov Chain Monte Carlo (MCMC) methodology of stochastic sampling makes the Bayesian DT technique feasible to perform. However, in practice, the MCMC technique may become stuck in a particular DT which is far away from a region with a maximal posterior. Sampling such DTs causes bias in the posterior estimates, and as a result the evaluation of classification uncertainty may be incorrect. In a particular case, the negative effect of such sampling may be reduced by giving additional prior information on the shape of DTs. In this paper we describe a new approach based on sweeping the DTs without additional priors on the favorite shape of DTs. The performances of Bayesian DT techniques with the standard and sweeping strategies are compared on a synthetic data as well as on real datasets. Quantitatively evaluating the uncertainty in terms of entropy of class posterior probabilities, we found that the sweeping strategy is superior to the standard strategy.
JClarens: A Java Framework for Developing and Deploying Web Services for Grid Computing
Venue: arXiv cs.DC 2005
Year: 2005

High Energy Physics (HEP) and other scientific communities have adopted Service Oriented Architectures (SOA) as part of a larger Grid computing effort. This effort involves the integration of many legacy applications and programming libraries into a SOA framework. The Grid Analysis Environment (GAE) is such a service oriented architecture based on the Clarens Grid Services Framework and is being developed as part of the Compact Muon Solenoid (CMS) experiment at the Large Hadron Collider (LHC) at European Laboratory for Particle Physics (CERN). Clarens provides a set of authorization, access control, and discovery services, as well as XMLRPC and SOAP access to all deployed services. Two implementations of the Clarens Web Services Framework (Python and Java) offer integration possibilities for a wide range of programming languages. This paper describes the Java implementation of the Clarens Web Services Framework called JClarens. and several web services of interest to the scientific and Grid community that have been deployed using JClarens.
A Neural-Network Technique for Recognition of Filaments in Solar Images
Venue: arXiv cs.NE 2005
Year: 2005

We describe a new neural-network technique developed for an automated recognition of solar filaments visible in the hydrogen H-alpha line full disk spectroheliograms. This technique allows neural networks learn from a few image fragments labelled manually to recognize the single filaments depicted on a local background. The trained network is able to recognize filaments depicted on the backgrounds with variations in brightness caused by atmospherics distortions. Despite the difference in backgrounds in our experiments the neural network has properly recognized filaments in the testing image fragments. Using a parabolic activation function we extend this technique to recognize multiple solar filaments which may appear in one fragment.
A Learning Algorithm for Evolving Cascade Neural Networks
Venue: arXiv cs.NE 2005
Year: 2005

A new learning algorithm for Evolving Cascade Neural Networks (ECNNs) is described. An ECNN starts to learn with one input node and then adding new inputs as well as new hidden neurons evolves it. The trained ECNN has a nearly minimal number of input and hidden neurons as well as connections. The algorithm was successfully applied to classify artifacts and normal segments in clinical electroencephalograms (EEGs). The EEG segments were visually labeled by EEG-viewer. The trained ECNN has correctly classified 96.69% of the testing segments. It is slightly better than a standard fully connected neural network.
Comparison of the Bayesian and Randomised Decision Tree Ensembles within an Uncertainty Envelope Technique
Venue: arXiv cs.AI 2005
Year: 2005

Multiple Classifier Systems (MCSs) allow evaluation of the uncertainty of classification outcomes that is of crucial importance for safety critical applications. The uncertainty of classification is determined by a trade-off between the amount of data available for training, the classifier diversity and the required performance. The interpretability of MCSs can also give useful information for experts responsible for making reliable classifications. For this reason Decision Trees (DTs) seem to be attractive classification models for experts. The required diversity of MCSs exploiting such classification models can be achieved by using two techniques, the Bayesian model averaging and the randomised DT ensemble. Both techniques have revealed promising results when applied to real-world problems. In this paper we experimentally compare the classification uncertainty of the Bayesian model averaging with a restarting strategy and the randomised DT ensemble on a synthetic dataset and some domain problems commonly used in the machine learning community. To make the Bayesian DT averaging feasible, we use a Markov Chain Monte Carlo technique. The classification uncertainty is evaluated within an Uncertainty Envelope technique dealing with the class posterior distribution and a given confidence probability. Exploring a full posterior distribution, this technique produces realistic estimates which can be easily interpreted in statistical terms. In our experiments we found out that the Bayesian DTs are superior to the randomised DT ensembles within the Uncertainty Envelope technique.
Knowledge Representation Issues in Semantic Graphs for Relationship Detection
Venue: arXiv cs.AI 2005
Year: 2005

An important task for Homeland Security is the prediction of threat vulnerabilities, such as through the detection of relationships between seemingly disjoint entities. A structure used for this task is a "semantic graph", also known as a "relational data graph" or an "attributed relational graph". These graphs encode relationships as "typed" links between a pair of "typed" nodes. Indeed, semantic graphs are very similar to semantic networks used in AI. The node and link types are related through an ontology graph (also known as a schema). Furthermore, each node has a set of attributes associated with it (e.g., "age" may be an attribute of a node of type "person"). Unfortunately, the selection of types and attributes for both nodes and links depends on human expertise and is somewhat subjective and even arbitrary. This subjectiveness introduces biases into any algorithm that operates on semantic graphs. Here, we raise some knowledge representation issues for semantic graphs and provide some possible solutions using recently developed ideas in the field of complex networks. In particular, we use the concept of transitivity to evaluate the relevance of individual links in the semantic graph for detecting relationships. We also propose new statistical measures for semantic graphs and illustrate these semantic measures on graphs constructed from movies and terrorism data.
Rendezvous Regions: A Scalable Architecture for Resource Discovery and Service Location in Large-Scale Mobile Networks
Venue: arXiv cs.NI 2005
Year: 2005

In large-scale wireless networks such as mobile ad hoc and sensor networks, efficient and robust service discovery and data-access mechanisms are both essential and challenging. Rendezvous-based mechanisms provide a valuable solution for provisioning a wide range of services. In this paper, we describe Rendezvous Regions (RRs) - a novel scalable rendezvous-based architecture for wireless networks. RR is a general architecture proposed for service location and bootstrapping in ad hoc networks, in addition to data-centric storage, configuration, and task assignment in sensor networks. In RR the network topology is divided into geographical regions, where each region is responsible for a set of keys representing the services or data of interest. Each key is mapped to a region based on a hash-table-like mapping scheme. A few elected nodes inside each region are responsible for maintaining the mapped information. The service or data provider stores the information in the corresponding region and the seekers retrieve it from there. We run extensive detailed simulations, and high-level simulations and analysis, to investigate the design space, and study the architecture in various environments including node mobility and failures. We evaluate it against other approaches to identify its merits and limitations. The results show high success rate and low overhead even with dynamics. RR scales to large number of nodes and is highly robust and efficient to node failures. It is also robust to node mobility and location inaccuracy with a significant advantage over point-based rendezvous mechanisms.
Performance of Gaussian Signalling in Non Coherent Rayleigh Fading Channels
Venue: arXiv cs.IT 2005
Year: 2005

The mutual information of a discrete time memoryless Rayleigh fading channel is considered, where neither the transmitter nor the receiver has the knowledge of the channel state information except the fading statistics. We present the mutual information of this channel in closed form when the input distribution is complex Gaussian, and derive a lower bound in terms of the capacity of the corresponding non fading channel and the capacity when the perfect channel state information is known at the receiver.
The Capacity of Random Ad hoc Networks under a Realistic Link Layer Model
Venue: arXiv cs.IT 2005
Year: 2005

The problem of determining asymptotic bounds on the capacity of a random ad hoc network is considered. Previous approaches assumed a threshold-based link layer model in which a packet transmission is successful if the SINR at the receiver is greater than a fixed threshold. In reality, the mapping from SINR to packet success probability is continuous. Hence, over each hop, for every finite SINR, there is a non-zero probability of packet loss. With this more realistic link model, it is shown that for a broad class of routing and scheduling schemes, a fixed fraction of hops on each route have a fixed non-zero packet loss probability. In a large network, a packet travels an asymptotically large number of hops from source to destination. Consequently, it is shown that the cumulative effect of per-hop packet loss results in a per-node throughput of only O(1/n) (instead of Theta(1/sqrt{n log{n}})) as shown previously for the threshold-based link model). A scheduling scheme is then proposed to counter this effect. The proposed scheme improves the link SINR by using conservative spatial reuse, and improves the per-node throughput to O(1/(K_n sqrt{n log{n}})), where each cell gets a transmission opportunity at least once every K_n slots, and K_n tends to infinity as n tends to infinity.
Adaptive Codes: A New Class of Non-standard Variable-length Codes
Venue: arXiv cs.DS 2005
Year: 2005

We introduce a new class of non-standard variable-length codes, called adaptive codes. This class of codes associates a variable-length codeword to the symbol being encoded depending on the previous symbols in the input data string. An efficient algorithm for constructing adaptive codes of order one is presented. Then, we introduce a natural generalization of adaptive codes, called GA codes.
Point set stratification and Delaunay depth
Venue: arXiv cs.CG 2005
Year: 2005

In the study of depth functions it is important to decide whether we want such a function to be sensitive to multimodality or not. In this paper we analyze the Delaunay depth function, which is sensitive to multimodality and compare this depth with others, as convex depth and location depth. We study the stratification that Delaunay depth induces in the point set (layers) and in the whole plane (levels), and we develop an algorithm for computing the Delaunay depth contours, associated to a point set in the plane, with running time O(n log^2 n). The depth of a query point p with respect to a data set S in the plane is the depth of p in the union of S and p. When S and p are given in the input the Delaunay depth can be computed in O(n log n), and we prove that this value is optimal.
Equivalence-Checking on Infinite-State Systems: Techniques and Results
Venue: arXiv cs.LO 2005
Year: 2005

The paper presents a selection of recently developed and/or used techniques for equivalence-checking on infinite-state systems, and an up-to-date overview of existing results (as of September 2004).