OpenRaiser/Intern-Atlas huggingface dataset:
Simple proofs for duality of generalized minimum poset weights and weight distributions of (Near-)MDS poset codes
Venue: arXiv cs.IT 2011
Year: 2011

In 1991, Wei introduced generalized minimum Hamming weights for linear codes and showed their monotonicity and duality. Recently, several authors extended these results to the case of generalized minimum poset weights by using different methods. Here, we would like to prove the duality by using matroid theory. This gives yet another and very simple proof of it. In particular, our argument will make it clear that the duality follows from the well-known relation between the rank function and the corank function of a matroid. In addition, we derive the weight distributions of linear MDS and Near-MDS poset codes in the same spirit.
Bounds on the Capacity of the Relay Channel with Noncausal State at Source
Venue: arXiv cs.IT 2011
Year: 2011

We consider a three-terminal state-dependent relay channel with the channel state available non-causally at only the source. Such a model may be of interest for node cooperation in the framework of cognition, i.e., collaborative signal transmission involving cognitive and non-cognitive radios. We study the capacity of this communication model. One principal problem is caused by the relay's not knowing the channel state. For the discrete memoryless (DM) model, we establish two lower bounds and an upper bound on channel capacity. The first lower bound is obtained by a coding scheme in which the source describes the state of the channel to the relay and destination, which then exploit the gained description for a better communication of the source's information message. The coding scheme for the second lower bound remedies the relay's not knowing the states of the channel by first computing, at the source, the appropriate input that the relay would send had the relay known the states of the channel, and then transmitting this appropriate input to the relay. The relay simply guesses the sent input and sends it in the next block. The upper bound is non trivial and it accounts for not knowing the state at the relay and destination. For the general Gaussian model, we derive lower bounds on the channel capacity by exploiting ideas in the spirit of those we use for the DM model; and we show that these bounds are optimal for small and large noise at the relay irrespective to the strength of the interference. Furthermore, we also consider a special case model in which the source input has two components one of which is independent of the state. We establish a better upper bound for both DM and Gaussian cases and we also characterize the capacity in a number of special cases.
Approximating the Balanced Minimum Evolution Problem
Venue: arXiv cs.DS 2011
Year: 2011

We prove a strong inapproximability result for the Balanced Minimum Evolution Problem. Our proof also implies that the problem remains NP-hard even when restricted to metric instances. Furthermore, we give a MST-based 2-approximation algorithm for the problem for such instances.
Can virtual reality predict body part discomfort and performance of people in realistic world for assembling tasks?
Venue: arXiv cs.RO 2011
Year: 2011

This paper presents our work on relationship of evaluation results between virtual environment (VE) and realistic environment (RE) for assembling tasks. Evaluation results consist of subjective results (BPD and RPE) and objective results (posture and physical performance). Same tasks were performed with same experimental configurations and evaluation results were measured in RE and VE respectively. Then these evaluation results were compared. Slight difference of posture between VE and RE was found but not great difference of effect on people according to conventional ergonomics posture assessment method. Correlation of BPD and performance results between VE and RE are found by linear regression method. Moreover, results of BPD, physical performance, and RPE in VE are higher than that in RE with significant difference. Furthermore, these results indicates that subjects feel more discomfort and fatigue in VE than RE because of additional effort required in VE.
Context Aware Multisensor Image Fusion for Military Sensor Networks using Multi Agent System
Venue: arXiv cs.MA 2011
Year: 2011

This paper proposes a Context Aware Agent based Military Sensor Network (CAMSN) to form an improved infrastructure for multi-sensor image fusion. It considers contexts driven by a node and sink. The contexts such as general and critical object detection are node driven where as sensing time (such as day or night) is sink driven. The agencies used in the scheme are categorized as node and sink agency. Each agency employs a set of static and mobile agents to perform dedicated tasks. Node agency performs context sensing and context interpretation based on the sensed image and sensing time. Node agency comprises of node manager agent, context agent and node blackboard (NBB). Context agent gathers the context from the target and updates the NBB, Node manager agent interprets the context and passes the context information to sink node by using flooding mechanism. Sink agency mainly comprises of sink manager agent, fusing agent, and sink black board. A context at the sensor node triggers the fusion process at the sink. Based on the context, sink manager agent triggers the fusing agent. Fusing agent roams around the network, visits active sensor node, fuses the relevant images and sends the fused image to sink. The fusing agent uses wavelet transform for fusion. The scheme is simulated for testing its operation effectiveness in terms of fusion time, mean square error, throughput, dropping rate, bandwidth requirement, node battery usage and agent overhead.
Expectations and Reality: Why an enterprise software system didn't work as planned
Venue: arXiv cs.SE 2011
Year: 2011

