OpenRaiser/Intern-Atlas huggingface dataset:
Documenting Spreadsheets with Pseudo-Code: an Exercise with Cash-Flow and Loans
Venue: arXiv cs.SE 2009
Year: 2009

"Look before you leap"; "a stitch in time saves nine"; "more haste, less speed". Many proverbs declare the wisdom of planning before doing. We suggest how to apply this to Excel, by explaining and specifying spreadsheets before coding them, so there will always be documentation for auditors and maintenance programmers. The specification method uses "pseudo-code": code that, for precision and conciseness, resembles a programming language, but is not executable. It is, however, based on the notation used by our Excelsior spreadsheet generator, which is executable. This paper is structured as a tutorial, in which we develop a simple cash-flow and loans spreadsheet.
Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut
Venue: arXiv cs.DS 2009
Year: 2009

This paper ties the line of work on algorithms that find an O(sqrt(log(n)))-approximation to the sparsest cut together with the line of work on algorithms that run in sub-quadratic time by using only single-commodity flows. We present an algorithm that simultaneously achieves both goals, finding an O(sqrt(log(n)/eps))-approximation using O(n^eps log^O(1) n) max-flows. The core of the algorithm is a stronger, algorithmic version of Arora et al.'s structure theorem, where we show that matching-chaining argument at the heart of their proof can be viewed as an algorithm that finds good augmenting paths in certain geometric multicommodity flow networks. By using that specialized algorithm in place of a black-box solver, we are able to solve those instances much more efficiently. We also show the cut-matching game framework can not achieve an approximation any better than Omega(log(n)/log log(n)) without re-routing flow.
From error detection to behaviour observation: first results from screen capture analysis
Venue: arXiv cs.HC 2009
Year: 2009

This paper deals with errors in using spreadsheets and analysis of automatic recording of user interaction with spreadsheets. After a review of literature devoted to spreadsheet errors, we advocate the importance of going from error detection to interaction behaviour analysis. We explain how we analyze screen captures and give the main results we have obtained using this specific methodology with secondary school students (N=24). Transcription provides general characteristics: time, sequence of performed tasks, unsuccessful attempts and user preferences. Analysis reveals preferred modes of actions (toolbar buttons or menu commands), ways of writing formulas, and typical approaches in searching for solutions. Time, rhythm and density appear to be promising indicators. We think such an approach (to analyze screen captures) could be used with more advanced spreadsheet users.
A dyadic solution of relative pose problems
Venue: arXiv cs.CV 2009
Year: 2009

A hierarchical interval subdivision is shown to lead to a $p$-adic encoding of image data. This allows in the case of the relative pose problem in computer vision and photogrammetry to derive equations having 2-adic numbers as coefficients, and to use Hensel's lifting method to their solution. This method is applied to the linear and non-linear equations coming from eight, seven or five point correspondences. An inherent property of the method is its robustness.
On P vs. NP, Geometric Complexity Theory, Explicit Proofs and the Complexity Barrier
Venue: arXiv cs.CC 2009
Year: 2009

Geometric complexity theory (GCT) is an approach to the P vs. NP and related problems. This article gives its complexity theoretic overview without assuming any background in algebraic geometry or representation theory.
Untangling the Web of E-Research: Towards a Sociology of Online Knowledge
Venue: arXiv cs.CY 2009
Year: 2009

e-Research is a rapidly growing research area, both in terms of publications and in terms of funding. In this article we argue that it is necessary to reconceptualize the ways in which we seek to measure and understand e-Research by developing a sociology of knowledge based on our understanding of how science has been transformed historically and shifted into online forms. Next, we report data which allows the examination of e-Research through a variety of traces in order to begin to understand how the knowledge in the realm of e-Research has been and is being constructed. These data indicate that e-Research has had a variable impact in different fields of research. We argue that only an overall account of the scale and scope of e-Research within and between different fields makes it possible to identify the organizational coherence and diffuseness of e-Research in terms of its socio-technical networks, and thus to identify the contributions of e-Research to various research fronts in the online production of knowledge.
Transaction-Oriented Simulation In Ad Hoc Grids: Design and Experience
Venue: arXiv cs.DC 2009
Year: 2009

