OpenRaiser/Intern-Atlas huggingface dataset:
The Second Law as a Cause of the Evolution
Venue: arXiv cs.IT 2007
Year: 2007

It is a common belief that in any environment where life is possible, life will be generated. Here it is suggested that the cause for a spontaneous generation of complex systems is probability driven processes. Based on equilibrium thermodynamics, it is argued that in low occupation number statistical systems, the second law of thermodynamics yields an increase of thermal entropy and a canonic energy distribution. However, in high occupation number statistical systems, the same law for the same reasons yields an increase of information and a Benford's law/power-law energy distribution. It is therefore, plausible, that eventually the heat death is not necessarily the end of the universe.
Fluoroscopy-based navigation system in spine surgery
Venue: arXiv cs.OH 2007
Year: 2007

The variability in width, height, and spatial orientation of a spinal pedicle makes pedicle screw insertion a delicate operation. The aim of the current paper is to describe a computer-assisted surgical navigation system based on fluoroscopic X-ray image calibration and three-dimensional optical localizers in order to reduce radiation exposure while increasing accuracy and reliability of the surgical procedure for pedicle screw insertion. Instrumentation using transpedicular screw fixation was performed: in a first group, a conventional surgical procedure was carried out with 26 patients (138 screws); in a second group, a navigated surgical procedure (virtual fluoroscopy) was performed with 26 patients (140 screws). Evaluation of screw placement in every case was done by using plain X-rays and post-operative computer tomography scan. A 5 per cent cortex penetration (7 of 140 pedicle screws) occurred for the computer-assisted group. A 13 per cent penetration (18 of 138 pedicle screws) occurred for the non computer-assisted group. The radiation running time for each vertebra level (two screws) reached 3.5 s on average in the computer-assisted group and 11.5 s on average in the non computer-assisted group. The operative time for two screws on the same vertebra level reaches 10 min on average in the non computer-assisted group and 11.9 min on average in the computer-assisted group. The fluoroscopy-based (two-dimensional) navigation system for pedicle screw insertion is a safe and reliable procedure for surgery in the lower thoracic and lumbar spine.
On the Mutual Information Distribution of OFDM-Based Spatial Multiplexing: Exact Variance and Outage Approximation
Venue: arXiv cs.IT 2007
Year: 2007

This paper considers the distribution of the mutual information of frequency-selective spatially-uncorrelated Rayleigh fading MIMO channels. Results are presented for OFDM-based spatial multiplexing. New exact closed-form expressions are derived for the variance of the mutual information. In contrast to previous results, our new expressions apply for systems with both arbitrary numbers of antennas and arbitrary-length channels. Simplified expressions are also presented for high and low SNR regimes. The analytical variance results are used to provide accurate analytical approximations for the distribution of the mutual information and the outage capacity.
Recommended Practices for Spreadsheet Testing
Venue: arXiv cs.SE 2007
Year: 2007

This paper presents the authors recommended practices for spreadsheet testing. Documented spreadsheet error rates are unacceptable in corporations today. Although improvements are needed throughout the systems development life cycle, credible improvement programs must include comprehensive testing. Several forms of testing are possible, but logic inspection is recommended for module testing. Logic inspection appears to be feasible for spreadsheet developers to do, and logic inspection appears to be safe and effective.
Learning View Generalization Functions
Venue: arXiv cs.CV 2007
Year: 2007

Learning object models from views in 3D visual object recognition is usually formulated either as a function approximation problem of a function describing the view-manifold of an object, or as that of learning a class-conditional density. This paper describes an alternative framework for learning in visual object recognition, that of learning the view-generalization function. Using the view-generalization function, an observer can perform Bayes-optimal 3D object recognition given one or more 2D training views directly, without the need for a separate model acquisition step. The paper shows that view generalization functions can be computationally practical by restating two widely-used methods, the eigenspace and linear combination of views approaches, in a view generalization framework. The paper relates the approach to recent methods for object recognition based on non-uniform blurring. The paper presents results both on simulated 3D ``paperclip'' objects and real-world images from the COIL-100 database showing that useful view-generalization functions can be realistically be learned from a comparatively small number of training examples.
On the Accepting Power of 2-Tape Büchi Automata
Venue: arXiv cs.CC 2007
Year: 2007

We show that, from a topological point of view, 2-tape Büchi automata have the same accepting power than Turing machines equipped with a Büchi acceptance condition. In particular, we show that for every non null recursive ordinal alpha, there exist some Sigma^0_alpha-complete and some Pi^0_alpha-complete infinitary rational relations accepted by 2-tape Büchi automata. This very surprising result gives answers to questions of W. Thomas [Automata and Quantifier Hierarchies, in: Formal Properties of Finite automata and Applications, Ramatuelle, 1988, LNCS 386, Springer, 1989, p.104-119], of P. Simonnet [Automates et Théorie Descriptive, Ph. D. Thesis, Université Paris 7, March 1992], and of H. Lescow and W. Thomas [Logical Specifications of Infinite Computations, In: "A Decade of Concurrency", LNCS 803, Springer, 1994, p. 583-621].
Period of the d-Sequence Based Random Number Generator
Venue: arXiv cs.CR 2007
Year: 2007

