OpenRaiser/Intern-Atlas huggingface dataset:
Lissom, a Source Level Proof Carrying Code Platform
Venue: arXiv cs.LO 2008
Year: 2008

This paper introduces a proposal for a Proof Carrying Code (PCC) architecture called Lissom. Started as a challenge for final year Computing students, Lissom was thought as a mean to prove to a sceptic community, and in particular to students, that formal verification tools can be put to practice in a realistic environment, and be used to solve complex and concrete problems. The attractiveness of the problems that PCC addresses has already brought students to show interest in this project.
Combined Intra- and Inter-domain Traffic Engineering using Hot-Potato Aware Link Weights Optimization
Venue: arXiv cs.NI 2008
Year: 2008

A well-known approach to intradomain traffic engineering consists in finding the set of link weights that minimizes a network-wide objective function for a given intradomain traffic matrix. This approach is inadequate because it ignores a potential impact on interdomain routing. Indeed, the resulting set of link weights may trigger BGP to change the BGP next hop for some destination prefixes, to enforce hot-potato routing policies. In turn, this results in changes in the intradomain traffic matrix that have not been anticipated by the link weights optimizer, possibly leading to degraded network performance. We propose a BGP-aware link weights optimization method that takes these effects into account, and even turns them into an advantage. This method uses the interdomain traffic matrix and other available BGP data, to extend the intradomain topology with external virtual nodes and links, on which all the well-tuned heuristics of a classical link weights optimizer can be applied. A key innovative asset of our method is its ability to also optimize the traffic on the interdomain peering links. We show, using an operational network as a case study, that our approach does so efficiently at almost no extra computational cost.
Impact of CSI on Distributed Space-Time Coding in Wireless Relay Networks
Venue: arXiv cs.IT 2008
Year: 2008

We consider a two-hop wireless network where a transmitter communicates with a receiver via $M$ relays with an amplify-and-forward (AF) protocol. Recent works have shown that sophisticated linear processing such as beamforming and distributed space-time coding (DSTC) at relays enables to improve the AF performance. However, the relative utility of these strategies depend on the available channel state information at transmitter (CSIT), which in turn depends on system parameters such as the speed of the underlying fading channel and that of training and feedback procedures. Moreover, it is of practical interest to have a single transmit scheme that handles different CSIT scenarios. This motivates us to consider a unified approach based on DSTC that potentially provides diversity gain with statistical CSIT and exploits some additional side information if available. Under individual power constraints at the relays, we optimize the amplifier power allocation such that pairwise error probability conditioned on the available CSIT is minimized. Under perfect CSIT we propose an on-off gradient algorithm that efficiently finds a set of relays to switch on. Under partial and statistical CSIT, we propose a simple waterfilling algorithm that yields a non-trivial solution between maximum power allocation and a generalized STC that equalizes the averaged amplified noise for all relays. Moreover, we derive closed-form solutions for M=2 and in certain asymptotic regimes that enable an easy interpretation of the proposed algorithms. It is found that an appropriate amplifier power allocation is mandatory for DSTC to offer sufficient diversity and power gain in a general network topology.
Equivalence of Probabilistic Tournament and Polynomial Ranking Selection
Venue: arXiv cs.NE 2008
Year: 2008

Crucial to an Evolutionary Algorithm's performance is its selection scheme. We mathematically investigate the relation between polynomial rank and probabilistic tournament methods which are (respectively) generalisations of the popular linear ranking and tournament selection schemes. We show that every probabilistic tournament is equivalent to a unique polynomial rank scheme. In fact, we derived explicit operators for translating between these two types of selection. Of particular importance is that most linear and most practical quadratic rank schemes are probabilistic tournaments.
The Role of Management Practices in Closing the Productivity Gap
Venue: arXiv cs.OH 2008
Year: 2008

