OpenRaiser/Intern-Atlas huggingface dataset:
Group-Decodable Space-Time Block Codes with Code Rate > 1
Venue: arXiv cs.IT 2010
Year: 2010

High-rate space-time block codes (STBC with code rate > 1) in multi-input multi-output (MIMO) systems are able to provide both spatial multiplexing gain and diversity gain, but have high maximum likelihood (ML) decoding complexity. Since group-decodable (quasi-orthogonal) code structure can reduce the decoding complexity, we present in this paper systematic methods to construct group-decodable high-rate STBC with full symbol-wise diversity gain for arbitrary transmit antenna number and code length. We show that the proposed group-decodable STBC can achieve high code rate that increases almost linearly with the transmit antenna number, and the slope of this near-linear dependence increases with the code length. Comparisons with existing low-rate and high-rate codes (such as orthogonal STBC and algebraic STBC) are conducted to show the decoding complexity reduction and good code performance achieved by the proposed codes.
Bisimulations for Nondeterministic Labeled Markov Processes
Venue: arXiv cs.LO 2010
Year: 2010

We extend the theory of labeled Markov processes with internal nondeterminism, a fundamental concept for the further development of a process theory with abstraction on nondeterministic continuous probabilistic systems. We define nondeterministic labeled Markov processes (NLMP) and provide three definition of bisimulations: a bisimulation following a traditional characterization, a state based bisimulation tailored to our "measurable" non-determinism, and an event based bisimulation. We show the relation between them, including that the largest state bisimulation is also an event bisimulation. We also introduce a variation of the Hennessy-Milner logic that characterizes event bisimulation and that is sound w.r.t. the other bisimulations for arbitrary NLMP. This logic, however, is infinitary as it contains a denumerable $\lor$. We then introduce a finitary sublogic that characterize all bisimulations for image finite NLMP whose underlying measure space is also analytic. Hence, in this setting, all notions of bisimulation we deal with turn out to be equal. Finally, we show that all notions of bisimulations are different in the general case. The counterexamples that separate them turn to be non-probabilistic NLMP.
Multi-core: Adding a New Dimension to Computing
Venue: arXiv cs.AR 2010
Year: 2010

Invention of Transistors in 1948 started a new era in technology, called Solid State Electronics. Since then, sustaining development and advancement in electronics and fabrication techniques has caused the devices to shrink in size and become smaller, paving the quest for increasing density and clock speed. That quest has suddenly come to a halt due to fundamental bounds applied by physical laws. But, demand for more and more computational power is still prevalent in the computing world. As a result, the microprocessor industry has started exploring the technology along a different dimension. Speed of a single work unit (CPU) is no longer the concern, rather increasing the number of independent processor cores packed in a single package has become the new concern. Such processors are commonly known as multi-core processors. Scaling the performance by using multiple cores has gained so much attention from the academia and the industry, that not only desktops, but also laptops, PDAs, cell phones and even embedded devices today contain these processors. In this paper, we explore state of the art technologies for multi-core processors and existing software tools to support parallelism. We also discuss present and future trend of research in this field. From our survey, we conclude that next few decades are going to be marked by the success of this "Ubiquitous parallel processing".
Fast Multiplication of Matrices with Decay
Venue: arXiv cs.DS 2010
Year: 2010

A fast algorithm for the approximate multiplication of matrices with decay is introduced; the Sparse Approximate Matrix Multiply (SpAMM) reduces complexity in the product space, a different approach from current methods that economize within the matrix space through truncation or rank reduction. Matrix truncation (element dropping) is compared to SpAMM for quantum chemical matrices with approximate exponential and algebraic decay. For matched errors in the electronic total energy, SpAMM is found to require fewer to far fewer floating point operations relative to dropping. The challenges and opportunities afforded by this new approach are discussed, including the potential for high performance implementations.
A Probabilistic Approach for Learning Folksonomies from Structured Data
Venue: arXiv cs.AI 2010
Year: 2010

Learning structured representations has emerged as an important problem in many domains, including document and Web data mining, bioinformatics, and image analysis. One approach to learning complex structures is to integrate many smaller, incomplete and noisy structure fragments. In this work, we present an unsupervised probabilistic approach that extends affinity propagation to combine the small ontological fragments into a collection of integrated, consistent, and larger folksonomies. This is a challenging task because the method must aggregate similar structures while avoiding structural inconsistencies and handling noise. We validate the approach on a real-world social media dataset, comprised of shallow personal hierarchies specified by many individual users, collected from the photosharing website Flickr. Our empirical results show that our proposed approach is able to construct deeper and denser structures, compared to an approach using only the standard affinity propagation algorithm. Additionally, the approach yields better overall integration quality than a state-of-the-art approach based on incremental relational clustering.
A Framework for Quantitative Analysis of Cascades on Networks
Venue: arXiv cs.SI 2010
Year: 2010