In this paper we analyse the requirements of performing parallel transaction-oriented simulations within loosely coupled systems like ad hoc grids. We focus especially on the space-parallel approach to parallel simulation and on discrete event synchronisation algorithms that are suitable for transaction-oriented simulation and the target environment of ad hoc grids. To demonstrate our findings, a Java-based parallel simulator for the transaction-oriented language GPSS/H is implemented on the basis of the most promising shock-resistant Time Warp (SRTW) synchronisation algorithm and using the grid framework ProActive. The analysis of our parallel simulator, based on experiments using the Grid5000 platform, shows that the SRTW algorithm can successfully reduce the number of rolled back transaction moves but it also reveals circumstances in which the SRTW algorithm can be outperformed by the normal Time Warp algorithm. Finally, possible improvements to the SRTW algorithm are proposed in order to avoid such problems.
Two Algorithms for Network Size Estimation for Master/Slave Ad Hoc Networks
Venue: arXiv cs.NI 2009
Year: 2009

This paper proposes an adaptation of two network size estimation methods: random tour and gossip-based aggregation to suit master/slave mobile ad hoc networks. We show that it is feasible to accurately estimate the size of ad hoc networks when topology changes due to mobility using both methods. The algorithms were modified to account for the specific constraints of master/slave ad hoc networks and the results show that the proposed modifications perform better on these networks than the original protocols. Each of the two algorithms presents strengths and weaknesses and these are outlined in this paper.
Acyclic Edge coloring of Planar Graphs
Venue: arXiv cs.DM 2009
Year: 2009

An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The \emph{acyclic chromatic index} of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by $a'(G)$. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that $a'(G)\le Δ+2$, where $Δ=Δ(G)$ denotes the maximum degree of the graph. We prove that if $G$ is a planar graph with maximum degree $Δ$, then $a'(G)\le Δ+ 12$.
A Channel Coding Perspective of Collaborative Filtering
Venue: arXiv cs.IT 2009
Year: 2009

We consider the problem of collaborative filtering from a channel coding perspective. We model the underlying rating matrix as a finite alphabet matrix with block constant structure. The observations are obtained from this underlying matrix through a discrete memoryless channel with a noisy part representing noisy user behavior and an erasure part representing missing data. Moreover, the clusters over which the underlying matrix is constant are {\it unknown}. We establish a sharp threshold result for this model: if the largest cluster size is smaller than $C_1 \log(mn)$ (where the rating matrix is of size $m \times n$), then the underlying matrix cannot be recovered with any estimator, but if the smallest cluster size is larger than $C_2 \log(mn)$, then we show a polynomial time estimator with diminishing probability of error. In the case of uniform cluster size, not only the order of the threshold, but also the constant is identified.
New method to characterize a machining system: application in turning
Venue: arXiv cs.CE 2009
Year: 2009

Many studies simulates the machining process by using a single degree of freedom spring-mass sytem to model the tool stiffness, or the workpiece stiffness, or the unit tool-workpiece stiffness in modelings 2D. Others impose the tool action, or use more or less complex modelings of the efforts applied by the tool taking account the tool geometry. Thus, all these models remain two-dimensional or sometimes partially three-dimensional. This paper aims at developing an experimental method allowing to determine accurately the real three-dimensional behaviour of a machining system (machine tool, cutting tool, tool-holder and associated system of force metrology six-component dynamometer). In the work-space model of machining, a new experimental procedure is implemented to determine the machining system elastic behaviour. An experimental study of machining system is presented. We propose a machining system static characterization. A decomposition in two distinct blocks of the system "Workpiece-Tool-Machine" is realized. The block Tool and the block Workpiece are studied and characterized separately by matrix stiffness and displacement (three translations and three rotations). The Castigliano's theory allows us to calculate the total stiffness matrix and the total displacement matrix. A stiffness center point and a plan of tool tip static displacement are presented in agreement with the turning machining dynamic model and especially during the self induced vibration. These results are necessary to have a good three-dimensional machining system dynamic characterization.
XTile: An Error-Correction Package for DNA Self-Assembly
Venue: arXiv cs.IT 2009
Year: 2009