This paper presents an expression to compute the exact period of a recursive random number generator based on d-sequences. Using the multi-recursive version of this generator we can produce large number of pseudorandom sequences.
Simrank++: Query rewriting through link analysis of the click graph
Venue: arXiv cs.DL 2007
Year: 2007

We focus on the problem of query rewriting for sponsored search. We base rewrites on a historical click graph that records the ads that have been clicked on in response to past user queries. Given a query q, we first consider Simrank as a way to identify queries similar to q, i.e., queries whose ads a user may be interested in. We argue that Simrank fails to properly identify query similarities in our application, and we present two enhanced version of Simrank: one that exploits weights on click graph edges and another that exploits ``evidence.'' We experimentally evaluate our new schemes against Simrank, using actual click graphs and queries form Yahoo!, and using a variety of metrics. Our results show that the enhanced methods can yield more and better query rewrites.
Prostate biopsies guided by three-dimensional real-time (4-D) transrectal ultrasonography on a phantom: comparative study versus two-dimensional transrectal ultrasound-guided biopsies
Venue: arXiv cs.OH 2007
Year: 2007

OBJECTIVE: This study evaluated the accuracy in localisation and distribution of real-time three-dimensional (4-D) ultrasound-guided biopsies on a prostate phantom. METHODS: A prostate phantom was created. A three-dimensional real-time ultrasound system with a 5.9MHz probe was used, making it possible to see several reconstructed orthogonal viewing planes in real time. Fourteen operators performed biopsies first under 2-D then 4-D transurethral ultrasound (TRUS) guidance (336 biopsies). The biopsy path was modelled using segmentation in a 3-D ultrasonographic volume. Special software was used to visualise the biopsy paths in a reference prostate and assess the sampled area. A comparative study was performed to examine the accuracy of the entry points and target of the needle. Distribution was assessed by measuring the volume sampled and a redundancy ratio of the sampled prostate. RESULTS: A significant increase in accuracy in hitting the target zone was identified using 4-D ultrasonography as compared to 2-D. There was no increase in the sampled volume or improvement in the biopsy distribution with 4-D ultrasonography as compared to 2-D. CONCLUSION: The 4-D TRUS guidance appears to show, on a synthetic model, an improvement in location accuracy and in the ability to reproduce a protocol. The biopsy distribution does not seem improved.
Computational Chemotaxis in Ants and Bacteria over Dynamic Environments
Venue: arXiv cs.MA 2007
Year: 2007

Chemotaxis can be defined as an innate behavioural response by an organism to a directional stimulus, in which bacteria, and other single-cell or multicellular organisms direct their movements according to certain chemicals in their environment. This is important for bacteria to find food (e.g., glucose) by swimming towards the highest concentration of food molecules, or to flee from poisons. Based on self-organized computational approaches and similar stigmergic concepts we derive a novel swarm intelligent algorithm. What strikes from these observations is that both eusocial insects as ant colonies and bacteria have similar natural mechanisms based on stigmergy in order to emerge coherent and sophisticated patterns of global collective behaviour. Keeping in mind the above characteristics we will present a simple model to tackle the collective adaptation of a social swarm based on real ant colony behaviors (SSA algorithm) for tracking extrema in dynamic environments and highly multimodal complex functions described in the well-know De Jong test suite. Later, for the purpose of comparison, a recent model of artificial bacterial foraging (BFOA algorithm) based on similar stigmergic features is described and analyzed. Final results indicate that the SSA collective intelligence is able to cope and quickly adapt to unforeseen situations even when over the same cooperative foraging period, the community is requested to deal with two different and contradictory purposes, while outperforming BFOA in adaptive speed. Results indicate that the present approach deals well in severe Dynamic Optimization problems.
Characterization Of A Class Of Graphs Related To Pairs Of Disjoint Matchings
Venue: arXiv cs.DM 2007
Year: 2007

For a given graph consider a pair of disjoint matchings the union of which contains as many edges as possible. Furthermore, consider the relation of the cardinalities of a maximum matching and the largest matching in those pairs. It is known that this relation does not exceed 5/4 for any graph. We characterize the class of graphs for which this relation is precisely 5/4. Our characterization implies that these graphs contain a spanning subgraph, every component of which is the minimal graph of this class.
Transactional WaveCache: Towards Speculative and Out-of-Order DataFlow Execution of Memory Operations
Venue: arXiv cs.AR 2007
Year: 2007

