OpenRaiser/Intern-Atlas huggingface dataset:
Life Under Your Feet: An End-to-End Soil Ecology Sensor Network, Database, Web Server, and Analysis Service
Venue: arXiv cs.DB 2007
Year: 2007

Wireless sensor networks can revolutionize soil ecology by providing measurements at temporal and spatial granularities previously impossible. This paper presents a soil monitoring system we developed and deployed at an urban forest in Baltimore as a first step towards realizing this vision. Motes in this network measure and save soil moisture and temperature in situ every minute. Raw measurements are periodically retrieved by a sensor gateway and stored in a central database where calibrated versions are derived and stored. The measurement database is published through Web Services interfaces. In addition, analysis tools let scientists analyze current and historical data and help manage the sensor network. The article describes the system design, what we learned from the deployment, and initial results obtained from the sensors. The system measures soil factors with unprecedented temporal precision. However, the deployment required device-level programming, sensor calibration across space and time, and cross-referencing measurements with external sources. The database, web server, and data analysis design required considerable innovation and expertise. So, the ratio of computer-scientists to ecologists was 3:1. Before sensor networks can fulfill their potential as instruments that can be easily deployed by scientists, these technical problems must be addressed so that the ratio is one nerd per ten ecologists.
Scatter of Weak Robots
Venue: arXiv cs.DC 2007
Year: 2007

In this paper, we first formalize the problem to be solved, i.e., the Scatter Problem (SP). We then show that SP cannot be deterministically solved. Next, we propose a randomized algorithm for this problem. The proposed solution is trivially self-stabilizing. We then show how to design a self-stabilizing version of any deterministic solution for the Pattern Formation and the Gathering problems.
A Note on Local Ultrametricity in Text
Venue: arXiv cs.CL 2007
Year: 2007

High dimensional, sparsely populated data spaces have been characterized in terms of ultrametric topology. This implies that there are natural, not necessarily unique, tree or hierarchy structures defined by the ultrametric topology. In this note we study the extent of local ultrametric topology in texts, with the aim of finding unique ``fingerprints'' for a text or corpus, discriminating between texts from different domains, and opening up the possibility of exploiting hierarchical structures in the data. We use coherent and meaningful collections of over 1000 texts, comprising over 1.3 million words.
Certification of the QR factor R, and of lattice basis reducedness
Venue: arXiv cs.SC 2007
Year: 2007

Given a lattice basis of n vectors in Z^n, we propose an algorithm using 12n^3+O(n^2) floating point operations for checking whether the basis is LLL-reduced. If the basis is reduced then the algorithm will hopefully answer ''yes''. If the basis is not reduced, or if the precision used is not sufficient with respect to n, and to the numerical properties of the basis, the algorithm will answer ''failed''. Hence a positive answer is a rigorous certificate. For implementing the certificate itself, we propose a floating point algorithm for computing (certified) error bounds for the entries of the R factor of the QR matrix factorization. This algorithm takes into account all possible approximation and rounding errors. The cost 12n^3+O(n^2) of the certificate is only six times more than the cost of numerical algorithms for computing the QR factorization itself, and the certificate may be implemented using matrix library routines only. We report experiments that show that for a reduced basis of adequate dimension and quality the certificate succeeds, and establish the effectiveness of the certificate. This effectiveness is applied for certifying the output of fastest existing floating point heuristics of LLL reduction, without slowing down the whole process.
An Abstract Monte-Carlo Method for the Analysis of Probabilistic Programs
Venue: arXiv cs.PL 2007
Year: 2007

We introduce a new method, combination of random testing and abstract interpretation, for the analysis of programs featuring both probabilistic and non-probabilistic nondeterminism. After introducing "ordinary" testing, we show how to combine testing and abstract interpretation and give formulas linking the precision of the results to the number of iterations. We then discuss complexity and optimization issues and end with some experimental results.
A multivariate interlace polynomial
Venue: arXiv cs.LO 2007
Year: 2007

We define a multivariate polynomial that generalizes several interlace polynomials defined by Arratia, Bollobas and Sorkin on the one hand, and Aigner and van der Holst on the other. We follow the route traced by Sokal, who defined a multivariate generalization of Tutte's polynomial. We also show that bounded portions of our interlace polynomial can be evaluated in polynomial time for graphs of bounded clique-width. Its full evaluation is necessarly exponential just because of the size of the result.
Gaussian Interference Channel Capacity to Within One Bit
Venue: arXiv cs.IT 2007
Year: 2007