Self assembly is a process by which supramolecular species form spontaneously from their components. This process is ubiquitous throughout the life chemistry and is central to biological information processing. It has been predicted that in future self assembly will become an important engineering discipline by combining the fields of bio molecular computation, nano technology and medicine. However error control is a key challenge in realizing the potential of self assembly. Recently many authors have proposed several combinatorial error correction schemes to control errors which have a close analogy with the coding theory such as Winfree s proofreading scheme and its generalizations by Chen and Goel and compact scheme of Reif, Sahu and Yin. In this work, we present an error correction computational tool XTile that can be used to create input files to the Xgrow simulator of Winfree by providing the design logic of the tiles and it also allows the user to apply proofreading, snake and compact error correction schemes.
The Single Source Two Terminal Network with Network Coding
Venue: arXiv cs.IT 2009
Year: 2009

We consider a communication network with a single source that has a set of messages and two terminals where each terminal is interested in an arbitrary subset of messages at the source. A tight capacity region for this problem is demonstrated. We show by a simple graph-theoretic procedure that any such problem can be solved by performing network coding on the subset of messages that are requested by both the terminals and that routing is sufficient for transferring the remaining messages.
Throughput of Cellular Uplink with Dynamic User Activity and Cooperative Base-Stations
Venue: arXiv cs.IT 2009
Year: 2009

The throughput of a linear cellular uplink with a random number of users, different power control schemes, and cooperative base stations is considered in the large system limit where the number of cells is large for non fading Gaussian channels. The analysis is facilitated by establishing an analogy between the cellular channel per-cell throughput with joint multi-cell processing (MCP), and the rate of a deterministic inter-symbol interference (ISI) channel with flat fading. It is shown that, under certain conditions, the dynamics of cellular systems (i.e., a random number of users coupled with a given power control scheme) can be interpreted, as far as the uplink throughput is concerned, as the flat fading process of the equivalent ISI channel. The results are used to demonstrate the benefits of MCP over the conventional single cell processing approach as a function of various system parameters in the presence of random user activity.
Location of Single Neuron Memories in a Hebbian Network
Venue: arXiv cs.NE 2009
Year: 2009

This paper reports the results of an experiment on the use of Kak's B-Matrix approach to spreading activity in a Hebbian neural network. Specifically, it concentrates on the memory retrieval from single neurons and compares the performance of the B-Matrix approach to that of the traditional approach.
Level Crossing Rate and Average Fade Duration of Dual Selection Combining with Cochannel Interference and Nakagami Fading
Venue: arXiv cs.IT 2009
Year: 2009

This letter provides closed-form expressions for the outage probability, the average level crossing rate (LCR) and the average fade duration (AFD) of a dual diversity selection combining (SC) system exposed to the combined influence of the cochannel interference (CCI) and the thermal noise (AWGN) in Nakagami fading channel. The branch selection is based on the desired signal power SC algorithm with all input signals assumed to be independent, while the powers of the desired signals in all diversity branches are mutually equal but distinct from the power of the interference signals. The analytical results reduce to known solutions in the cases of an interference-limited system in Rayleigh fading and an AWGN-limited system in Nakagami fading. The average LCR is determined by an original approach that does not require explicit knowledge of the joint PDF of the envelope and its time derivative, which also paves the way for similar analysis of other diversity systems.
Carnival of Samplings: Nets, Approximations, Relative and Sensitive
Venue: arXiv cs.CG 2009
Year: 2009

We survey several results known on sampling in computational geometry.
On the Exponentiation of Interval Matrices
Venue: arXiv cs.NA 2009
Year: 2009