There is no doubt that management practices are linked to the productivity and performance of a company. However, research findings are mixed. This paper provides a multi-disciplinary review of the current evidence of such a relationship and offers suggestions for further exploration. We provide an extensive review of the literature in terms of research findings from studies that have been trying to measure and understand the impact that individual management practices and clusters of management practices have on productivity at different levels of analysis. We focus our review on Operations Management (om) and Human Resource Management (hrm) practices as well as joint applications of these practices. In conclusion, we can say that taken as a whole, the research findings are equivocal. Some studies have found a positive relationship between the adoption of management practices and productivity, some negative and some no association whatsoever. We believe that the lack of universal consensus on the effect of the adoption of complementary management practices might be driven either by measurement issues or by the level of analysis. Consequently, there is a need for further research. In particular, for a multi-level approach from the lowest possible level of aggregation up to the firm-level of analysis in order to assess the impact of management practices upon the productivity of firms.
Towards a human eye behavior model by applying Data Mining Techniques on Gaze Information from IEC
Venue: arXiv cs.HC 2008
Year: 2008

In this paper, we firstly present what is Interactive Evolutionary Computation (IEC) and rapidly how we have combined this artificial intelligence technique with an eye-tracker for visual optimization. Next, in order to correctly parameterize our application, we present results from applying data mining techniques on gaze information coming from experiments conducted on about 80 human individuals.
Archiving: The Overlooked Spreadsheet Risk
Venue: arXiv cs.SE 2008
Year: 2008

This paper maintains that archiving has been overlooked as a key spreadsheet internal control. The case of failed Jamaican commercial banks demonstrates how poor archiving can lead to weaknesses in spreadsheet control that contribute to operational risk. In addition, the Sarbanes-0xley Act contains a number of provisions that require tighter control over the archiving of spreadsheets. To mitigate operational risks and achieve compliance with the records-related provisions of Sarbanes-Oxley, the author argues that organisations should introduce records management programmes that provide control over the archiving of spreadsheets. At a minimum, spreadsheet archiving controls should identify and ensure compliance with retention requirements, support document production in the event of regulatory inquiries or litigation, and prevent unauthorised destruction of records.
Capacity of Gaussian MIMO Bidirectional Broadcast Channels
Venue: arXiv cs.IT 2008
Year: 2008

We consider the broadcast phase of a three-node network, where a relay node establishes a bidirectional communication between two nodes using a spectrally efficient two-phase decode-and-forward protocol. In the first phase the two nodes transmit their messages to the relay node. Then the relay node decodes the messages and broadcasts a re-encoded composition of them in the second phase. We consider Gaussian MIMO channels and determine the capacity region for the second phase which we call the Gaussian MIMO bidirectional broadcast channel.
Combinatorial Explorations in Su-Doku
Venue: arXiv cs.AI 2008
Year: 2008

Su-Doku, a popular combinatorial puzzle, provides an excellent testbench for heuristic explorations. Several interesting questions arise from its deceptively simple set of rules. How many distinct Su-Doku grids are there? How to find a solution to a Su-Doku puzzle? Is there a unique solution to a given Su-Doku puzzle? What is a good estimation of a puzzle's difficulty? What is the minimum puzzle size (the number of "givens")? This paper explores how these questions are related to the well-known alldifferent constraint which emerges in a wide variety of Constraint Satisfaction Problems (CSP) and compares various algorithmic approaches based on different formulations of Su-Doku.
On the reconstruction of block-sparse signals with an optimal number of measurements
Venue: arXiv cs.IT 2008
Year: 2008