Over two decades, we and other research groups have found that ethnographic and social analyses of work settings can provide insights useful to the process of system analysis and design. Despite this, ethnographic and social analyses have not been widely assimilated into industry practice. Practitioners tend to address sociotechnical factors in an ad-hoc manner, often post-implementation, once system use or outcome has become problematic. In response to this, we have developed a lightweight qualitative approach to provide insights to ameliorate problematic system deployments. Unlike typical ethnographies and social analyses of work activity that inform systems analysis and design; we argue that analysis of intentional and structural factors to inform system deployment and integration can have a shorter time duration and yet can provide actionable insights. We evaluate our approach using a case study of a problematic enterprise document manage-ment system within a multinational systems engineering organization. Our find-ings are of academic and practical significance as our approach demonstrates that structural-intentional analysis scales to enable the timely analysis of large-scale system deployments.
Coding Bounds for Multiple Phased-Burst Correction and Single Burst Correction Codes
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, two upper bounds on the achievable code rate of linear block codes for multiple phased-burst correction (MPBC) are presented. One bound is constrained to a maximum correctable cyclic burst length within every subblock, or equivalently a constraint on the minimum error free length or gap within every phased-burst. This bound, when reduced to the special case of a bound for single burst correction (SBC), is shown to be the Abramson bound when the cyclic burst length is less than half the block length. The second MPBC bound is developed without the minimum error free gap constraint and is used as a comparison to the first bound.
Gaussian Affine Feature Detector
Venue: arXiv cs.CV 2011
Year: 2011

A new method is proposed to get image features' geometric information. Using Gaussian as an input signal, a theoretical optimal solution to calculate feature's affine shape is proposed. Based on analytic result of a feature model, the method is different from conventional iterative approaches. From the model, feature's parameters such as position, orientation, background luminance, contrast, area and aspect ratio can be extracted. Tested with synthesized and benchmark data, the method achieves or outperforms existing approaches in term of accuracy, speed and stability. The method can detect small, long or thin objects precisely, and works well under general conditions, such as for low contrast, blurred or noisy images.
Prosper: image and robot-guided prostate brachytherapy
Venue: arXiv cs.RO 2011
Year: 2011

Brachytherapy for localized prostate cancer consists in destroying cancer by introducing iodine radioactive seeds into the gland through hollow needles. The planning of the position of the seeds and their introduction into the prostate is based on intra-operative ultrasound (US) imaging. We propose to optimize the global quality of the procedure by: i) using 3D US; ii) enhancing US data with MRI registration; iii) using a specially designed needle-insertion robot, connected to the imaging data. The imaging methods have been successfully tested on patient data while the robot accuracy has been evaluated on a realistic deformable phantom.
Physical Simulation of Inarticulate Robots
Venue: arXiv cs.RO 2011
Year: 2011

In this note we study the structure and the behavior of inarticulate robots. We introduce a robot that moves by successive revolvings. The robot's structure is analyzed, simulated and discussed in detail.
A Fuzzy Control Algorithm for the Electronic Stability Program optimized for tyre burst control
Venue: arXiv cs.SY 2011
Year: 2011

This paper introduces an improved Electronic Stability Program for cars that can deal with the sudden burst of a tyre. The Improved Electronic Stability Program (IESP) is based on a fuzzy logic algorithm. The IESP collects data from the same sensors of a standard ESP and acts on brakes/throttle with the same actuators. The IESP reads the driver steering angle and the dynamic condition of the car and selectively acts on throttle and brakes in order to put the car on the required direction even during a tyre burst.
Continuous and Discrete Adjoints to the Euler Equations for Fluids
Venue: arXiv cs.CE 2011
Year: 2011

Adjoints are used in optimization to speed-up computations, simplify optimality conditions or compute sensitivities. Because time is reversed in adjoint equations with first order time derivatives, boundary conditions and transmission conditions through shocks can be difficult to understand. In this article we analyze the adjoint equations that arise in the context of compressible flows governed by the Euler equations of fluid dynamics. We show that the continuous adjoints and the discrete adjoints computed by automatic differentiation agree numerically; in particular the adjoint is found to be continuous at the shocks and usually discontinuous at contact discontinuities by both.
Multi-User Diversity with Random Number of Users
Venue: arXiv cs.IT 2011
Year: 2011

