OpenRaiser/Intern-Atlas huggingface dataset:
Communication-Based Decomposition Mechanisms for Decentralized MDPs
Venue: arXiv cs.AI 2011
Year: 2011

Multi-agent planning in stochastic environments can be framed formally as a decentralized Markov decision problem. Many real-life distributed problems that arise in manufacturing, multi-robot coordination and information gathering scenarios can be formalized using this framework. However, finding the optimal solution in the general case is hard, limiting the applicability of recently developed algorithms. This paper provides a practical approach for solving decentralized control problems when communication among the decision makers is possible, but costly. We develop the notion of communication-based mechanism that allows us to decompose a decentralized MDP into multiple single-agent problems. In this framework, referred to as decentralized semi-Markov decision process with direct communication (Dec-SMDP-Com), agents operate separately between communications. We show that finding an optimal mechanism is equivalent to solving optimally a Dec-SMDP-Com. We also provide a heuristic search algorithm that converges on the optimal decomposition. Restricting the decomposition to some specific types of local behaviors reduces significantly the complexity of planning. In particular, we present a polynomial-time algorithm for the case in which individual agents perform goal-oriented behaviors between communications. The paper concludes with an additional tractable algorithm that enables the introduction of human knowledge, thereby reducing the overall problem to finding the best time to communicate. Empirical results show that these approaches provide good approximate solutions.
Nominal Logic with Equations Only
Venue: arXiv cs.LO 2011
Year: 2011

Many formal systems, particularly in computer science, may be captured by equations modulated by side conditions asserting the "freshness of names"; these can be reasoned about with Nominal Equational Logic (NEL). Like most logics of this sort NEL employs this notion of freshness as a first class logical connective. However, this can become inconvenient when attempting to translate results from standard equational logic to the nominal setting. This paper presents proof rules for a logic whose only connectives are equations, which we call Nominal Equation-only Logic (NEoL). We prove that NEoL is just as expressive as NEL. We then give a simple description of equality in the empty NEoL-theory, then extend that result to describe freshness in the empty NEL-theory.
Swayed by Friends or by the Crowd?
Venue: arXiv cs.SI 2011
Year: 2011

We have conducted three empirical studies of the effects of friend recommendations and general ratings on how online users make choices. These two components of social influence were investigated through user studies on Mechanical Turk. We find that for a user deciding between two choices an additional rating star has a much larger effect than an additional friend's recommendation on the probability of selecting an item. Equally important, negative opinions from friends are more influential than positive opinions, and people exhibit more random behavior in their choices when the decision involves less cost and risk. Our results can be generalized across different demographics, implying that individuals trade off recommendations from friends and ratings in a similar fashion.
PKind: A parallel k-induction based model checker
Venue: arXiv cs.LO 2011
Year: 2011

PKind is a novel parallel k-induction-based model checker of invariant properties for finite- or infinite-state Lustre programs. Its architecture, which is strictly message-based, is designed to minimize synchronization delays and easily accommodate the incorporation of incremental invariant generators to enhance basic k-induction. We describe PKind's functionality and main features, and present experimental evidence that PKind significantly speeds up the verification of safety properties and, due to incremental invariant generation, also considerably increases the number of provable ones.
Equational theories of profinite structures
Venue: arXiv cs.FL 2011
Year: 2011

In this paper we consider a general way of constructing profinite struc- tures based on a given framework - a countable family of objects and a countable family of recognisers (e.g. formulas). The main theorem states: A subset of a family of recognisable sets is a lattice if and only if it is definable by a family of profinite equations. This result extends Theorem 5.2 from [GGEP08] expressed only for finite words and morphisms to finite monoids. One of the applications of our theorem is the situation where objects are finite relational structures and recognisers are first order sentences. In that setting a simple characterisation of lattices of first order formulas arise.
An achievable region for the double unicast problem based on a minimum cut analysis
Venue: arXiv cs.IT 2011
Year: 2011

We consider the multiple unicast problem under network coding over directed acyclic networks when there are two source-terminal pairs, $s_1-t_1$ and $s_2-t_2$. Current characterizations of the multiple unicast capacity region in this setting have a large number of inequalities, which makes them hard to explicitly evaluate. In this work we consider a slightly different problem. We assume that we only know certain minimum cut values for the network, e.g., mincut$(S_i, T_j)$, where $S_i \subseteq \{s_1, s_2\}$ and $T_j \subseteq \{t_1, t_2\}$ for different subsets $S_i$ and $T_j$. Based on these values, we propose an achievable rate region for this problem based on linear codes. Towards this end, we begin by defining a base region where both sources are multicast to both the terminals. Following this we enlarge the region by appropriately encoding the information at the source nodes, such that terminal $t_i$ is only guaranteed to decode information from the intended source $s_i$, while decoding a linear function of the other source. The rate region takes different forms depending upon the relationship of the different cut values in the network.
Partial Redundancy Elimination for Multi-threaded Programs
Venue: arXiv cs.SE 2011
Year: 2011

