OpenRaiser/Intern-Atlas huggingface dataset:
Path placement optimization of manipulators based on energy consumption: application to the orthoglide 3-axis
Venue: arXiv cs.RO 2009
Year: 2009

This paper deals with the optimal path placement for a manipulator based on energy consumption. It proposes a methodology to determine the optimal location of a given test path within the workspace of a manipulator with minimal electric energy used by the actuators while taking into account the geometric, kinematic and dynamic constraints. The proposed methodology is applied to the Orthoglide~3-axis, a three-degree-of-freedom translational parallel kinematic machine (PKM), as an illustrative example.
Counting Independent Sets and Kernels of Regular Graphs
Venue: arXiv cs.DM 2009
Year: 2009

Chandrasekaran, Chertkov, Gamarnik, Shah, and Shin recently proved that the average number of independent sets of random regular graphs of size n and degree 3 approaches w^n for large n, where w is approximately 1.54563, consistent with the Bethe approximation. They also made the surprising conjecture that the fluctuations of the logarithm of the number of independent sets were only O(1) as n grew large, which would mean that the Bethe approximation is amazingly accurate for all 3-regular graphs. Here, I provide numerical evidence supporting this conjecture obtained from exact counts of independent sets using binary decision diagrams. I also provide numerical evidence that supports the novel conjectures that the number of kernels of 3-regular graphs of size n is given by y^n, where y is approximately 1.299, and that the fluctuations in the logarithm of the number of kernels is also only O(1).
Yet Another Pacman 3D Adventures
Venue: arXiv cs.GR 2009
Year: 2009

This game is meant to be extension of the overly-beaten pacman-style game (code-named "Yet Another Pacman 3D Adventures", or YAP3DAD) from the proposed ideas and other projects with advance visual and computer graphics features, including a-game-in-a-game approach. The project is an open-source project published on SourceForge.net for possible future development and extension.
An Iterative Shrinkage Approach to Total-Variation Image Restoration
Venue: arXiv cs.CV 2009
Year: 2009

The problem of restoration of digital images from their degraded measurements plays a central role in a multitude of practically important applications. A particularly challenging instance of this problem occurs in the case when the degradation phenomenon is modeled by an ill-conditioned operator. In such a case, the presence of noise makes it impossible to recover a valuable approximation of the image of interest without using some a priori information about its properties. Such a priori information is essential for image restoration, rendering it stable and robust to noise. Particularly, if the original image is known to be a piecewise smooth function, one of the standard priors used in this case is defined by the Rudin-Osher-Fatemi model, which results in total variation (TV) based image restoration. The current arsenal of algorithms for TV-based image restoration is vast. In the present paper, a different approach to the solution of the problem is proposed based on the method of iterative shrinkage (aka iterated thresholding). In the proposed method, the TV-based image restoration is performed through a recursive application of two simple procedures, viz. linear filtering and soft thresholding. Therefore, the method can be identified as belonging to the group of first-order algorithms which are efficient in dealing with images of relatively large sizes. Another valuable feature of the proposed method consists in its working directly with the TV functional, rather then with its smoothed versions. Moreover, the method provides a single solution for both isotropic and anisotropic definitions of the TV functional, thereby establishing a useful connection between the two formulae.
Temporal Debugging using URDB
Venue: arXiv cs.OS 2009
Year: 2009

A new style of temporal debugging is proposed. The new URDB debugger can employ such techniques as temporal search for finding an underlying fault that is causing a bug. This improves on the standard iterative debugging style, which iteratively re-executes a program under debugger control in the search for the underlying fault. URDB acts as a meta-debugger, with current support for four widely used debuggers: gdb, MATLAB, python, and perl. Support for a new debugger can be added in a few hours. Among its points of novelty are: (i) the first reversible debuggers for MATLAB, python, and perl; (ii) support for today's multi-core architectures; (iii) reversible debugging of multi-process and distributed computations; and (iv) temporal search on changes in program expressions. URDB gains its reversibility and temporal abilities through the fast checkpoint-restart capability of DMTCP (Distributed MultiThreaded CheckPointing). The recently enhanced DMTCP also adds ptrace support, enabling one to freeze, migrate, and replicate debugging sessions.
A theoretical foundation for building Knowledge-work Support Systems
Venue: arXiv cs.HC 2009
Year: 2009