Let A be an M by N matrix (M < N) which is an instance of a real random Gaussian ensemble. In compressed sensing we are interested in finding the sparsest solution to the system of equations A x = y for a given y. In general, whenever the sparsity of x is smaller than half the dimension of y then with overwhelming probability over A the sparsest solution is unique and can be found by an exhaustive search over x with an exponential time complexity for any y. The recent work of Candés, Donoho, and Tao shows that minimization of the L_1 norm of x subject to A x = y results in the sparsest solution provided the sparsity of x, say K, is smaller than a certain threshold for a given number of measurements. Specifically, if the dimension of y approaches the dimension of x, the sparsity of x should be K < 0.239 N. Here, we consider the case where x is d-block sparse, i.e., x consists of n = N / d blocks where each block is either a zero vector or a nonzero vector. Instead of L_1-norm relaxation, we consider the following relaxation min x \| X_1 \|_2 + \| X_2 \|_2 + ... + \| X_n \|_2, subject to A x = y where X_i = (x_{(i-1)d+1}, x_{(i-1)d+2}, ..., x_{i d}) for i = 1,2, ..., N. Our main result is that as n -> \infty, the minimization finds the sparsest solution to Ax = y, with overwhelming probability in A, for any x whose block sparsity is k/n < 1/2 - O(ε), provided M/N > 1 - 1/d, and d = Ω(\log(1/ε)/ε). The relaxation can be solved in polynomial time using semi-definite programming.
Mapping Semantic Networks to Undirected Networks
Venue: arXiv cs.DS 2008
Year: 2008

There exists an injective, information-preserving function that maps a semantic network (i.e a directed labeled network) to a directed network (i.e. a directed unlabeled network). The edge label in the semantic network is represented as a topological feature of the directed network. Also, there exists an injective function that maps a directed network to an undirected network (i.e. an undirected unlabeled network). The edge directionality in the directed network is represented as a topological feature of the undirected network. Through function composition, there exists an injective function that maps a semantic network to an undirected network. Thus, aside from space constraints, the semantic network construct does not have any modeling functionality that is not possible with either a directed or undirected network representation. Two proofs of this idea will be presented. The first is a proof of the aforementioned function composition concept. The second is a simpler proof involving an undirected binary encoding of a semantic network.
Joint Beamforming for Multiaccess MIMO Systems with Finite Rate Feedback
Venue: arXiv cs.IT 2008
Year: 2008

This paper considers multiaccess multiple-input multiple-output (MIMO) systems with finite rate feedback. The goal is to understand how to efficiently employ the given finite feedback resource to maximize the sum rate by characterizing the performance analytically. Towards this, we propose a joint quantization and feedback strategy: the base station selects the strongest users, jointly quantizes their strongest eigen-channel vectors and broadcasts a common feedback to all the users. This joint strategy is different from an individual strategy, in which quantization and feedback are performed across users independently, and it improves upon the individual strategy in the same way that vector quantization improves upon scalar quantization. In our proposed strategy, the effect of user selection is analyzed by extreme order statistics, while the effect of joint quantization is quantified by what we term ``the composite Grassmann manifold''. The achievable sum rate is then estimated by random matrix theory. Due to its simple implementation and solid performance analysis, the proposed scheme provides a benchmark for multiaccess MIMO systems with finite rate feedback.
Realistic Haptic Rendering of Interacting Deformable Objects in Virtual Environments
Venue: arXiv cs.GR 2008
Year: 2008

A new computer haptics algorithm to be used in general interactive manipulations of deformable virtual objects is presented. In multimodal interactive simulations, haptic feedback computation often comes from contact forces. Subsequently, the fidelity of haptic rendering depends significantly on contact space modeling. Contact and friction laws between deformable models are often simplified in up to date methods. They do not allow a "realistic" rendering of the subtleties of contact space physical phenomena (such as slip and stick effects due to friction or mechanical coupling between contacts). In this paper, we use Signorini's contact law and Coulomb's friction law as a computer haptics basis. Real-time performance is made possible thanks to a linearization of the behavior in the contact space, formulated as the so-called Delassus operator, and iteratively solved by a Gauss-Seidel type algorithm. Dynamic deformation uses corotational global formulation to obtain the Delassus operator in which the mass and stiffness ratio are dissociated from the simulation time step. This last point is crucial to keep stable haptic feedback. This global approach has been packaged, implemented, and tested. Stable and realistic 6D haptic feedback is demonstrated through a clipping task experiment.
Computing a Finite Size Representation of the Set of Approximate Solutions of an MOP
Venue: arXiv cs.NA 2008
Year: 2008