The WaveScalar is the first DataFlow Architecture that can efficiently provide the sequential memory semantics required by imperative languages. This work presents an alternative memory ordering mechanism for this architecture, the Transaction WaveCache. Our mechanism maintains the execution order of memory operations within blocks of code, called Waves, but adds the ability to speculatively execute, out-of-order, operations from different waves. This ordering mechanism is inspired by progress in supporting Transactional Memories. Waves are considered as atomic regions and executed as nested transactions. If a wave has finished the execution of all its memory operations, as soon as the previous waves are committed, it can be committed. If a hazard is detected in a speculative Wave, all the following Waves (children) are aborted and re-executed. We evaluate the WaveCache on a set artificial benchmarks. If the benchmark does not access memory often, we could achieve speedups of around 90%. Speedups of 33.1% and 24% were observed on more memory intensive applications, and slowdowns up to 16% arise if memory bandwidth is a bottleneck. For an application full of WAW, WAR and RAW hazards, a speedup of 139.7% was verified.
Joint Receiver and Transmitter Optimization for Energy-Efficient CDMA Communications
Venue: arXiv cs.IT 2007
Year: 2007

This paper focuses on the cross-layer issue of joint multiuser detection and resource allocation for energy efficiency in wireless CDMA networks. In particular, assuming that a linear multiuser detector is adopted in the uplink receiver, the case considered is that in which each terminal is allowed to vary its transmit power, spreading code, and uplink receiver in order to maximize its own utility, which is defined as the ratio of data throughput to transmit power. Resorting to a game-theoretic formulation, a non-cooperative game for utility maximization is formulated, and it is proved that a unique Nash equilibrium exists, which, under certain conditions, is also Pareto-optimal. Theoretical results concerning the relationship between the problems of SINR maximization and MSE minimization are given, and, resorting to the tools of large system analysis, a new distributed power control algorithm is implemented, based on very little prior information about the user of interest. The utility profile achieved by the active users in a large CDMA system is also computed, and, moreover, the centralized socially optimum solution is analyzed. Considerations on the extension of the proposed framework to a multi-cell scenario are also briefly detailed. Simulation results confirm that the proposed non-cooperative game largely outperforms competing alternatives, and that it exhibits a quite small performance loss with respect to the socially optimum solution, and only in the case in which the users number exceeds the processing gain. Finally, results also show an excellent agreement between the theoretical closed-form formulas based on large system analysis and the outcome of numerical experiments.
Borel Ranks and Wadge Degrees of Context Free Omega Languages
Venue: arXiv cs.LO 2007
Year: 2007

We show that, from a topological point of view, considering the Borel and the Wadge hierarchies, 1-counter Büchi automata have the same accepting power than Turing machines equipped with a Büchi acceptance condition. In particular, for every non null recursive ordinal alpha, there exist some Sigma^0_alpha-complete and some Pi^0_alpha-complete omega context free languages accepted by 1-counter Büchi automata, and the supremum of the set of Borel ranks of context free omega languages is the ordinal gamma^1_2 which is strictly greater than the first non recursive ordinal. This very surprising result gives answers to questions of H. Lescow and W. Thomas [Logical Specifications of Infinite Computations, In:"A Decade of Concurrency", LNCS 803, Springer, 1994, p. 583-621].
Graphs and Path Equilibria
Venue: arXiv cs.GT 2007
Year: 2007

The quest for optimal/stable paths in graphs has gained attention in a few practical or theoretical areas. To take part in this quest this chapter adopts an equilibrium-oriented approach that is abstract and general: it works with (quasi-arbitrary) arc-labelled digraphs, and it assumes very little about the structure of the sought paths and the definition of equilibrium, \textit{i.e.} optimality/stability. In this setting, this chapter presents a sufficient condition for equilibrium existence for every graph; it also presents a necessary condition for equilibrium existence for every graph. The necessary condition does not imply the sufficient condition a priori. However, the chapter pinpoints their logical difference and thus identifies what work remains to be done. Moreover, the necessary and the sufficient conditions coincide when the definition of optimality relates to a total order, which provides a full-equivalence property. These results are applied to network routing.
Ontology and Formal Semantics - Integration Overdue
Venue: arXiv cs.AI 2007
Year: 2007

In this note we suggest that difficulties encountered in natural language semantics are, for the most part, due to the use of mere symbol manipulation systems that are devoid of any content. In such systems, where there is hardly any link with our common-sense view of the world, and it is quite difficult to envision how one can formally account for the considerable amount of content that is often implicit, but almost never explicitly stated in our everyday discourse. The solution, in our opinion, is a compositional semantics grounded in an ontology that reflects our commonsense view of the world and the way we talk about it in ordinary language. In the compositional logic we envision there are ontological (or first-intension) concepts, and logical (or second-intension) concepts, and where the ontological concepts include not only Davidsonian events, but other abstract objects as well (e.g., states, processes, properties, activities, attributes, etc.) It will be demonstrated here that in such a framework, a number of challenges in the semantics of natural language (e.g., metonymy, intensionality, metaphor, etc.) can be properly and uniformly addressed.
Tournament MAC with Constant Size Congestion Window for WLAN
Venue: arXiv cs.NI 2007
Year: 2007