The capacity of the two-user Gaussian interference channel has been open for thirty years. The understanding on this problem has been limited. The best known achievable region is due to Han-Kobayashi but its characterization is very complicated. It is also not known how tight the existing outer bounds are. In this work, we show that the existing outer bounds can in fact be arbitrarily loose in some parameter ranges, and by deriving new outer bounds, we show that a simplified Han-Kobayashi type scheme can achieve to within a single bit the capacity for all values of the channel parameters. We also show that the scheme is asymptotically optimal at certain high SNR regimes. Using our results, we provide a natural generalization of the point-to-point classical notion of degrees of freedom to interference-limited scenarios.
On the possibility of making the complete computer model of a human brain
Venue: arXiv cs.NE 2007
Year: 2007

The development of the algorithm of a neural network building by the corresponding parts of a DNA code is discussed.
Firebird Database Backup by Serialized Database Table Dump
Venue: arXiv cs.DB 2007
Year: 2007

This paper presents a simple data dump and load utility for Firebird databases which mimics mysqldump in MySQL. This utility, fb_dump and fb_load, for dumping and loading respectively, retrieves each database table using kinterbasdb and serializes the data using marshal module. This utility has two advantages over the standard Firebird database backup utility, gbak. Firstly, it is able to backup and restore single database tables which might help to recover corrupted databases. Secondly, the output is in text-coded format (from marshal module) making it more resilient than a compressed text backup, as in the case of using gbak.
Authentication via wireless networks
Venue: arXiv cs.OH 2007
Year: 2007

Personal authentication is an important process we encounter almost every day; when we are logging on a computer, entering a company where we work, or a restricted area, when we are using our plastic credit cards to pay for a service or to complete some other financial transaction, etc. In each of these processes of personal authentication some kind of magnetic or optical token is required. But by using novel technologies like mobile computing and wireless networking, it is possible to avoid carrying multitude of ID cards or remembering a number of PIN codes. Article shows how to efficiently authenticate users via Personal Area Networks (PAN) like Bluetooth or IrDA using commonplace AES (Rijndel) or MD5 encryption. This method can be implemented on many types of mobile devices like Pocket PC PDA with Windows CE (Windows Mobile 2003) real-time operating system, or any other customized OS, so we will explain all components and key features of such basic system.
A note on using finite non-abelian $p$-groups in the MOR cryptosystem
Venue: arXiv cs.CR 2007
Year: 2007

The MOR cryptosystem is a natural generalization of the El-Gamal cryptosystem to non-abelian groups. Using a $p$-group, a cryptosystem was built by this author in 'A simple generalization of El-Gamal cryptosystem to non-abelian groups'. It seems reasonable to assume the cryptosystem is as secure as the El-Gamal cryptosystem over finite fields. A natural question arises can one make a better cryptosystem using $p$-groups? In this paper we show that the answer is no.
Exploring the academic invisible web
Venue: arXiv cs.DL 2007
Year: 2007

Purpose: To provide a critical review of Bergman's 2001 study on the Deep Web. In addition, we bring a new concept into the discussion, the Academic Invisible Web (AIW). We define the Academic Invisible Web as consisting of all databases and collections relevant to academia but not searchable by the general-purpose internet search engines. Indexing this part of the Invisible Web is central to scientific search engines. We provide an overview of approaches followed thus far. Design/methodology/approach: Discussion of measures and calculations, estimation based on informetric laws. Literature review on approaches for uncovering information from the Invisible Web. Findings: Bergman's size estimate of the Invisible Web is highly questionable. We demonstrate some major errors in the conceptual design of the Bergman paper. A new (raw) size estimate is given. Research limitations/implications: The precision of our estimate is limited due to a small sample size and lack of reliable data. Practical implications: We can show that no single library alone will be able to index the Academic Invisible Web. We suggest collaboration to accomplish this task. Originality/value: Provides library managers and those interested in developing academic search engines with data on the size and attributes of the Academic Invisible Web.
Informed Dynamic Scheduling for Belief-Propagation Decoding of LDPC Codes
Venue: arXiv cs.IT 2007
Year: 2007

Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation, or message-passing, algorithm over the factor graph of the code. The traditional message-passing schedule consists of updating all the variable nodes in the graph, using the same pre-update information, followed by updating all the check nodes of the graph, again, using the same pre-update information. Recently several studies show that sequential scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. Sequential scheduling raises the problem of finding the best sequence of message updates. This paper presents practical scheduling strategies that use the value of the messages in the graph to find the next message to be updated. Simulation results show that these informed update sequences require significantly fewer iterations than standard sequential schedules. Furthermore, the paper shows that informed scheduling solves some standard trapping set errors. Therefore, it also outperforms traditional scheduling for a large numbers of iterations. Complexity and implementability issues are also addressed.
On the decidability and complexity of Metric Temporal Logic over finite words
Venue: arXiv cs.LO 2007
Year: 2007