The numerical computation of the exponentiation of a real matrix has been intensively studied. The main objective of a good numerical method is to deal with round-off errors and computational cost. The situation is more complicated when dealing with interval matrices exponentiation: Indeed, the main problem will now be the dependency loss of the different occurrences of the variables due to interval evaluation, which may lead to so wide enclosures that they are useless. In this paper, the problem of computing a sharp enclosure of the interval matrix exponential is proved to be NP-hard. Then the scaling and squaring method is adapted to interval matrices and shown to drastically reduce the dependency loss w.r.t. the interval evaluation of the Taylor series.
Recombinations of Busy Beaver Machines
Venue: arXiv cs.CC 2009
Year: 2009

Many programmers belive that Turing-based machines cannot think. We also believe in this, however it is interesting to note that the most sophisticated machines are not programmed by human beings. We have only discovered them. In this paper, using well-known Busy Beaver and Placid Platypus machines, we generate further very similar, but not exactly the same machines. We have found a recombinated BB_5 machine which can make 70.740.809 steps before halting.
Optimization of Bit Plane Combination for Efficient Digital Image Watermarking
Venue: arXiv cs.CR 2009
Year: 2009

In view of the frequent multimedia data transfer authentication and protection of images has gained importance in todays world. In this paper we propose a new watermarking technique, based on bit plane, which enhances robustness and capacity of the watermark, as well as maintains transparency of the watermark and fidelity of the image. In the proposed technique, higher strength bit plane of digital signature watermark is embedded in to a significant bit plane of the original image. The combination of bit planes (image and watermark) selection is an important issue. Therefore, a mechanism is developed for appropriate bit plane selection. Ten different attacks are selected to test different alternatives. These attacks are given different weightings as appropriate to user requirement. A weighted correlation coefficient for retrieved watermark is estimated for each of the alternatives. Based on these estimated values optimal bit plane combination is identified for a given user requirement. The proposed method is found to be useful for authentication and to prove legal ownership. We observed better results by our proposed method in comparison with the previously reported work on pseudorandom watermark embedded in least significant bit (LSB) plane.
Bridging the Gap between Crisis Response Operations and Systems
Venue: arXiv cs.CY 2009
Year: 2009

There exist huge problems in the current practice of crisis response operations. Response problems are projected as a combination of failure in communication, failure in technology, failure in methodology, failure of management, and finally failure of observation. In this paper we compare eight crisis response systems namely: DrillSim [2, 13], DEFACTO [12, 17], ALADDIN [1, 6], RoboCup Rescue [11, 15], FireGrid [3, 8, 18], WIPER [16], D-AESOP [4], and PLAN C [14]. Comparison results will disclose the cause of failure of current crisis response operations (the response gap). Based on comparison results; we provide recommendations for bridging this gap between response operations and systems.
Handwritten Farsi Character Recognition using Artificial Neural Network
Venue: arXiv cs.CV 2009
Year: 2009

Neural Networks are being used for character recognition from last many years but most of the work was confined to English character recognition. Till date, a very little work has been reported for Handwritten Farsi Character recognition. In this paper, we have made an attempt to recognize handwritten Farsi characters by using a multilayer perceptron with one hidden layer. The error backpropagation algorithm has been used to train the MLP network. In addition, an analysis has been carried out to determine the number of hidden nodes to achieve high performance of backpropagation network in the recognition of handwritten Farsi characters. The system has been trained using several different forms of handwriting provided by both male and female participants of different age groups. Finally, this rigorous training results an automatic HCR system using MLP network. In this work, the experiments were carried out on two hundred fifty samples of five writers. The results showed that the MLP networks trained by the error backpropagation algorithm are superior in recognition accuracy and memory usage. The result indicates that the backpropagation network provides good recognition accuracy of more than 80% of handwritten Farsi characters.
Spreadsheets and the Financial Collapse
Venue: arXiv cs.CY 2009
Year: 2009

