OpenRaiser/Intern-Atlas huggingface dataset:
Partial Interference Alignment for K-user MIMO Interference Channels
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we consider a Partial Interference Alignment and Interference Detection (PIAID) design for $K$-user quasi-static MIMO interference channels with discrete constellation inputs. Each transmitter has M antennas and transmits L independent data streams to the desired receiver with N receive antennas. We focus on the case where not all K-1 interfering transmitters can be aligned at every receiver. As a result, there will be residual interference at each receiver that cannot be aligned. Each receiver detects and cancels the residual interference based on the constellation map. However, there is a window of unfavorable interference profile at the receiver for Interference Detection (ID). In this paper, we propose a low complexity Partial Interference Alignment scheme in which we dynamically select the user set for IA so as to create a favorable interference profile for ID at each receiver. We first derive the average symbol error rate (SER) by taking into account of the non-Guassian residual interference due to discrete constellation. Using graph theory, we then devise a low complexity user set selection algorithm for the PIAID scheme,which minimizes the asymptotically tight bound for the average end-to-end SER performance. Moreover, we substantially simplify interference detection at the receiver using Semi-Definite Relaxation (SDR) techniques. It is shown that the SER performance of the proposed PIAID scheme has significant gain compared with various conventional baseline solutions.
Connection and Dispersion of Computation
Venue: arXiv cs.LO 2011
Year: 2011

This paper talk about the influence of Connection and Dispersion on Computational Complexity. And talk about the HornCNF's connection and CNF's dispersion, and show the difference between CNFSAT and HornSAT. First, I talk the relation between MUC decision problem and classifying the truth value assignment. Second, I define the two inner products ("inner product" and "inner harmony") and talk about the influence of orthogonal and correlation to MUC. And we can not reduce MUC to Orthogonalization MUC by using HornMUC in polynomial size because HornMUC have high orthogonal of inner harmony and MUC do not. So DP is not P, and NP is not P.
Augmented Reality Implementation Methods in Mainstream Applications
Venue: arXiv cs.CV 2011
Year: 2011

Augmented reality has became an useful tool in many areas from space exploration to military applications. Although used theoretical principles are well known for almost a decade, the augmented reality is almost exclusively used in high budget solutions with a special hardware. However, in last few years we could see rising popularity of many projects focused on deployment of the augmented reality on different mobile devices. Our article is aimed on developers who consider development of an augmented reality application for the mainstream market. Such developers will be forced to keep the application price, therefore also the development price, at reasonable level. Usage of existing image processing software library could bring a significant cut-down of the development costs. In the theoretical part of the article is presented an overview of the augmented reality application structure. Further, an approach for selection appropriate library as well as the review of the existing software libraries focused in this area is described. The last part of the article outlines our implementation of key parts of the augmented reality application using the OpenCV library.
Writing on the Facade of RWTH ICT Cubes: Cost Constrained Geometric Huffman Coding
Venue: arXiv cs.IT 2011
Year: 2011

In this work, a coding technique called cost constrained Geometric Huffman coding (ccGhc) is developed. ccGhc minimizes the Kullback-Leibler distance between a dyadic probability mass function (pmf) and a target pmf subject to an affine inequality constraint. An analytical proof is given that when ccGhc is applied to blocks of symbols, the optimum is asymptotically achieved when the blocklength goes to infinity. The derivation of ccGhc is motivated by the problem of encoding a text to a sequence of slats subject to architectural design criteria. For the considered architectural problem, for a blocklength of 3, the codes found by ccGhc match the design criteria. For communications channels with average cost constraints, ccGhc can be used to efficiently find prefix-free modulation codes that are provably capacity achieving.
Distributed Interference Alignment with Low Overhead
Venue: arXiv cs.IT 2011
Year: 2011

Based on closed-form interference alignment (IA) solutions, a low overhead distributed interference alignment (LOIA) scheme is proposed in this paper for the $K$-user SISO interference channel, and extension to multiple antenna scenario is also considered. Compared with the iterative interference alignment (IIA) algorithm proposed by Gomadam et al., the overhead is greatly reduced. Simulation results show that the IIA algorithm is strictly suboptimal compared with our LOIA algorithm in the overhead-limited scenario.
Combining Explicit and Symbolic Approaches for Better On-the-Fly LTL Model Checking
Venue: arXiv cs.LO 2011
Year: 2011