Multi-user diversity is considered when the number of users in the system is random. The complete monotonicity of the error rate as a function of the (deterministic) number of users is established and it is proved that randomization of the number of users always leads to deterioration of average system performance at any average SNR. Further, using stochastic ordering theory, a framework for comparison of system performance for different user distributions is provided. For Poisson distributed users, the difference in error rate of the random and deterministic number of users cases is shown to asymptotically approach zero as the average number of users goes to infinity for any fixed average SNR. In contrast, for a finite average number of users and high SNR, it is found that randomization of the number of users deteriorates performance significantly, and the diversity order under fading is dominated by the smallest possible number of users. For Poisson distributed users communicating over Rayleigh faded channels, further closed-form results are provided for average error rate, and the asymptotic scaling law for ergodic capacity is also provided. Simulation results are provided to corroborate our analytical findings.
A quantum protocol for sampling correlated equilibria unconditionally and without a mediator
Venue: arXiv cs.GT 2011
Year: 2011

A correlated equilibrium is a fundamental solution concept in game theory that enjoys many desirable properties. However, it requires a trusted mediator, which is a major drawback in many practical applications. A computational solution to this problem was proposed by Dodis, Halevi and Rabin. They extended the original game by adding an initial communication stage and showed that any correlated strategy for 2-player games can be achieved, provided that the players are computationally bounded. In this paper, we show that if the players can communicate via a quantum channel before the game, then any correlated equilibrium for 2-player games can be achieved, without a trusted mediator and unconditionally. This provides another example of a major advantage of quantum information processing. More precisely, we prove that for any correlated equilibrium p of a strategic game G, there exists an extended game (with a quantum communication initial stage) Q with an efficiently computable approximate Nash equilibrium q, such that the expected payoff for both players in q is at least as high as in p. The main cryptographic tool used in the construction is the quantum weak coin flipping protocol of Mochon.
Simulating Spiking Neural P systems without delays using GPUs
Venue: arXiv cs.DC 2011
Year: 2011

We present in this paper our work regarding simulating a type of P system known as a spiking neural P system (SNP system) using graphics processing units (GPUs). GPUs, because of their architectural optimization for parallel computations, are well-suited for highly parallelizable problems. Due to the advent of general purpose GPU computing in recent years, GPUs are not limited to graphics and video processing alone, but include computationally intensive scientific and mathematical applications as well. Moreover P systems, including SNP systems, are inherently and maximally parallel computing models whose inspirations are taken from the functioning and dynamics of a living cell. In particular, SNP systems try to give a modest but formal representation of a special type of cell known as the neuron and their interactions with one another. The nature of SNP systems allowed their representation as matrices, which is a crucial step in simulating them on highly parallel devices such as GPUs. The highly parallel nature of SNP systems necessitate the use of hardware intended for parallel computations. The simulation algorithms, design considerations, and implementation are presented. Finally, simulation results, observations, and analyses using an SNP system that generates all numbers in $\mathbb N$ - {1} are discussed, as well as recommendations for future work.
Randomized $Δ$-Edge-Coloring via Quaternion of Complex Colors
Venue: arXiv cs.DS 2011
Year: 2011

This paper explores the application of a new algebraic method of color exchanges to the edge coloring of simple graphs. Vizing's theorem states that the edge coloring of a simple graph $G$ requires either $Δ$ or $Δ+1$ colors, where $Δ$ is the maximum vertex degree of $G$. Holyer proved that it is {\bf NP}-complete to decide whether $G$ is $Δ$-edge-colorable even for cubic graphs. By introducing the concept of complex colors, we show that the color-exchange operation follows the same multiplication rules as quaternion. An initially $Δ$-edge-colored graph $G$ allows variable-colored edges, which can be eliminated by color exchanges in a manner similar to variable eliminations in solving systems of linear equations. The problem is solved if all variables are eliminated and a properly $Δ$-edge-colored graph is reached. For a randomly generated graph $G$, we prove that our algorithm returns a proper $Δ$-edge-coloring with a probability of at least 1/2 in $O(Δ|V||E|^5)$ time if $G$ is $Δ$-edge-colorable. Otherwise, the algorithm halts in polynomial time and signals the impossibility of a solution, meaning that the chromatic index of $G$ probably equals $Δ+1$. Animations of the edge-coloring algorithms proposed in this paper are posted at YouTube http://www.youtube.com/watch?v=KMnj4UMYl7k.
Off-Line Handwritten Signature Retrieval using Curvelet Transforms
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, a new method for offline handwritten signature retrieval is based on curvelet transform is proposed. Many applications in image processing require similarity retrieval of an image from a large collection of images. In such cases, image indexing becomes important for efficient organization and retrieval of images. This paper addresses this issue in the context of a database of handwritten signature images and describes a system for similarity retrieval. The proposed system uses a curvelet based texture features extraction. The performance of the system has been tested with an image database of 180 signatures. The results obtained indicate that the proposed system is able to identify signatures with great with accuracy even when a part of a signature is missing.
GEOMIR2K9 - A Similar Scene Finder
Venue: arXiv cs.CV 2011
Year: 2011