In this paper we propose a novel approach aimed at building a new class of information system platforms which we call the "Knowledge-work Support Systems" or KwSS. KwSS can play a significant role in enhancing the IS support for knowledge management processes, including those customarily identified as less amenable to IS support. In our approach we try to enhance basic functionalities provided by the computer-based information systems, namely, that of improving the efficiency of the knowledge workers in accessing, processing and creating useful information. The improvement, along with proper focus on cultural, social and other aspects of the knowledge management processes, can enhance the workers' efficiency significantly in performing high quality knowledge works. In order to build the proposed approach, we develop several new concepts. The approach analyzes the information availability and usage from the knowledge workers and their works' perspectives and consequently brings forth more transparency in various aspects of information life-cycle with respect to knowledge management. KsSSes are technology platforms, which can be implemented independently as well as in conjunction with other knowledge management and data management technology platforms, to provide significant boost in the knowledge capabilities of organizations.
Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hashtables
Venue: arXiv cs.DS 2009
Year: 2009

We study the the following question in Random Graphs. We are given two disjoint sets $L,R$ with $|L|=n=αm$ and $|R|=m$. We construct a random graph $G$ by allowing each $x\in L$ to choose $d$ random neighbours in $R$. The question discussed is as to the size $μ(G)$ of the largest matching in $G$. When considered in the context of Cuckoo Hashing, one key question is as to when is $μ(G)=n$ whp? We answer this question exactly when $d$ is at least four. We also establish a precise threshold for when Phase 1 of the Karp-Sipser Greedy matching algorithm suffices to compute a maximum matching whp.
Forced Evolution in Silico by Artificial Transposons and their Genetic Operators: The John Muir Ant Problem
Venue: arXiv cs.NE 2009
Year: 2009

Modern evolutionary computation utilizes heuristic optimizations based upon concepts borrowed from the Darwinian theory of natural selection. We believe that a vital direction in this field must be algorithms that model the activity of genomic parasites, such as transposons, in biological evolution. This publication is our first step in the direction of developing a minimal assortment of algorithms that simulate the role of genomic parasites. Specifically, we started in the domain of genetic algorithms (GA) and selected the Artificial Ant Problem as a test case. We define these artificial transposons as a fragment of an ant's code that possesses properties that cause it to stand apart from the rest. We concluded that artificial transposons, analogous to real transposons, are truly capable of acting as intelligent mutators that adapt in response to an evolutionary problem in the course of co-evolution with their hosts.
An Improved Implementation of Grain
Venue: arXiv cs.CR 2009
Year: 2009

A common approach to protect confidential information is to use a stream cipher which combines plain text bits with a pseudo-random bit sequence. Among the existing stream ciphers, Non-Linear Feedback Shift Register (NLFSR)-based ones provide the best trade-off between cryptographic security and hardware efficiency. In this paper, we show how to further improve the hardware efficiency of Grain stream cipher. By transforming the NLFSR of Grain from its original Fibonacci configuration to the Galois configuration and by introducing a clock division block, we double the throughput of the 80 and 128-bit key 1bit/cycle architectures of Grain with no area penalty.
Magnetworks: how mobility impacts the design of Mobile Networks
Venue: arXiv cs.GT 2009
Year: 2009