We present two new hybrid techniques that replace the synchronized product used in the automata-theoretic approach for LTL model checking. The proposed products are explicit graphs of aggregates (symbolic sets of states) that can be interpreted as Büchi automata. These hybrid approaches allow on the one hand to use classical emptiness-check algorithms and build the graph on-the-fly, and on the other hand, to have a compact encoding of the state space thanks to the symbolic representation of the aggregates. The Symbolic Observation Product assumes a globally stuttering property (e.g., LTL \ X) to aggregate states. The Self-Loop Aggregation Product} does not require the property to be globally stuttering (i.e., it can tackle full LTL), but dynamically detects and exploits a form of stuttering where possible. Our experiments show that these two variants, while incomparable with each other, can outperform other existing approaches.
Algorithms for Solving Rubik's Cubes
Venue: arXiv cs.DS 2011
Year: 2011

The Rubik's Cube is perhaps the world's most famous and iconic puzzle, well-known to have a rich underlying mathematical structure (group theory). In this paper, we show that the Rubik's Cube also has a rich underlying algorithmic structure. Specifically, we show that the n x n x n Rubik's Cube, as well as the n x n x 1 variant, has a "God's Number" (diameter of the configuration space) of Theta(n^2/log n). The upper bound comes from effectively parallelizing standard Theta(n^2) solution algorithms, while the lower bound follows from a counting argument. The upper bound gives an asymptotically optimal algorithm for solving a general Rubik's Cube in the worst case. Given a specific starting state, we show how to find the shortest solution in an n x O(1) x O(1) Rubik's Cube. Finally, we show that finding this optimal solution becomes NP-hard in an n x n x 1 Rubik's Cube when the positions and colors of some of the cubies are ignored (not used in determining whether the cube is solved).
A Dirty Model for Multiple Sparse Regression
Venue: arXiv cs.LG 2011
Year: 2011

Sparse linear regression -- finding an unknown vector from linear measurements -- is now known to be possible with fewer samples than variables, via methods like the LASSO. We consider the multiple sparse linear regression problem, where several related vectors -- with partially shared support sets -- have to be recovered. A natural question in this setting is whether one can use the sharing to further decrease the overall number of samples required. A line of recent research has studied the use of \ell_1/\ell_q norm block-regularizations with q>1 for such problems; however these could actually perform worse in sample complexity -- vis a vis solving each problem separately ignoring sharing -- depending on the level of sharing. We present a new method for multiple sparse linear regression that can leverage support and parameter overlap when it exists, but not pay a penalty when it does not. A very simple idea: we decompose the parameters into two components and regularize these differently. We show both theoretically and empirically, our method strictly and noticeably outperforms both \ell_1 or \ell_1/\ell_q methods, over the entire range of possible overlaps (except at boundary cases, where we match the best method). We also provide theoretical guarantees that the method performs well under high-dimensional scaling.
An Architectural Model for a Grid based Workflow Management Platform in Scientific Applications
Venue: arXiv cs.DC 2011
Year: 2011

With recent increasing computational and data requirements of scientific applications, the use of large clustered systems as well as distributed resources is inevitable. Although executing large applications in these environments brings increased performance, the automation of the process becomes more and more challenging. While the use of complex workflow management systems has been a viable solution for this automation process in business oriented environments, the open source engines available for scientific applications lack some functionalities or are too difficult to use for non-specialists. In this work we propose an architectural model for a grid based workflow management platform providing features like an intuitive way to describe workflows, efficient data handling mechanisms and flexible fault tolerance support. Our integrated solution introduces a workflow engine component based on ActiveBPEL extended with additional functionalities and a scheduling component providing efficient mapping between tasks and available resources.
Implementing Human-like Intuition Mechanism in Artificial Intelligence
Venue: arXiv cs.AI 2011
Year: 2011

Human intuition has been simulated by several research projects using artificial intelligence techniques. Most of these algorithms or models lack the ability to handle complications or diversions. Moreover, they also do not explain the factors influencing intuition and the accuracy of the results from this process. In this paper, we present a simple series based model for implementation of human-like intuition using the principles of connectivity and unknown entities. By using Poker hand datasets and Car evaluation datasets, we compare the performance of some well-known models with our intuition model. The aim of the experiment was to predict the maximum accurate answers using intuition based models. We found that the presence of unknown entities, diversion from the current problem scenario, and identifying weakness without the normal logic based execution, greatly affects the reliability of the answers. Generally, the intuition based models cannot be a substitute for the logic based mechanisms in handling such problems. The intuition can only act as a support for an ongoing logic based model that processes all the steps in a sequential manner. However, when time and computational cost are very strict constraints, this intuition based model becomes extremely important and useful, because it can give a reasonably good performance. Factors affecting intuition are analyzed and interpreted through our model.
Image denoising assessment using anisotropic stack filtering
Venue: arXiv cs.CV 2011
Year: 2011