Recently, a framework for the approximation of the entire set of $ε$-efficient solutions (denote by $E_ε$) of a multi-objective optimization problem with stochastic search algorithms has been proposed. It was proven that such an algorithm produces -- under mild assumptions on the process to generate new candidate solutions --a sequence of archives which converges to $E_ε$ in the limit and in the probabilistic sense. The result, though satisfactory for most discrete MOPs, is at least from the practical viewpoint not sufficient for continuous models: in this case, the set of approximate solutions typically forms an $n$-dimensional object, where $n$ denotes the dimension of the parameter space, and thus, it may come to perfomance problems since in practise one has to cope with a finite archive. Here we focus on obtaining finite and tight approximations of $E_ε$, the latter measured by the Hausdorff distance. We propose and investigate a novel archiving strategy theoretically and empirically. For this, we analyze the convergence behavior of the algorithm, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting approximation, and present some numerical results.
Spatial Interference Cancelation for Mobile Ad Hoc Networks: Perfect CSI
Venue: arXiv cs.IT 2008
Year: 2008

Interference between nodes directly limits the capacity of mobile ad hoc networks. This paper focuses on spatial interference cancelation with perfect channel state information (CSI), and analyzes the corresponding network capacity. Specifically, by using multiple antennas, zero-forcing beamforming is applied at each receiver for canceling the strongest interferers. Given spatial interference cancelation, the network transmission capacity is analyzed in this paper, which is defined as the maximum transmitting node density under constraints on outage and the signal-to-interference-noise ratio. Assuming the Poisson distribution for the locations of network nodes and spatially i.i.d. Rayleigh fading channels, mathematical tools from stochastic geometry are applied for deriving scaling laws for transmission capacity. Specifically, for small target outage probability, transmission capacity is proved to increase following a power law, where the exponent is the inverse of the size of antenna array or larger depending on the pass loss exponent. As shown by simulations, spatial interference cancelation increases transmission capacity by an order of magnitude or more even if only one extra antenna is added to each node.
On ad hoc routing with guaranteed delivery
Venue: arXiv cs.DC 2008
Year: 2008

We point out a simple poly-time log-space routing algorithm in ad hoc networks with guaranteed delivery using universal exploration sequences.
Cache-Oblivious Selection in Sorted X+Y Matrices
Venue: arXiv cs.DS 2008
Year: 2008

Let X[0..n-1] and Y[0..m-1] be two sorted arrays, and define the mxn matrix A by A[j][i]=X[i]+Y[j]. Frederickson and Johnson gave an efficient algorithm for selecting the k-th smallest element from A. We show how to make this algorithm IO-efficient. Our cache-oblivious algorithm performs O((m+n)/B) IOs, where B is the block size of memory transfers.
Reducing Overconfidence in Spreadsheet Development
Venue: arXiv cs.HC 2008
Year: 2008

Despite strong evidence of widespread errors, spreadsheet developers rarely subject their spreadsheets to post-development testing to reduce errors. This may be because spreadsheet developers are overconfident in the accuracy of their spreadsheets. This conjecture is plausible because overconfidence is present in a wide variety of human cognitive domains, even among experts. This paper describes two experiments in overconfidence in spreadsheet development. The first is a pilot study to determine the existence of overconfidence. The second tests a manipulation to reduce overconfidence and errors. The manipulation is modestly successful, indicating that overconfidence reduction is a promising avenue to pursue.
Cauchy's Arm Lemma on a Growing Sphere
Venue: arXiv cs.CG 2008
Year: 2008

We propose a variant of Cauchy's Lemma, proving that when a convex chain on one sphere is redrawn (with the same lengths and angles) on a larger sphere, the distance between its endpoints increases. The main focus of this work is a comparison of three alternate proofs, to show the links between Toponogov's Comparison Theorem, Legendre's Theorem and Cauchy's Arm Lemma.
Méthode de calcul du rayonnement acoustique de structures complexes
Venue: arXiv cs.CE 2008
Year: 2008