In this paper we study the optimal placement and optimal number of active relay nodes through the traffic density in mobile sensor ad-hoc networks. We consider a setting in which a set of mobile sensor sources is creating data and a set of mobile sensor destinations receiving that data. We make the assumption that the network is massively dense, i.e., there are so many sources, destinations, and relay nodes, that it is best to describe the network in terms of macroscopic parameters, such as their spatial density, rather than in terms of microscopic parameters, such as their individual placements. We focus on a particular physical layer model that is characterized by the following assumptions: i) the nodes must only transport the data from the sources to the destinations, and do not need to sense the data at the sources, or deliver them at the destinations once the data arrive at their physical locations, and ii) the nodes have limited bandwidth available to them, but they use it optimally to locally achieve the network capacity. In this setting, the optimal distribution of nodes induces a traffic density that resembles the electric displacement that will be created if we substitute the sources and destinations with positive and negative charges respectively. The analogy between the two settings is very tight and have a direct interpretation in wireless sensor networks.
From Single-thread to Multithreaded: An Efficient Static Analysis Algorithm
Venue: arXiv cs.PL 2009
Year: 2009

A great variety of static analyses that compute safety properties of single-thread programs have now been developed. This paper presents a systematic method to extend a class of such static analyses, so that they handle programs with multiple POSIX-style threads. Starting from a pragmatic operational semantics, we build a denotational semantics that expresses reasoning a la assume-guarantee. The final algorithm is then derived by abstract interpretation. It analyses each thread in turn, propagating interferences between threads, in addition to other semantic information. The combinatorial explosion, ensued from the explicit consideration of all interleavings, is thus avoided. The worst case complexity is only increased by a factor n compared to the single-thread case, where n is the number of instructions in the program. We have implemented prototype tools, demonstrating the practicality of the approach.
Meshat: Monitoring and Experience Sharing Tool for Project-Based Learning
Venue: arXiv cs.CY 2009
Year: 2009

Our work aims at studying tools offered to learners and tutors involved in face-to-face or blended project-based learning activities. To understand better the needs and expectations of each actor, we are especially interested in the specific case of project management training. The results of a course observation show that the lack of monitoring and expertise transfer tools involves important dysfunctions in the course organisation and therefore dissatisfaction for tutors and students (in particular about the acquisition of knowledge and expertise). So as to solve this problem, we propose a personalised platform (according to the actor: project group, student or tutor) which gives information to monitor activities and supports the acquisition and transfer of expertise. This platform is meant for the complex educational context of project-based learning. Indeed, as for the majority of project-based learning activities, the articulation conceptualisation-experiment is an important part of the process. The originality of our approach relies on also supporting the articulation between action (experiment or conceptualisation) and reflection. This approach so improves the acquisition of complex skills (e.g. management, communication and collaboration), which requires a behavioural evolution. We aim at making the students become able ?to learn to learn' and evolve according to contexts. We facilitate their ability to have a critical analysis of their actions according to the situations they encounter.
On the precoder design of flat fading MIMO systems equipped with MMSE receivers: a large system approach
Venue: arXiv cs.IT 2009
Year: 2009

This paper is devoted to the design of precoders maximizing the ergodic mutual information (EMI) of bi-correlated flat fading MIMO systems equiped with MMSE receivers. The channel state information and the second order statistics of the channel are assumed available at the receiver side and at the transmitter side respectively. As the direct maximization of the EMI needs the use of non attractive algorithms, it is proposed to optimize an approximation of the EMI, introduced recently, obtained when the number of transmit and receive antennas $t$ and $r$ converge to $\infty$ at the same rate. It is established that the relative error between the actual EMI and its approximation is a $O(\frac{1}{t^{2}})$ term. It is shown that the left singular eigenvectors of the optimum precoder coincide with the eigenvectors of the transmit covariance matrix, and its singular values are solution of a certain maximization problem. Numerical experiments show that the mutual information provided by this precoder is close from what is obtained by maximizing the true EMI, but that the algorithm maximizing the approximation is much less computationally intensive.
From Method Fragments to Method Services
Venue: arXiv cs.SE 2009
Year: 2009