In this paper we propose a measure of anisotropy as a quality parameter to estimate the amount of noise in noisy images. The anisotropy of an image can be determined through a directional measure, using an appropriate statistical distribution of the information contained in the image. This new measure is achieved through a stack filtering paradigm. First, we define a local directional entropy, based on the distribution of 0's and 1's in the neigborhood of every pixel location of each stack level. Then the entropy variation of this directional entropy is used to define an anisotropic measure. The empirical results have shown that this measure can be regarded as an excellent image noise indicator, which is particularly relevant for quality assessment of denoising algorithms. The method has been evaluated with artificial and real-world degraded images.
From Cognitive Binary Logic to Cognitive Intelligent Agents
Venue: arXiv cs.AI 2011
Year: 2011

The relation between self awareness and intelligence is an open problem these days. Despite the fact that self awarness is usually related to Emotional Intelligence, this is not the case here. The problem described in this paper is how to model an agent which knows (Cognitive) Binary Logic and which is also able to pass (without any mistake) a certain family of Turing Tests designed to verify its knowledge and its discourse about the modal states of truth corresponding to well-formed formulae within the language of Propositional Binary Logic.
Simulation Framework for Modeling Large-Scale Distributed Systems
Venue: arXiv cs.DC 2011
Year: 2011

Simulation has become the evaluation method of choice for many areas of distributing computing research. However, most existing simulation packages have several limitations on the size and complexity of the system being modeled. Fine grained simulation of complex systems such as Grids requires high computational effort which can only be obtained by using an underlying distributed architecture. We are proposing a new distributed simulation system that has the advantage of being able to model very complex distributed systems while hiding the computational effort from the end-user.
Operations on polytopes: application to tolerance analysis
Venue: arXiv cs.CG 2011
Year: 2011

This article presents numerical methods in order to solve problems of tolerance analysis. A geometric specification, a contact specification and a functional requirement can be respectively characterized by a finite set of geometric constraints, a finite set of contact constraints and a finite set of functional constraints. Mathematically each constraint formalises a n-face (hyperplan of dimension n) of a n-polytope (1 {\leq} n {\leq} 6). Thus the relative position between two any surfaces of a mechanism can be calculated with two operations on polytopes : the Minkowski sum and the Intersection. The result is a new polytope: the calculated polytope. The inclusion of the calculated polytope inside the functional polytope indicates if the functional requirement is satisfied or not satisfied. Examples illustrate these numerical methods.
Visual Secret Sharing Scheme using Grayscale Images
Venue: arXiv cs.CR 2011
Year: 2011

Pixel expansion and the quality of the reconstructed secret image has been a major issue of visual secret sharing (VSS) schemes. A number of probabilistic VSS schemes with minimum pixel expansion have been proposed for black and white (binary) secret images. This paper presents a probabilistic (2, 3)-VSS scheme for gray scale images. Its pixel expansion is larger in size but the quality of the image is perfect when it's reconstructed. The construction of the shadow images (transparent shares) is based on the binary OR operation.
Automaton based detection of affected cells in three dimensional biological system
Venue: arXiv cs.CE 2011
Year: 2011

The aim of this research review is to propose the logic and search mechanism for the development of an artificially intelligent automaton (AIA) that can find affected cells in a 3-dimensional biological system. Research on the possible application of such automatons to detect and control cancer cells in the human body are greatly focused MRI and PET scans finds the affected regions at the tissue level even as we can find the affected regions at the cellular level using the framework. The AIA may be designed to ensure optimum utilization as they record and might control the presence of affected cells in a human body. The proposed models and techniques can be generalized and used in any application where cells are injured or affected by some disease or accident. The best method to import AIA into the body without surgery or injection is to insert small pill like automata, carrying material viz drugs or leukocytes that is needed to correct the infection. In this process, the AIA can be compared to nano pills to deliver or support therapy. NanoHive simulation software was used to validate the framework of this paper. The existing nanomedicine models such as obstacle avoidance algorithm based models (Hla K H S et al 2008) and the framework in this model were tested in different simulation based experiments. The existing models such as obstacle avoidance based models failed in complex environmental conditions (such as changing environmental conditions, presence of semi-solid particles, etc) while the model in this paper executed its framework successfully.Come systems biology, this field of automatons deserves a bigger leap of understanding especially when pharmacogenomics is at its peak. The results also indicate the importance of artificial intelligence and other computational capabilities in the proposed model for the successful detection of affected cells.
Learning to Order BDD Variables in Verification
Venue: arXiv cs.AI 2011
Year: 2011