In the context of radio distributed networks, we present a generalized approach for the Medium Access Control (MAC) with fixed congestion window. Our protocol is quite simple to analyze and can be used in a lot of different situations. We give mathematical evidence showing that our performance is tight, in the sense that no protocol with fixed congestion window can do better. We also place ourselves in the WiFi/WiMAX framework, and show experimental results enlightening collision reduction of 14% to 21% compared to the best known other methods. We show channel capacity improvement, and fairness considerations.
Back-of-the-Envelope Computation of Throughput Distributions in CSMA Wireless Networks
Venue: arXiv cs.NI 2007
Year: 2007

This work started out with our accidental discovery of a pattern of throughput distributions among links in IEEE 802.11 networks from experimental results. This pattern gives rise to an easy computation method, which we term back-of-the-envelop (BoE) computation, because for many network configurations, very accurate results can be obtained within minutes, if not seconds, by simple hand computation. BoE beats prior methods in terms of both speed and accuracy. While the computation procedure of BoE is simple, explaining why it works is by no means trivial. Indeed the majority of our investigative efforts have been devoted to the construction of a theory to explain BoE. This paper models an ideal CSMA network as a set of interacting on-off telegraph processes. In developing the theory, we discovered a number of analytical techniques and observations that have eluded prior research, such as that the carrier-sensing interactions among links in an ideal CSMA network result in a system state evolution that is time-reversible; and that the probability distribution of the system state is insensitive to the distributions of the "on" and "off" durations given their means, and is a Markov random field. We believe these theoretical frameworks are useful not just for explaining BoE, but could also be a foundation for a fundamental understanding of how links in CSMA networks interact. Last but not least, because of their basic nature, we surmise that some of the techniques and results developed in this paper may be applicable to not just CSMA networks, but also to other physical and engineering systems consisting of entities interacting with each other in time and space.
Constructing Bio-molecular Databases on a DNA-based Computer
Venue: arXiv cs.NE 2007
Year: 2007

Codd [Codd 1970] wrote the first paper in which the model of a relational database was proposed. Adleman [Adleman 1994] wrote the first paper in which DNA strands in a test tube were used to solve an instance of the Hamiltonian path problem. From [Adleman 1994], it is obviously indicated that for storing information in molecules of DNA allows for an information density of approximately 1 bit per cubic nm (nanometer) and a dramatic improvement over existing storage media such as video tape which store information at a density of approximately 1 bit per 1012 cubic nanometers. This paper demonstrates that biological operations can be applied to construct bio-molecular databases where data records in relational tables are encoded as DNA strands. In order to achieve the goal, DNA algorithms are proposed to perform eight operations of relational algebra (calculus) on bio-molecular relational databases, which include Cartesian product, union, set difference, selection, projection, intersection, join and division. Furthermore, this work presents clear evidence of the ability of molecular computing to perform data retrieval operations on bio-molecular relational databases.
A New Outer Bound and the Noisy-Interference Sum-Rate Capacity for Gaussian Interference Channels
Venue: arXiv cs.IT 2007
Year: 2007

A new outer bound on the capacity region of Gaussian interference channels is developed. The bound combines and improves existing genie-aided methods and is shown to give the sum-rate capacity for noisy interference as defined in this paper. Specifically, it is shown that if the channel coefficients and power constraints satisfy a simple condition then single-user detection at each receiver is sum-rate optimal, i.e., treating the interference as noise incurs no loss in performance. This is the first concrete (finite signal-to-noise ratio) capacity result for the Gaussian interference channel with weak to moderate interference. Furthermore, for certain mixed (weak and strong) interference scenarios, the new outer bounds give a corner point of the capacity region.
An axiomatic approach to intrinsic dimension of a dataset
Venue: arXiv cs.IR 2007
Year: 2007

We perform a deeper analysis of an axiomatic approach to the concept of intrinsic dimension of a dataset proposed by us in the IJCNN'07 paper (arXiv:cs/0703125). The main features of our approach are that a high intrinsic dimension of a dataset reflects the presence of the curse of dimensionality (in a certain mathematically precise sense), and that dimension of a discrete i.i.d. sample of a low-dimensional manifold is, with high probability, close to that of the manifold. At the same time, the intrinsic dimension of a sample is easily corrupted by moderate high-dimensional noise (of the same amplitude as the size of the manifold) and suffers from prohibitevely high computational complexity (computing it is an $NP$-complete problem). We outline a possible way to overcome these difficulties.