In Method Engineering (ME) science, the key issue is the consideration of information system development methods as fragments. Numerous ME approaches have produced several definitions of method parts. Different in nature, these fragments have nevertheless some common disadvantages: lack of implementation tools, insufficient standardization effort, and so on. On the whole, the observed drawbacks are related to the shortage of usage orientation. We have proceeded to an in-depth analysis of existing method fragments within a comparison framework in order to identify their drawbacks. We suggest overcoming them by an improvement of the ?method service? concept. In this paper, the method service is defined through the service paradigm applied to a specific method fragment ? chunk. A discussion on the possibility to develop a unique representation of method fragment completes our contribution.
Feature-Weighted Linear Stacking
Venue: arXiv cs.LG 2009
Year: 2009

Ensemble methods, such as stacking, are designed to boost predictive accuracy by blending the predictions of multiple machine learning models. Recent work has shown that the use of meta-features, additional inputs describing each example in a dataset, can boost the performance of ensemble methods, but the greatest reported gains have come from nonlinear procedures requiring significant tuning and training time. Here, we present a linear technique, Feature-Weighted Linear Stacking (FWLS), that incorporates meta-features for improved accuracy while retaining the well-known virtues of linear regression regarding speed, stability, and interpretability. FWLS combines model predictions linearly using coefficients that are themselves linear functions of meta-features. This technique was a key facet of the solution of the second place team in the recently concluded Netflix Prize competition. Significant increases in accuracy over standard linear stacking are demonstrated on the Netflix Prize collaborative filtering dataset.
Strange Bedfellows: Quantum Mechanics and Data Mining
Venue: arXiv cs.LG 2009
Year: 2009

Last year, in 2008, I gave a talk titled {\it Quantum Calisthenics}. This year I am going to tell you about how the work I described then has spun off into a most unlikely direction. What I am going to talk about is how one maps the problem of finding clusters in a given data set into a problem in quantum mechanics. I will then use the tricks I described to let quantum evolution lets the clusters come together on their own.
Radio Transmission Performance of EPCglobal Gen-2 RFID System
Venue: arXiv cs.OH 2009
Year: 2009

In this paper, we analyze the performance of the encoding and the modulation processes in the downlink and uplink of the EPCglobal Gen2 system through the analysis and simulation. Furthermore, the synchronization issues on time and frequency domain and the preamble architecture are evaluated. Through the simulation in the uplink, we find that the detection probability of FM0 and Miller coding approaches 1 at 13dB Eb/N0.
On Element SDD Approximability
Venue: arXiv cs.NA 2009
Year: 2009

This short communication shows that in some cases scalar elliptic finite element matrices cannot be approximated well by an SDD matrix. We also give a theoretical analysis of a simple heuristic method for approximating an element by an SDD matrix.
GSM Security Using Identity-based Cryptography
Venue: arXiv cs.CR 2009
Year: 2009

Current security model in Global System for Mobile Communications (GSM) predominantly use symmetric key cryptography. The rapid advancement of Internet technology facilitates online trading, banking, downloading, emailing using resource-constrained handheld devices such as personal digital assistants and cell phones. However, these applications require more security than the present GSM supports. Consequently, a careful design of GSM security using both symmetric and asymmetric key cryptography would make GSM security more adaptable in security intensive applications. This paper presents a secure and efficient protocol for GSM security using identity based cryptography. The salient features of the proposed protocol are (i) authenticated key exchange; (ii) mutual authentication amongst communicating entities; and (iii) user anonymity. The security analysis of the protocol shows its strength against some known threats observed in conventional GSM security.
Multiple Description Coding of Discrete Ergodic Sources
Venue: arXiv cs.IT 2009
Year: 2009