In the automotive industry, predicting noise during design cycle is a necessary step. Well-known methods exist to answer this issue in low frequency domain. Among these, Finite Element Methods, adapted to closed domains, are quite easy to implement whereas Boundary Element Methods are more adapted to infinite domains, but may induce singularity problems. In this article, the described method, the SDM, allows to use both methods in their best application domain. A new method is also presented to solve the SDM exterior problem. Instead of using Boundary Element Methods, an original use of Finite Elements is made. Efficiency of this new version of the Substructure Deletion Method is discussed.
Spreading Signals in the Wideband Limit
Venue: arXiv cs.IT 2008
Year: 2008

Wideband communications are impossible with signals that are spread over a very large band and are transmitted over multipath channels unknown ahead of time. This work exploits the I-mmse connection to bound the achievable data-rate of spreading signals in wideband settings, and to conclude that the achievable data-rate diminishes as the bandwidth increases due to channel uncertainty. The result applies to all spreading modulations, i.e. signals that are evenly spread over the bandwidth available to the communication system, with SNR smaller than log(W/L)/(W/L) and holds for communications over channels where the number of paths L is unbounded by sub-linear in the bandwidth W.
Nonextensive Generalizations of the Jensen-Shannon Divergence
Venue: arXiv cs.IT 2008
Year: 2008

Convexity is a key concept in information theory, namely via the many implications of Jensen's inequality, such as the non-negativity of the Kullback-Leibler divergence (KLD). Jensen's inequality also underlies the concept of Jensen-Shannon divergence (JSD), which is a symmetrized and smoothed version of the KLD. This paper introduces new JSD-type divergences, by extending its two building blocks: convexity and Shannon's entropy. In particular, a new concept of q-convexity is introduced and shown to satisfy a Jensen's q-inequality. Based on this Jensen's q-inequality, the Jensen-Tsallis q-difference is built, which is a nonextensive generalization of the JSD, based on Tsallis entropies. Finally, the Jensen-Tsallis q-difference is charaterized in terms of convexity and extrema.
Space-Time Codes from Structured Lattices
Venue: arXiv cs.IT 2008
Year: 2008

We present constructions of Space-Time (ST) codes based on lattice coset coding. First, we focus on ST code constructions for the short block-length case, i.e., when the block-length is equal to or slightly larger than the number of transmit antennas. We present constructions based on dense lattice packings and nested lattice (Voronoi) shaping. Our codes achieve the optimal diversity-multiplexing tradeoff of quasi-static MIMO fading channels for any fading statistics, and perform very well also at practical, moderate values of signal to noise ratios (SNR). Then, we extend the construction to the case of large block lengths, by using trellis coset coding. We provide constructions of trellis coded modulation (TCM) schemes that are endowed with good packing and shaping properties. Both short-block and trellis constructions allow for a reduced complexity decoding algorithm based on minimum mean squared error generalized decision feedback equalizer (MMSE-GDFE) lattice decoding and a combination of this with a Viterbi TCM decoder for the TCM case. Beyond the interesting algebraic structure, we exhibit codes whose performance is among the state-of-the art considering codes with similar encoding/decoding complexity.
A Security Protocol for Multi-User Authentication
Venue: arXiv cs.CR 2008
Year: 2008

In this note we propose an encryption communication protocol which also provides database security. For the encryption of the data communication we use a transformation similar to the Cubic Public-key transformation. This method represents a many-to-one mapping which increases the complexity for any brute force attack. Some interesting properties of the transformation are also included which are basic in the authentication protocol.
Towards Physarum robots: computing and manipulating on water surface
Venue: arXiv cs.RO 2008
Year: 2008

Plasmodium of Physarym polycephalum is an ideal biological substrate for implementing concurrent and parallel computation, including combinatorial geometry and optimization on graphs. We report results of scoping experiments on Physarum computing in conditions of minimal friction, on the water surface. We show that plasmodium of Physarum is capable for computing a basic spanning trees and manipulating of light-weight objects. We speculate that our results pave the pathways towards design and implementation of amorphous biological robots.