Metric Temporal Logic (MTL) is a prominent specification formalism for real-time systems. In this paper, we show that the satisfiability problem for MTL over finite timed words is decidable, with non-primitive recursive complexity. We also consider the model-checking problem for MTL: whether all words accepted by a given Alur-Dill timed automaton satisfy a given MTL formula. We show that this problem is decidable over finite words. Over infinite words, we show that model checking the safety fragment of MTL--which includes invariance and time-bounded response properties--is also decidable. These results are quite surprising in that they contradict various claims to the contrary that have appeared in the literature.
High Performance Direct Gravitational N-body Simulations on Graphics Processing Units
Venue: arXiv cs.PF 2007
Year: 2007

We present the results of gravitational direct $N$-body simulations using the commercial graphics processing units (GPU) NVIDIA Quadro FX1400 and GeForce 8800GTX, and compare the results with GRAPE-6Af special purpose hardware. The force evaluation of the $N$-body problem was implemented in Cg using the GPU directly to speed-up the calculations. The integration of the equations of motions were, running on the host computer, implemented in C using the 4th order predictor-corrector Hermite integrator with block time steps. We find that for a large number of particles ($N \apgt 10^4$) modern graphics processing units offer an attractive low cost alternative to GRAPE special purpose hardware. A modern GPU continues to give a relatively flat scaling with the number of particles, comparable to that of the GRAPE. Using the same time step criterion the total energy of the $N$-body system was conserved better than to one in $10^6$ on the GPU, which is only about an order of magnitude worse than obtained with GRAPE. For $N\apgt 10^6$ the GeForce 8800GTX was about 20 times faster than the host computer. Though still about an order of magnitude slower than GRAPE, modern GPU's outperform GRAPE in their low cost, long mean time between failure and the much larger onboard memory; the GRAPE-6Af holds at most 256k particles whereas the GeForce 8800GTF can hold 9 million particles in memory.
Tree Automata and Essential Subtrees
Venue: arXiv cs.CC 2007
Year: 2007

We introduce essential subtrees for terms (trees) and tree automata . There are some results concerning independent sets of subtrees and separable sets for a tree and an automaton.
Characterization of $m$-Sequences of Lengths $2^{2k}-1$ and $2^k-1$ with Three-Valued Crosscorrelation
Venue: arXiv cs.CR 2007
Year: 2007

Considered is the distribution of the crosscorrelation between $m$-sequences of length $2^m-1$, where $m=2k$, and $m$-sequences of shorter length $2^k-1$. New pairs of $m$-sequences with three-valued crosscorrelation are found and the complete correlation distribution is determined. Finally, we conjecture that there are no more cases with a three-valued crosscorrelation apart from the ones proven here.
Linking Microscopic and Macroscopic Models for Evolution: Markov Chain Network Training and Conservation Law Approximations
Venue: arXiv cs.CE 2007
Year: 2007

In this paper, a general framework for the analysis of a connection between the training of artificial neural networks via the dynamics of Markov chains and the approximation of conservation law equations is proposed. This framework allows us to demonstrate an intrinsic link between microscopic and macroscopic models for evolution via the concept of perturbed generalized dynamic systems. The main result is exemplified with a number of illustrative examples where efficient numerical approximations follow directly from network-based computational models, viewed here as Markov chain approximations. Finally, stability and consistency conditions of such computational models are discussed.
A note on rate-distortion functions for nonstationary Gaussian autoregressive processes
Venue: arXiv cs.IT 2007
Year: 2007

Source coding theorems and Shannon rate-distortion functions were studied for the discrete-time Wiener process by Berger and generalized to nonstationary Gaussian autoregressive processes by Gray and by Hashimoto and Arimoto. Hashimoto and Arimoto provided an example apparently contradicting the methods used in Gray, implied that Gray's rate-distortion evaluation was not correct in the nonstationary case, and derived a new formula that agreed with previous results for the stationary case and held in the nonstationary case. In this correspondence it is shown that the rate-distortion formulas of Gray and Hashimoto and Arimoto are in fact consistent and that the example of of Hashimoto and Arimoto does not form a counter example to the methods or results of the earlier paper. Their results do provide an alternative, but equivalent, formula for the rate-distortion function in the nonstationary case and they provide a concrete example that the classic Kolmogorov formula differs from the autoregressive formula when the autoregressive source is not stationary. Some observations are offered on the different versions of the Toeplitz asymptotic eigenvalue distribution theorem used in the two papers to emphasize how a slight modification of the classic theorem avoids the problems with certain singularities.
On a characterization of cellular automata in tilings of the hyperbolic plane
Venue: arXiv cs.DM 2007
Year: 2007