We investigate the problem of Multiple Description (MD) coding of discrete ergodic processes. We introduce the notion of MD stationary coding, and characterize its relationship to the conventional block MD coding. In stationary coding, in addition to the two rate constraints normally considered in the MD problem, we consider another rate constraint which reflects the conditional entropy of the process generated by the third decoder given the reconstructions of the two other decoders. The relationship that we establish between stationary and block MD coding enables us to devise a universal algorithm for MD coding of discrete ergodic sources, based on simulated annealing ideas that were recently proven useful for the standard rate distortion problem.
Power and Transmission Duration Control for Un-Slotted Cognitive Radio Networks
Venue: arXiv cs.IT 2009
Year: 2009

We consider an unslotted primary channel with alternating on/off activity and provide a solution to the problem of finding the optimal secondary transmission power and duration given some sensing outcome. The goal is to maximize a weighted sum of the primary and secondary throughput where the weight is determined by the minimum rate required by the primary terminals. The primary transmitter sends at a fixed power and a fixed rate. Its on/off durations follow an exponential distribution. Two sensing schemes are considered: perfect sensing in which the actual state of the primary channel is revealed, and soft sensing in which the secondary transmission power and time are determined based on the sensing metric directly. We use an upperbound for the secondary throughput assuming that the secondary receiver tracks the instantaneous secondary channel state information. The objective function is non-convex and, hence, the optimal solution is obtained via exhaustive search. Our results show that an increase in the overall weighted throughput can be obtained by allowing the secondary to transmit even when the channel is found to be busy. For the examined system parameter values, the throughput gain from soft sensing is marginal. Further investigation is needed for assessing the potential of soft sensing.
Multicell Zero-Forcing and User Scheduling on the Downlink of a Linear Cell Array
Venue: arXiv cs.IT 2009
Year: 2009

Coordinated base station (BS) transmission has attracted much interest for its potential to increase the capacity of wireless networks. Yet at the same time, the achievable sum-rate with single-cell processing (SCP) scales optimally with the number of users under Rayleigh fading conditions. One may therefore ask if the value of BS coordination is limited in the many-user regime from a sum-rate perspective. With this in mind we consider multicell zero-forcing beamforming (ZFBF) on the downlink of a linear cell-array. We first identify the beamforming weights and the optimal scheduling policy under a per-base power constraint. We then compare the number of users m and n required per-cell to achieve the same mean SINR, after optimal scheduling, with SCP and ZFBF respectively. Specifically, we show that the ratio m/n grows logarithmically with n. Finally, we demonstrate that the gain in sum-rate between ZFBF and SCP is significant for all practical values of number of users.
Knowledge linkage structures in communication studies using citation analysis among communication journals
Venue: arXiv cs.DL 2009
Year: 2009

This research analyzes a "who cites whom" matrix in terms of aggregated, journal-journal citations to determine the location of communication studies on the academic spectrum. Using the Journal of Communication as the seed journal, the 2006 data in the Journal Citation Reports are used to map communication studies. The results show that social and experimental psychology journals are the most frequently used sources of information in this field. In addition, several journals devoted to the use and effects of media and advertising are weakly integrated into the larger communication research community, whereas communication studies are dominated by American journals.
Bounding the radii of balls meeting every connected component of semi-algebraic sets
Venue: arXiv cs.SC 2009
Year: 2009

We prove explicit bounds on the radius of a ball centered at the origin which is guaranteed to contain all bounded connected components of a semi-algebraic set $S \subset \mathbbm{R}^k$ defined by a quantifier-free formula involving $s$ polynomials in $\mathbbm{Z}[X_1, ..., X_k]$ having degrees at most $d$, and whose coefficients have bitsizes at most $τ$. Our bound is an explicit function of $s, d, k$ and $τ$, and does not contain any undetermined constants. We also prove a similar bound on the radius of a ball guaranteed to intersect every connected component of $S$ (including the unbounded components). While asymptotic bounds of the form $2^{τd^{O (k)}}$ on these quantities were known before, some applications require bounds which are explicit and which hold for all values of $s, d, k$ and $τ$. The bounds proved in this paper are of this nature.