We briefly review the well-known risks, weaknesses and limitations of spreadsheets and then introduce some more. We review and slightly extend our previous work on the importance and criticality of spreadsheets in the City of London, introducing the notions of ubiquity, centrality, legality and contagion. We identify the sector of the financial market that we believed in 2005 to be highly dependant on the use of spreadsheets and relate this to its recent catastrophic financial performance. We outline the role of spreadsheets in the collapse of the Jamaican banking system in the late 1990's and then review the UK financial regulator's knowledge of the risks of spreadsheets in the contemporary financial system. We summarise the available evidence and suggest that there is a link between the use of spreadsheets and the recent collapse of the global financial system. We provide governments and regulating authorities with some simple recommendations to reduce the risks of continued overdependence on unreliable spreadsheets. We conclude with three fundamental lessons from a century of human error research.
Asymptotic Equipartition Property of Output when Rate is above Capacity
Venue: arXiv cs.IT 2009
Year: 2009

The output distribution, when rate is above capacity, is investigated. It is shown that there is an asymptotic equipartition property (AEP) of the typical output sequences, independently of the specific codebook used, as long as the codebook is typical according to the standard random codebook generation. This equipartition of the typical output sequences is caused by the mixup of input sequences when there are too many of them, namely, when the rate is above capacity. This discovery sheds some light on the optimal design of the compress-and-forward relay schemes.
Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas
Venue: arXiv cs.CC 2009
Year: 2009

We show lower bounds of $Ω(\sqrt{n})$ and $Ω(n^{1/4})$ on the randomized and quantum communication complexity, respectively, of all $n$-variable read-once Boolean formulas. Our results complement the recent lower bound of $Ω(n/8^d)$ by Leonardos and Saks and $Ω(n/2^{Ω(d\log d)})$ by Jayram, Kopparty and Raghavendra for randomized communication complexity of read-once Boolean formulas with depth $d$. We obtain our result by "embedding" either the Disjointness problem or its complement in any given read-once Boolean formula.
The eel-like robot
Venue: arXiv cs.RO 2009
Year: 2009

The aim of this project is to design, study and build an "eel-like robot" prototype able to swim in three dimensions. The study is based on the analysis of eel swimming and results in the realization of a prototype with 12 vertebrae, a skin and a head with two fins. To reach these objectives, a multidisciplinary group of teams and laboratories has been formed in the framework of two French projects.
A Computational View of Market Efficiency
Venue: arXiv cs.CE 2009
Year: 2009

We propose to study market efficiency from a computational viewpoint. Borrowing from theoretical computer science, we define a market to be \emph{efficient with respect to resources $S$} (e.g., time, memory) if no strategy using resources $S$ can make a profit. As a first step, we consider memory-$m$ strategies whose action at time $t$ depends only on the $m$ previous observations at times $t-m,...,t-1$. We introduce and study a simple model of market evolution, where strategies impact the market by their decision to buy or sell. We show that the effect of optimal strategies using memory $m$ can lead to "market conditions" that were not present initially, such as (1) market bubbles and (2) the possibility for a strategy using memory $m' > m$ to make a bigger profit than was initially possible. We suggest ours as a framework to rationalize the technological arms race of quantitative trading firms.
On the optimal design of parallel robots taking into account their deformations and natural frequencies
Venue: arXiv cs.RO 2009
Year: 2009

This paper discusses the utility of using simple stiffness and vibrations models, based on the Jacobian matrix of a manipulator and only the rigidity of the actuators, whenever its geometry is optimised. In many works, these simplified models are used to propose optimal design of robots. However, the elasticity of the drive system is often negligible in comparison with the elasticity of the elements, especially in applications where high dynamic performances are needed. Therefore, the use of such a simplified model may lead to the creation of robots with long legs, which will be submitted to large bending and twisting deformations. This paper presents an example of manipulator for which it is preferable to use a complete stiffness or vibration model to obtain the most suitable design and shows that the use of simplified models can lead to mechanisms with poorer rigidity.