In this paper, we look at the extention of Hedlund's characterization of cellular automata to the case of cellular automata in the hyperbolic plane. This requires an additionnal condition. The new theorem is proved with full details in the case of the pentagrid and in the case of the ternary heptagrid and enough indications to show that it holds also on the grids $\{p,q\}$ of the hyperbolic plane.
Perfect Hashing for Data Management Applications
Venue: arXiv cs.DS 2007
Year: 2007

Perfect hash functions can potentially be used to compress data in connection with a variety of data management tasks. Though there has been considerable work on how to construct good perfect hash functions, there is a gap between theory and practice among all previous methods on minimal perfect hashing. On one side, there are good theoretical results without experimentally proven practicality for large key sets. On the other side, there are the theoretically analyzed time and space usage algorithms that assume that truly random hash functions are available for free, which is an unrealistic assumption. In this paper we attempt to bridge this gap between theory and practice, using a number of techniques from the literature to obtain a novel scheme that is theoretically well-understood and at the same time achieves an order-of-magnitude increase in performance compared to previous ``practical'' methods. This improvement comes from a combination of a novel, theoretically optimal perfect hashing scheme that greatly simplifies previous methods, and the fact that our algorithm is designed to make good use of the memory hierarchy. We demonstrate the scalability of our algorithm by considering a set of over one billion URLs from the World Wide Web of average length 64, for which we construct a minimal perfect hash function on a commodity PC in a little more than 1 hour. Our scheme produces minimal perfect hash functions using slightly more than 3 bits per key. For perfect hash functions in the range $\{0,...,2n-1\}$ the space usage drops to just over 2 bits per key (i.e., one bit more than optimal for representing the key). This is significantly below of what has been achieved previously for very large values of $n$.
Perfectly Secure Steganography: Capacity, Error Exponents, and Code Constructions
Venue: arXiv cs.IT 2007
Year: 2007

An analysis of steganographic systems subject to the following perfect undetectability condition is presented in this paper. Following embedding of the message into the covertext, the resulting stegotext is required to have exactly the same probability distribution as the covertext. Then no statistical test can reliably detect the presence of the hidden message. We refer to such steganographic schemes as perfectly secure. A few such schemes have been proposed in recent literature, but they have vanishing rate. We prove that communication performance can potentially be vastly improved; specifically, our basic setup assumes independently and identically distributed (i.i.d.) covertext, and we construct perfectly secure steganographic codes from public watermarking codes using binning methods and randomized permutations of the code. The permutation is a secret key shared between encoder and decoder. We derive (positive) capacity and random-coding exponents for perfectly-secure steganographic systems. The error exponents provide estimates of the code length required to achieve a target low error probability. We address the potential loss in communication performance due to the perfect-security requirement. This loss is the same as the loss obtained under a weaker order-1 steganographic requirement that would just require matching of first-order marginals of the covertext and stegotext distributions. Furthermore, no loss occurs if the covertext distribution is uniform and the distortion metric is cyclically symmetric; steganographic capacity is then achieved by randomized linear codes. Our framework may also be useful for developing computationally secure steganographic systems that have near-optimal communication performance.
Solving Stochastic Differential Equations with Jump-Diffusion Efficiently: Applications to FPT Problems in Credit Risk
Venue: arXiv cs.CE 2007
Year: 2007

The first passage time (FPT) problem is ubiquitous in many applications. In finance, we often have to deal with stochastic processes with jump-diffusion, so that the FTP problem is reducible to a stochastic differential equation with jump-diffusion. While the application of the conventional Monte-Carlo procedure is possible for the solution of the resulting model, it becomes computationally inefficient which severely restricts its applicability in many practically interesting cases. In this contribution, we focus on the development of efficient Monte-Carlo-based computational procedures for solving the FPT problem under the multivariate (and correlated) jump-diffusion processes. We also discuss the implementation of the developed Monte-Carlo-based technique for multivariate jump-diffusion processes driving by several compound Poisson shocks. Finally, we demonstrate the application of the developed methodologies for analyzing the default rates and default correlations of differently rated firms via historical data.
Simulation of Phase Combinations in Shape Memory Alloys Patches by Hybrid Optimization Methods
Venue: arXiv cs.CE 2007
Year: 2007

In this paper, phase combinations among martensitic variants in shape memory alloys patches and bars are simulated by a hybrid optimization methodology. The mathematical model is based on the Landau theory of phase transformations. Each stable phase is associated with a local minimum of the free energy function, and the phase combinations are simulated by minimizing the bulk energy. At low temperature, the free energy function has double potential wells leading to non-convexity of the optimization problem. The methodology proposed in the present paper is based on an initial estimate of the global solution by a genetic algorithm, followed by a refined quasi-Newton procedure to locally refine the optimum. By combining the local and global search algorithms, the phase combinations are successfully simulated. Numerical experiments are presented for the phase combinations in a SMA patch under several typical mechanical loadings.