The size and complexity of software and hardware systems have significantly increased in the past years. As a result, it is harder to guarantee their correct behavior. One of the most successful methods for automated verification of finite-state systems is model checking. Most of the current model-checking systems use binary decision diagrams (BDDs) for the representation of the tested model and in the verification process of its properties. Generally, BDDs allow a canonical compact representation of a boolean function (given an order of its variables). The more compact the BDD is, the better performance one gets from the verifier. However, finding an optimal order for a BDD is an NP-complete problem. Therefore, several heuristic methods based on expert knowledge have been developed for variable ordering. We propose an alternative approach in which the variable ordering algorithm gains 'ordering experience' from training models and uses the learned knowledge for finding good orders. Our methodology is based on offline learning of pair precedence classifiers from training models, that is, learning which variable pair permutation is more likely to lead to a good order. For each training model, a number of training sequences are evaluated. Every training model variable pair permutation is then tagged based on its performance on the evaluated orders. The tagged permutations are then passed through a feature extractor and are given as examples to a classifier creation algorithm. Given a model for which an order is requested, the ordering algorithm consults each precedence classifier and constructs a pair precedence table which is used to create the order. Our algorithm was integrated with SMV, which is one of the most widely used verification systems. Preliminary empirical evaluation of our methodology, using real benchmark models, shows performance that is better than random ordering and is competitive with existing algorithms that use expert knowledge. We believe that in sub-domains of models (alu, caches, etc.) our system will prove even more valuable. This is because it features the ability to learn sub-domain knowledge, something that no other ordering algorithm does.
Taming Numbers and Durations in the Model Checking Integrated Planning System
Venue: arXiv cs.AI 2011
Year: 2011

The Model Checking Integrated Planning System (MIPS) is a temporal least commitment heuristic search planner based on a flexible object-oriented workbench architecture. Its design clearly separates explicit and symbolic directed exploration algorithms from the set of on-line and off-line computed estimates and associated data structures. MIPS has shown distinguished performance in the last two international planning competitions. In the last event the description language was extended from pure propositional planning to include numerical state variables, action durations, and plan quality objective functions. Plans were no longer sequences of actions but time-stamped schedules. As a participant of the fully automated track of the competition, MIPS has proven to be a general system; in each track and every benchmark domain it efficiently computed plans of remarkable quality. This article introduces and analyzes the most important algorithmic novelties that were necessary to tackle the new layers of expressiveness in the benchmark problems and to achieve a high level of performance. The extensions include critical path analysis of sequentially generated plans to generate corresponding optimal parallel plans. The linear time algorithm to compute the parallel plan bypasses known NP hardness results for partial ordering by scheduling plans with respect to the set of actions and the imposed precedence relations. The efficiency of this algorithm also allows us to improve the exploration guidance: for each encountered planning state the corresponding approximate sequential plan is scheduled. One major strength of MIPS is its static analysis phase that grounds and simplifies parameterized predicates, functions and operators, that infers knowledge to minimize the state description length, and that detects domain object symmetries. The latter aspect is analyzed in detail. MIPS has been developed to serve as a complete and optimal state space planner, with admissible estimates, exploration engines and branching cuts. In the competition version, however, certain performance compromises had to be made, including floating point arithmetic, weighted heuristic search exploration according to an inadmissible estimate and parameterized optimization.
A Personalized System for Conversational Recommendations
Venue: arXiv cs.IR 2011
Year: 2011

Searching for and making decisions about information is becoming increasingly difficult as the amount of information and number of choices increases. Recommendation systems help users find items of interest of a particular type, such as movies or restaurants, but are still somewhat awkward to use. Our solution is to take advantage of the complementary strengths of personalized recommendation systems and dialogue systems, creating personalized aides. We present a system -- the Adaptive Place Advisor -- that treats item selection as an interactive, conversational process, with the program inquiring about item attributes and the user responding. Individual, long-term user preferences are unobtrusively obtained in the course of normal recommendation dialogues and used to direct future conversations with the same user. We present a novel user model that influences both item search and the questions asked during a conversation. We demonstrate the effectiveness of our system in significantly reducing the time and number of interactions required to find a satisfactory item, as compared to a control group of users interacting with a non-adaptive version of the system.