How does information flow in online social networks? How does the structure and size of the information cascade evolve in time? How can we efficiently mine the information contained in cascade dynamics? We approach these questions empirically and present an efficient and scalable mathematical framework for quantitative analysis of cascades on networks. We define a cascade generating function that captures the details of the microscopic dynamics of the cascades. We show that this function can also be used to compute the macroscopic properties of cascades, such as their size, spread, diameter, number of paths, and average path length. We present an algorithm to efficiently compute cascade generating function and demonstrate that while significantly compressing information within a cascade, it nevertheless allows us to accurately reconstruct its structure. We use this framework to study information dynamics on the social network of Digg. Digg allows users to post and vote on stories, and easily see the stories that friends have voted on. As a story spreads on Digg through voting, it generates cascades. We extract cascades of more than 3,500 Digg stories and calculate their macroscopic and microscopic properties. We identify several trends in cascade dynamics: spreading via chaining, branching and community. We discuss how these affect the spread of the story through the Digg social network. Our computational framework is general and offers a practical solution to quantitative analysis of the microscopic structure of even very large cascades.
Optimizing real-time RDF data streams
Venue: arXiv cs.AI 2010
Year: 2010

The Resource Description Framework (RDF) provides a common data model for the integration of "real-time" social and sensor data streams with the Web and with each other. While there exist numerous protocols and data formats for exchanging dynamic RDF data, or RDF updates, these options should be examined carefully in order to enable a Semantic Web equivalent of the high-throughput, low-latency streams of typical Web 2.0, multimedia, and gaming applications. This paper contains a brief survey of RDF update formats and a high-level discussion of both TCP and UDP-based transport protocols for updates. Its main contribution is the experimental evaluation of a UDP-based architecture which serves as a real-world example of a high-performance RDF streaming application in an Internet-scale distributed environment.
iCare: A Mobile Health Monitoring System for the Elderly
Venue: arXiv cs.OH 2010
Year: 2010

This paper describes a mobile health monitoring system called iCare for the elderly. We use wireless body sensors and smart phones to monitor the wellbeing of the elderly. It can offer remote monitoring for the elderly anytime anywhere and provide tailored services for each person based on their personal health condition. When detecting an emergency, the smart phone will automatically alert pre-assigned people who could be the old people's family and friends, and call the ambulance of the emergency centre. It also acts as the personal health information system and the medical guidance which offers one communication platform and the medical knowledge database so that the family and friends of the served people can cooperate with doctors to take care of him/her. The system also features some unique functions that cater to the living demands of the elderly, including regular reminder, quick alarm, medical guidance, etc. iCare is not only a real-time health monitoring system for the elderly, but also a living assistant which can make their lives more convenient and comfortable.
Network error correction with unequal link capacities
Venue: arXiv cs.IT 2010
Year: 2010

This paper studies the capacity of single-source single-sink noiseless networks under adversarial or arbitrary errors on no more than z edges. Unlike prior papers, which assume equal capacities on all links, arbitrary link capacities are considered. Results include new upper bounds, network error correction coding strategies, and examples of network families where our bounds are tight. An example is provided of a network where the capacity is 50% greater than the best rate that can be achieved with linear coding. While coding at the source and sink suffices in networks with equal link capacities, in networks with unequal link capacities, it is shown that intermediate nodes may have to do coding, nonlinear error detection, or error correction in order to achieve the network error correction capacity.
Optimal Distributed Beamforming for MISO Interference Channels
Venue: arXiv cs.IT 2010
Year: 2010

We consider the problem of quantifying the Pareto optimal boundary in the achievable rate region over multiple-input single-output (MISO) interference channels, where the problem boils down to solving a sequence of convex feasibility problems after certain transformations. The feasibility problem is solved by two new distributed optimal beamforming algorithms, where the first one is to parallelize the computation based on the method of alternating projections, and the second one is to localize the computation based on the method of cyclic projections. Convergence proofs are established for both algorithms.
Artificial Hormone Reaction Networks: Towards Higher Evolvability in Evolutionary Multi-Modular Robotics
Venue: arXiv cs.RO 2010
Year: 2010