Multi-threaded programs have many applications which are widely used such as operating systems. Analyzing multi-threaded programs differs from sequential ones; the main feature is that many threads execute at the same time. The effect of all other running threads must be taken in account. Partial redundancy elimination is among the most powerful compiler optimizations: it performs loop-invariant code motion and common subexpression elimination. We present a type system with optimization component which performs partial redundancy elimination for multi-threaded programs.
Efficient Network for Non-Binary QC-LDPC Decoder
Venue: arXiv cs.AR 2011
Year: 2011

This paper presents approaches to develop efficient network for non-binary quasi-cyclic LDPC (QC-LDPC) decoders. By exploiting the intrinsic shifting and symmetry properties of the check matrices, significant reduction of memory size and routing complexity can be achieved. Two different efficient network architectures for Class-I and Class-II non-binary QC-LDPC decoders have been proposed, respectively. Comparison results have shown that for the code of the 64-ary (1260, 630) rate-0.5 Class-I code, the proposed scheme can save more than 70.6% hardware required by shuffle network than the state-of-the-art designs. The proposed decoder example for the 32-ary (992, 496) rate-0.5 Class-II code can achieve a 93.8% shuffle network reduction compared with the conventional ones. Meanwhile, based on the similarity of Class-I and Class-II codes, similar shuffle network is further developed to incorporate both classes of codes at a very low cost.
Low-Latency SC Decoder Architectures for Polar Codes
Venue: arXiv cs.AR 2011
Year: 2011

Nowadays polar codes are becoming one of the most favorable capacity achieving error correction codes for their low encoding and decoding complexity. However, due to the large code length required by practical applications, the few existing successive cancellation (SC) decoder implementations still suffer from not only the high hardware cost but also the long decoding latency. This paper presents novel several approaches to design low-latency decoders for polar codes based on look-ahead techniques. Look-ahead techniques can be employed to reschedule the decoding process of polar decoder in numerous approaches. However, among those approaches, only well-arranged ones can achieve good performance in terms of both latency and hardware complexity. By revealing the recurrence property of SC decoding chart, the authors succeed in reducing the decoding latency by 50% with look-ahead techniques. With the help of VLSI-DSP design techniques such as pipelining, folding, unfolding, and parallel processing, methodologies for four different polar decoder architectures have been proposed to meet various application demands. Sub-structure sharing scheme has been adopted to design the merged processing element (PE) for further hardware reduction. In addition, systematic methods for construction refined pipelining decoder (2nd design) and the input generating circuits (ICG) block have been given. Detailed gate-level analysis has demonstrated that the proposed designs show latency advantages over conventional ones with similar hardware cost.
Sparsity and Robustness in Face Recognition
Venue: arXiv cs.CV 2011
Year: 2011

This report concerns the use of techniques for sparse signal representation and sparse error correction for automatic face recognition. Much of the recent interest in these techniques comes from the paper "Robust Face Recognition via Sparse Representation" by Wright et al. (2009), which showed how, under certain technical conditions, one could cast the face recognition problem as one of seeking a sparse representation of a given input face image in terms of a "dictionary" of training images and images of individual pixels. In this report, we have attempted to clarify some frequently encountered questions about this work and particularly, on the validity of using sparse representation techniques for face recognition.
A robust, low-cost approach to Face Detection and Face Recognition
Venue: arXiv cs.CV 2011
Year: 2011

In the domain of Biometrics, recognition systems based on iris, fingerprint or palm print scans etc. are often considered more dependable due to extremely low variance in the properties of these entities with respect to time. However, over the last decade data processing capability of computers has increased manifold, which has made real-time video content analysis possible. This shows that the need of the hour is a robust and highly automated Face Detection and Recognition algorithm with credible accuracy rate. The proposed Face Detection and Recognition system using Discrete Wavelet Transform (DWT) accepts face frames as input from a database containing images from low cost devices such as VGA cameras, webcams or even CCTV's, where image quality is inferior. Face region is then detected using properties of L*a*b* color space and only Frontal Face is extracted such that all additional background is eliminated. Further, this extracted image is converted to grayscale and its dimensions are resized to 128 x 128 pixels. DWT is then applied to entire image to obtain the coefficients. Recognition is carried out by comparison of the DWT coefficients belonging to the test image with those of the registered reference image. On comparison, Euclidean distance classifier is deployed to validate the test image from the database. Accuracy for various levels of DWT Decomposition is obtained and hence, compared.
On Three Challenges of Artificial Living Systems and Embodied Evolution
Venue: arXiv cs.RO 2011
Year: 2011