The main goal of the GEOMIR2K9 project is to create a software program that is able to find similar scenic images clustered by geographical location and sorted by similarity based only on their visual content. The user should be able to input a query image, based on this given query image the program should find relevant visual content and present this to the user in a meaningful way. Technically the goal for the GEOMIR2K9 project is twofold. The first of these two goals is to create a basic low level visual information retrieval system. This includes feature extraction, post processing of the feature data and classification/ clustering based on similarity with a strong focus on scenic images. The second goal of this project is to provide the user with a novel and suitable interface and visualization method so that the user may interact with the retrieved images in a natural and meaningful way.
Optimizing XML querying using type-based document projection
Venue: arXiv cs.DB 2011
Year: 2011

XML data projection (or pruning) is a natural optimization for main memory query engines: given a query Q over a document D, the subtrees of D that are not necessary to evaluate Q are pruned, thus producing a smaller document D'; the query Q is then executed on D', hence avoiding to allocate and process nodes that will never be reached by Q. In this article, we propose a new approach, based on types, that greatly improves current solutions. Besides providing comparable or greater precision and far lesser pruning overhead, our solution ---unlike current approaches--- takes into account backward axes, predicates, and can be applied to multiple queries rather than just to single ones. A side contribution is a new type system for XPath able to handle backward axes. The soundness of our approach is formally proved. Furthermore, we prove that the approach is also complete (i.e., yields the best possible type-driven pruning) for a relevant class of queries and Schemas. We further validate our approach using the XMark and XPathMark benchmarks and show that pruning not only improves the main memory query engine's performances (as expected) but also those of state of the art native XML databases.
A Universal Part-of-Speech Tagset
Venue: arXiv cs.CL 2011
Year: 2011

To facilitate future research in unsupervised induction of syntactic structure and to standardize best-practices, we propose a tagset that consists of twelve universal part-of-speech categories. In addition to the tagset, we develop a mapping from 25 different treebank tagsets to this universal set. As a result, when combined with the original treebank data, this universal tagset and mapping produce a dataset consisting of common parts-of-speech for 22 different languages. We highlight the use of this resource via two experiments, including one that reports competitive accuracies for unsupervised grammar induction without gold standard part-of-speech tags.
Extracting Parts of 2D Shapes Using Local and Global Interactions Simultaneously
Venue: arXiv cs.CV 2011
Year: 2011

Perception research provides strong evidence in favor of part based representation of shapes in human visual system. Despite considerable differences among different theories in terms of how part boundaries are found, there is substantial agreement on that the process depends on many local and global geometric factors. This poses an important challenge from the computational point of view. In the first part of the chapter, I present a novel decomposition method by taking both local and global interactions within the shape domain into account. At the top of the partitioning hierarchy, the shape gets split into two parts capturing, respectively, the gross structure and the peripheral structure. The gross structure may be conceived as the least deformable part of the shape which remains stable under visual transformations. The peripheral structure includes limbs, protrusions, and boundary texture. Such a separation is in accord with the behavior of the artists who start with a gross shape and enrich it with details. The method is particularly interesting from the computational point of view as it does not resort to any geometric notions (e.g. curvature, convexity) explicitly. In the second part of the chapter, I relate the new method to PDE based shape representation schemes.
Subexponential Parameterized Algorithm for Minimum Fill-in
Venue: arXiv cs.DS 2011
Year: 2011

The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. Kaplan, Shamir, and Tarjan [FOCS 1994] have shown that the problem is solvable in time O(2^(O(k)) + k2 * nm) on graphs with n vertices and m edges and thus is fixed parameter tractable. Here, we give the first subexponential parameterized algorithm solving Minimum Fill-in in time O(2^(O(\sqrt{k} log k)) + k2 * nm). This substantially lower the complexity of the problem. Techniques developed for Minimum Fill-in can be used to obtain subexponential parameterized algorithms for several related problems including Minimum Chain Completion, Chordal Graph Sandwich, and Triangulating Colored Graph.
The Critical Exponent is Computable for Automatic Sequences
Venue: arXiv cs.FL 2011
Year: 2011

The critical exponent of an infinite word is defined to be the supremum of the exponent of each of its factors. For k-automatic sequences, we show that this critical exponent is always either a rational number or infinite, and its value is computable. Our results also apply to variants of the critical exponent, such as the initial critical exponent of Berthe, Holton, and Zamboni and the Diophantine exponent of Adamczewski and Bugeaud. Our work generalizes or recovers previous results of Krieger and others, and is applicable to other situations; e.g., the computation of the optimal recurrence constant for a linearly recurrent k-automatic sequence.