The semi-automatic or automatic synthesis of robot controller software is both desirable and challenging. Synthesis of rather simple behaviors such as collision avoidance by applying artificial evolution has been shown multiple times. However, the difficulty of this synthesis increases heavily with increasing complexity of the task that should be performed by the robot. We try to tackle this problem of complexity with Artificial Homeostatic Hormone Systems (AHHS), which provide both intrinsic, homeostatic processes and (transient) intrinsic, variant behavior. By using AHHS the need for pre-defined controller topologies or information about the field of application is minimized. We investigate how the principle design of the controller and the hormone network size affects the overall performance of the artificial evolution (i.e., evolvability). This is done by comparing two variants of AHHS that show different effects when mutated. We evolve a controller for a robot built from five autonomous, cooperating modules. The desired behavior is a form of gait resulting in fast locomotion by using the modules' main hinges.
Decision Problems for Petri Nets with Names
Venue: arXiv cs.LO 2010
Year: 2010

We prove several decidability and undecidability results for nu-PN, an extension of P/T nets with pure name creation and name management. We give a simple proof of undecidability of reachability, by reducing reachability in nets with inhibitor arcs to it. Thus, the expressive power of nu-PN strictly surpasses that of P/T nets. We prove that nu-PN are Well Structured Transition Systems. In particular, we obtain decidability of coverability and termination, so that the expressive power of Turing machines is not reached. Moreover, they are strictly Well Structured, so that the boundedness problem is also decidable. We consider two properties, width-boundedness and depth-boundedness, that factorize boundedness. Width-boundedness has already been proven to be decidable. We prove here undecidability of depth-boundedness. Finally, we obtain Ackermann-hardness results for all our decidable decision problems.
The Use of Rapid Digital Game Creation to Learn Computational Thinking
Venue: arXiv cs.OH 2010
Year: 2010

Computational Thinking (CT) has been described as a universally applicable ability such as reading and writing. In this paper, we describe an innovative pedagogy using Rapid Digital Game Creation (RDGC) for learning CT skills. RDGC involves the rapid building of digital games with high-level software that requires little or no programming knowledge. We analyze how RDGC supports various CT concepts and how it may be mapped to equivalent Java concepts by building the same game using both RDGC and Java. We discuss the potential benefits of this approach for attracting computing majors, as a precursor to learning formal programming languages, for learning domain knowledge, and for bridging the digital divide. We present the implications of this work for teachers and researchers.
On Constructive Connectives and Systems
Venue: arXiv cs.LO 2010
Year: 2010

Canonical inference rules and canonical systems are defined in the framework of non-strict single-conclusion sequent systems, in which the succeedents of sequents can be empty. Important properties of this framework are investigated, and a general non-deterministic Kripke-style semantics is provided. This general semantics is then used to provide a constructive (and very natural), sufficient and necessary coherence criterion for the validity of the strong cut-elimination theorem in such a system. These results suggest new syntactic and semantic characterizations of basic constructive connectives.
A New Algorithm for General Cyclic Heptadiagonal Linear Systems Using Sherman-Morrison-Woodbury formula
Venue: arXiv cs.NA 2010
Year: 2010

In this paper, a new efficient computational algorithm is presented for solving cyclic heptadiagonal linear systems based on using of heptadiagonal linear solver and Sherman-Morrison-Woodbury formula. The implementation of the algorithm using computer algebra systems (CAS) such as MAPLE and MATLAB is straightforward. Numerical example is presented for the sake of illustration.
Opinion Polarity Identification through Adjectives
Venue: arXiv cs.CL 2010
Year: 2010

"What other people think" has always been an important piece of information during various decision-making processes. Today people frequently make their opinions available via the Internet, and as a result, the Web has become an excellent source for gathering consumer opinions. There are now numerous Web resources containing such opinions, e.g., product reviews forums, discussion groups, and Blogs. But, due to the large amount of information and the wide range of sources, it is essentially impossible for a customer to read all of the reviews and make an informed decision on whether to purchase the product. It is also difficult for the manufacturer or seller of a product to accurately monitor customer opinions. For this reason, mining customer reviews, or opinion mining, has become an important issue for research in Web information extraction. One of the important topics in this research area is the identification of opinion polarity. The opinion polarity of a review is usually expressed with values 'positive', 'negative' or 'neutral'. We propose a technique for identifying polarity of reviews by identifying the polarity of the adjectives that appear in them. Our evaluation shows the technique can provide accuracy in the area of 73%, which is well above the 58%-64% provided by naive Bayesian classifiers.
Analysis of attractor distances in Random Boolean Networks
Venue: arXiv cs.NE 2010
Year: 2010