Creating autonomous, self-supporting, self-replicating, sustainable systems is a great challenge. To some extent, understanding life means not only being able to create it from scratch, but also improving, supporting, saving it, or even making it even more advanced. This can be thought of as a long-term goal of living technologies and embodied evolution. Current research agenda targets several short- and middle-term steps towards achieving such a vision: connection of ICT and bio-/chemo- developments, advances in "soft" and "wet" robotics, integration of material science into developmental robotics, and potentially, addressing the self-replication in autonomous systems.
An architecture for "Web Of Things" using SOCKS protocol based IPv6/IPv4 gatewaying for heterogeneous communication
Venue: arXiv cs.NI 2011
Year: 2011

"Web Of Things" evolved from "Internet Of Things". Lot of research has been done in designing architecture for "Web Of Things". Two main architectures are Smart gateway based architecture and embedded Web Server based architecture. These architectures address some of the basic and essential issues relating to Service Oriented Architecture for "Web Of Things". Taking into consideration the period of coexistence of IPv4 and IPv6 we propose an architecture using SOCKS protocol based IPv6/IPv4 gatewaying and refinements which facilitates smooth heterogeneous communications between the IPv6 and IPv4 enabled embedded nodes and can potentially be used to prevent security threats like Denial-of-Service (DoS) attacks on embedded devices attached to the web and increase its performance. Our architecture provides a way for caching responses from device and thereby increasing its efficiency and performance and yielding quick response times.
Two Classes of Crooked Multinomials Inequivalent to Power Functions
Venue: arXiv cs.CR 2011
Year: 2011

It is known that crooked functions can be used to construct many interesting combinatorial objects, and a quadratic function is crooked if and only if it is almost perfect nonlinear (APN). In this paper, we introduce two infinite classes of quadratic crooked multinomials on fields of order $2^{2m}$. One class of APN functions constructed in [7] is a particular case of the one we construct in Theorem 1. Moreover, we prove that the two classes of crooked functions constructed in this paper are EA inequivalent to power functions and conjecture that CCZ inequivalence between them also holds.
Promoting Industry-University Partnership in Information Technology
Venue: arXiv cs.CY 2011
Year: 2011

It is becoming increasingly difficult for Nigerian universities to go it alone in terms of serving as a citadel of learning, coping with the huge wage bill and competing with their peers in other parts of the world, due to competitive, economic and other pressures. As a consequence, Nigerian universities are left with no option than to carry their industrial partners along in terms of research and development through the formation of partnerships for their mutual benefit. Since the industries are established for profit making and the universities for knowledge enhancement, such partnerships would help in spreading the costs in terms of provision of knowledge and costs of research. This paper discusses the various types of partnerships involving industries and universities, the benefits derived and a possible model for the working of such a partnership which could be adapted to other sectors and countries in sub-Saharan Africa.
The Gathering Problem for Two Oblivious Robots with Unreliable Compasses
Venue: arXiv cs.DC 2011
Year: 2011

Anonymous mobile robots are often classified into synchronous, semi-synchronous and asynchronous robots when discussing the pattern formation problem. For semi-synchronous robots, all patterns formable with memory are also formable without memory, with the single exception of forming a point (i.e., the gathering) by two robots. However, the gathering problem for two semi-synchronous robots without memory is trivially solvable when their local coordinate systems are consistent, and the impossibility proof essentially uses the inconsistencies in their coordinate systems. Motivated by this, this paper investigates the magnitude of consistency between the local coordinate systems necessary and sufficient to solve the gathering problem for two oblivious robots under semi-synchronous and asynchronous models. To discuss the magnitude of consistency, we assume that each robot is equipped with an unreliable compass, the bearings of which may deviate from an absolute reference direction, and that the local coordinate system of each robot is determined by its compass. We consider two families of unreliable compasses, namely,static compasses with constant bearings, and dynamic compasses the bearings of which can change arbitrarily. For each of the combinations of robot and compass models, we establish the condition on deviation ϕthat allows an algorithm to solve the gathering problem, where the deviation is measured by the largest angle formed between the x-axis of a compass and the reference direction of the global coordinate system: ϕ< π/2 for semi-synchronous and asynchronous robots with static compasses, ϕ< π/4 for semi-synchronous robots with dynamic compasses, and ϕ< π/6 for asynchronous robots with dynamic compasses. Except for asynchronous robots with dynamic compasses, these sufficient conditions are also necessary.
Semantic Grounding Strategies for Tagbased Recommender Systems
Venue: arXiv cs.IR 2011
Year: 2011

Recommender systems usually operate on similarities between recommended items or users. Tag based recommender systems utilize similarities on tags. The tags are however mostly free user entered phrases. Therefore, similarities computed without their semantic groundings might lead to less relevant recommendations. In this paper, we study a semantic grounding used for tag similarity calculus. We show a comprehensive analysis of semantic grounding given by 20 ontologies from different domains. The study besides other things reveals that currently available OWL ontologies are very narrow and the percentage of the similarity expansions is rather small. WordNet scores slightly better as it is broader but not much as it does not support several semantic relationships. Furthermore, the study reveals that even with such number of expansions, the recommendations change considerably.
Design and Validation of Safety Cruise Control System for Automobiles
Venue: arXiv cs.SE 2011
Year: 2011

In light of the recent humongous growth of the human population worldwide, there has also been a voluminous and uncontrolled growth of vehicles, which has consequently increased the number of road accidents to a large extent. In lieu of a solution to the above mentioned issue, our system is an attempt to mitigate the same using synchronous programming language. The aim is to develop a safety crash warning system that will address the rear end crashes and also take over the controlling of the vehicle when the threat is at a very high level. Adapting according to the environmental conditions is also a prominent feature of the system. Safety System provides warnings to drivers to assist in avoiding rear-end crashes with other vehicles. Initially the system provides a low level alarm and as the severity of the threat increases the level of warnings or alerts also rises. At the highest level of threat, the system enters in a Cruise Control Mode, wherein the system controls the speed of the vehicle by controlling the engine throttle and if permitted, the brake system of the vehicle. We focus on this crash area as it has a very high percentage of the crash-related fatalities. To prove the feasibility, robustness and reliability of the system, we have also proved some of the properties of the system using temporal logic along with a reference implementation in ESTEREL. To bolster the same, we have formally verified various properties of the system along with their proofs.
Updatable Queue Protocol Based On TCP For Virtual Reality Environment
Venue: arXiv cs.NI 2011
Year: 2011

The variance in number and types of tasks required to be implemented within Distributed Virtual Environments (DVE) highlights the needs for communication protocols can achieve consistency. In addition, these applications have to handle an increasing number of participants and deal with the difficult problem of scalability. Moreover, the real-time requirements of these applications make the scalability problem more difficult to solve. In this paper, we have implemented Updatable Queue Abstraction protocol (UQA) on TCP (TCP-UQA) and compared it with original TCP, UDP, and Updatable Queue Abstraction based on UDP (UDP-UQA) protocols. Results showed that TCP-UQA was the best in queue management.
De-amortizing Binary Search Trees
Venue: arXiv cs.DS 2011
Year: 2011

We present a general method for de-amortizing essentially any Binary Search Tree (BST) algorithm. In particular, by transforming Splay Trees, our method produces a BST that has the same asymptotic cost as Splay Trees on any access sequence while performing each search in O(log n) worst case time. By transforming Multi-Splay Trees, we obtain a BST that is O(log log n) competitive, satisfies the scanning theorem, the static optimality theorem, the static finger theorem, the working set theorem, and performs each search in O(log n) worst case time. Moreover, we prove that if there is a dynamically optimal BST algorithm, then there is a dynamically optimal BST algorithm that answers every search in O(log n) worst case time.
Performance Analysis of LS and LMMSE Channel Estimation Techniques for LTE Downlink Systems
Venue: arXiv cs.NI 2011
Year: 2011

The main purpose of this paper is to study the performance of two linear channel estimators for LTE Downlink systems, the Least Square Error (LSE) and the Linear Minimum Mean Square Error (LMMSE). As LTE is a MIMO-OFDM based system, a cyclic prefix is inserted at the beginning of each transmitted OFDM symbol in order to completely suppress both inter-carrier interference (ICI) and inter-symbol interference (ISI). Usually, the cyclic prefix is equal to or longer than the channel length but in some cases and because of some unforeseen channel behaviour, the cyclic prefix can be shorter. Therefore, we propose to study the performance of the two linear estimators under the effect of the channel length. Computer simulations show that, in the case where the cyclic prefix is equal to or longer than the channel length,LMMSE performs better than LSE but at the cost of computational complexity.In the other case, LMMSE continue to improve its performance only for low SNR values but it degrades for high SNR values in which LS shows better performance for LTE Downlink systems. MATLAB Monte-Carlo simulations are used to evaluate the performance of the studied estimators in terms of Mean Square Error (MSE) and Bit Error Rate (BER) for 2x2 LTE Downlink systems.