We study the properties of the distance between attractors in Random Boolean Networks, a prominent model of genetic regulatory networks. We define three distance measures, upon which attractor distance matrices are constructed and their main statistic parameters are computed. The experimental analysis shows that ordered networks have a very clustered set of attractors, while chaotic networks' attractors are scattered; critical networks show, instead, a pattern with characteristics of both ordered and chaotic networks.
Gaussian Relay Channel Capacity to Within a Fixed Number of Bits
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we show that the capacity of the three-node Gaussian relay channel can be achieved to within 1 and 2 bit/sec/Hz using compress-and-forward and amplify-and-forward relaying, respectively.
On conditional coloring of some graphs
Venue: arXiv cs.DM 2010
Year: 2010

For integers r and k > 0(k>r),a conditional (k, r)-coloring of a graph G is a proper k-coloring of G such that every vertex v of G has at least min{r,d(v)} differently colored neighbors, where d(v) is the degree of v. In this note, for different values of r we obtain the conditional chromatic number of a grid $G(2,n) \cong P_2 \ \Box \ P_n$, $C_n^2$ and the strong product of $P_n$ and $P_m$ (n,m being positive integers). Also, for integers $n \geq 3$ and $t \geq 1$ the second order conditional chromatic number (also known as dynamic chromatic number) of the (t,n)-web graph is obtained.
Distributed Graph Coloring: An Approach Based on the Calling Behavior of Japanese Tree Frogs
Venue: arXiv cs.AI 2010
Year: 2010

Graph coloring, also known as vertex coloring, considers the problem of assigning colors to the nodes of a graph such that adjacent nodes do not share the same color. The optimization version of the problem concerns the minimization of the number of used colors. In this paper we deal with the problem of finding valid colorings of graphs in a distributed way, that is, by means of an algorithm that only uses local information for deciding the color of the nodes. Such algorithms prescind from any central control. Due to the fact that quite a few practical applications require to find colorings in a distributed way, the interest in distributed algorithms for graph coloring has been growing during the last decade. As an example consider wireless ad-hoc and sensor networks, where tasks such as the assignment of frequencies or the assignment of TDMA slots are strongly related to graph coloring. The algorithm proposed in this paper is inspired by the calling behavior of Japanese tree frogs. Male frogs use their calls to attract females. Interestingly, groups of males that are located nearby each other desynchronize their calls. This is because female frogs are only able to correctly localize the male frogs when their calls are not too close in time. We experimentally show that our algorithm is very competitive with the current state of the art, using different sets of problem instances and comparing to one of the most competitive algorithms from the literature.
A system for coarse-grained location-based synchronisation
Venue: arXiv cs.HC 2010
Year: 2010

This paper describes a system for supporting coarse-grained location-based synchronisation. This type of synchronisation may occur when people need only some awareness about the location of others within the specific context of an on-going activity. We have identified a number of reference scenarios for this type of synchronisation and we have implemented and deployed a prototype to evaluate the type of support provided. The results of the evaluation suggest a good acceptance of the overall concept, indicating that this might be a valuable approach for many of the indicated scenarios, possibly replacing or complementing existing synchronisation practices.
Using Evolution Strategy with Meta-models for Well Placement Optimization
Venue: arXiv cs.CE 2010
Year: 2010

Optimum implementation of non-conventional wells allows us to increase considerably hydrocarbon recovery. By considering the high drilling cost and the potential improvement in well productivity, well placement decision is an important issue in field development. Considering complex reservoir geology and high reservoir heterogeneities, stochastic optimization methods are the most suitable approaches for optimum well placement. This paper proposes an optimization methodology to determine optimal well location and trajectory based upon the Covariance Matrix Adaptation - Evolution Strategy (CMA-ES) which is a variant of Evolution Strategies recognized as one of the most powerful derivative-free optimizers for continuous optimization. To improve the optimization procedure, two new techniques are investigated: (1). Adaptive penalization with rejection is developed to handle well placement constraints. (2). A meta-model, based on locally weighted regression, is incorporated into CMA-ES using an approximate ranking procedure. Therefore, we can reduce the number of reservoir simulations, which are computationally expensive. Several examples are presented. Our new approach is compared with a Genetic Algorithm incorporating the Genocop III technique. It is shown that our approach outperforms the genetic algorithm: it leads in general to both a higher NPV and a significant reduction of the number of reservoir simulations.
Secure Index Coding with Side Information
Venue: arXiv cs.IT 2010
Year: 2010

Security aspects of the Index Coding with Side Information (ICSI) problem are investigated. Building on the results of Bar-Yossef et al. (2006), the properties of linear coding schemes for the ICSI problem are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the coding scheme for the ICSI problem based on a linear code C of length n, minimum distance d and dual distance d^\perp, is (d-1-t)-block secure (and hence also weakly secure) if the adversary knows in advance t \le d - 2 messages, and is completely insecure if the adversary knows in advance more than n - d^\perp messages.