OpenRaiser/Intern-Atlas huggingface dataset:
Symbol-Based Successive Cancellation List Decoder for Polar Codes
Venue: arXiv cs.IT 2014
Year: 2014

Polar codes is promising because they can provably achieve the channel capacity while having an explicit construction method. Lots of work have been done for the bit-based decoding algorithm for polar codes. In this paper, generalized symbol-based successive cancellation (SC) and SC list decoding algorithms are discussed. A symbol-based recursive channel combination relationship is proposed to calculate the symbol-based channel transition probability. This proposed method needs less additions than the maximum-likelihood decoder used by the existing symbol-based polar decoding algorithm. In addition, a two-stage list pruning network is proposed to simplify the list pruning network for the symbol-based SC list decoding algorithm.
Perceiving Motion Cues Inspired by Microsoft Kinect Sensor on Game Experiencing
Venue: arXiv cs.HC 2014
Year: 2014

This paper proposed a novel method to replace the traditional mouse controller by using Microsoft Kinect Sensor to realize the functional implementation on human-machine interaction. With human hand gestures and movements, Kinect Sensor could accurately recognize the participants intention and transmit our order to desktop or laptop. In addition, the trend in current HCI market is giving the customer more freedom and experiencing feeling by involving human cognitive factors more deeply. Kinect sensor receives the motion cues continuously from the humans intention and feedback the reaction during the experiments. The comparison accuracy between the hand movement and mouse cursor demonstrates the efficiency for the proposed method. In addition, the experimental results on hit rate in the game of Fruit Ninja and Shape Touching proves the real-time ability of the proposed framework. The performance evaluation built up a promise foundation for the further applications in the field of human-machine interaction. The contribution of this work is the expansion on hand gesture perception and early formulation on Mac iPad.
Towards A Theory-Of-Mind-Inspired Generic Decision-Making Framework
Venue: arXiv cs.AI 2014
Year: 2014

Simulation is widely used to make model-based predictions, but few approaches have attempted this technique in dynamic physical environments of medium to high complexity or in general contexts. After an introduction to the cognitive science concepts from which this work is inspired and the current development in the use of simulation as a decision-making technique, we propose a generic framework based on theory of mind, which allows an agent to reason and perform actions using multiple simulations of automatically created or externally inputted models of the perceived environment. A description of a partial implementation is given, which aims to solve a popular game within the IJCAI2013 AIBirds contest. Results of our approach are presented, in comparison with the competition benchmark. Finally, future developments regarding the framework are discussed.
On State Dependent Broadcast Channels with Cooperation
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we investigate problems of communication over physically degraded, state-dependent broadcast channels (BCs) with cooperating decoders. Two different setups are considered and their capacity regions are characterized. First, we study a setting in which one decoder can use a finite capacity link to send the other decoder information regarding the messages or the channel states. In this scenario we analyze two cases: one where noncausal state information is available to the encoder and the strong decoder and the other where state information is available only to the encoder in a causal manner. Second, we examine a setting in which the cooperation between the decoders is limited to taking place before the outputs of the channel are given. In this case, one decoder, which is informed of the state sequence noncausally, can cooperate only to send the other decoder rate-limited information about the state sequence. The proofs of the capacity regions introduce a new method of coding for channels with cooperation between different users, where we exploit the link between the decoders for multiple-binning. Finally, we discuss the optimality of using rate splitting techniques when coding for cooperative BCs. In particular, we show that rate splitting is not necessarily optimal when coding for cooperative BCs by solving an example in which our method of coding outperforms rate splitting.
Opposition Based ElectromagnetismLike for Global Optimization
Venue: arXiv cs.AI 2014
Year: 2014

Electromagnetismlike Optimization (EMO) is a global optimization algorithm, particularly well suited to solve problems featuring nonlinear and multimodal cost functions. EMO employs searcher agents that emulate a population of charged particles which interact to each other according to electromagnetisms laws of attraction and repulsion. However, EMO usually requires a large number of iterations for a local search procedure; any reduction or cancelling over such number, critically perturb other issues such as convergence, exploration, population diversity and accuracy. This paper presents an enhanced EMO algorithm called OBEMO, which employs the Opposition-Based Learning (OBL) approach to accelerate the global convergence speed. OBL is a machine intelligence strategy which considers the current candidate solution and its opposite value at the same time, achieving a faster exploration of the search space. The proposed OBEMO method significantly reduces the required computational effort yet avoiding any detriment to the good search capabilities of the original EMO algorithm. Experiments are conducted over a comprehensive set of benchmark functions, showing that OBEMO obtains promising performance for most of the discussed test problems.
Application of Multilayer Feedforward Neural Networks in Predicting Tree Height and Forest Stock Volume of Chinese Fir
Venue: arXiv cs.CE 2014
Year: 2014

Wood increment is critical information in forestry management. Previous studies used mathematics models to describe complex growing pattern of forest stand, in order to determine the dynamic status of growing forest stand in multiple conditions. In our research, we aimed at studying non-linear relationships to establish precise and robust Artificial Neural Networks (ANN) models to predict the precise values of tree height and forest stock volume based on data of Chinese fir. Results show that Multilayer Feedforward Neural Networks with 4 nodes (MLFN-4) can predict the tree height with the lowest RMS error (1.77); Multilayer Feedforward Neural Networks with 7 nodes (MLFN-7) can predict the forest stock volume with the lowest RMS error (4.95). The training and testing process have proved that our models are precise and robust.
Security Threats in MANETS : A Review
Venue: arXiv cs.NI 2014
Year: 2014

Ad hoc networks are the special networks formed for specific applications. Operating in ad-hoc mode allows all wireless devices within range of each other to discover and communicate in a peer-to-peer fashion without involving central access points. Many routing protocols like AODV, DSR etc have been proposed for these networks to find an end to end path between the nodes. These routing protocols are prone to attacks by the malicious nodes. There is a need to detect and prevent these attacks in a timely manner before destruction of network services.
Many-to-Many Matching Games for Proactive Social-Caching in Wireless Small Cell Networks
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we address the caching problem in small cell networks from a game theoretic point of view. In particular, we formulate the caching problem as a many-to-many matching game between small base stations and service providers' servers. The servers store a set of videos and aim to cache these videos at the small base stations in order to reduce the experienced delay by the end-users. On the other hand, small base stations cache the videos according to their local popularity, so as to reduce the load on the backhaul links. We propose a new matching algorithm for the many-to-many problem and prove that it reaches a pairwise stable outcome. Simulation results show that the number of satisfied requests by the small base stations in the proposed caching algorithm can reach up to three times the satisfaction of a random caching policy. Moreover, the expected download time of all the videos can be reduced significantly.
Towards an ASP-Based Architecture for Autonomous UAVs in Dynamic Environments (Extended Abstract)
Venue: arXiv cs.AI 2014
Year: 2014

Traditional AI reasoning techniques have been used successfully in many domains, including logistics, scheduling and game playing. This paper is part of a project aimed at investigating how such techniques can be extended to coordinate teams of unmanned aerial vehicles (UAVs) in dynamic environments. Specifically challenging are real-world environments where UAVs and other network-enabled devices must communicate to coordinate -- and communication actions are neither reliable nor free. Such network-centric environments are common in military, public safety and commercial applications, yet most research (even multi-agent planning) usually takes communications among distributed agents as a given. We address this challenge by developing an agent architecture and reasoning algorithms based on Answer Set Programming (ASP). Although ASP has been used successfully in a number of applications, to the best of our knowledge this is the first practical application of a complete ASP-based agent architecture. It is also the first practical application of ASP involving a combination of centralized reasoning, decentralized reasoning, execution monitoring, and reasoning about network communications.
Projective simulation applied to the grid-world and the mountain-car problem
Venue: arXiv cs.AI 2014
Year: 2014

We study the model of projective simulation (PS) which is a novel approach to artificial intelligence (AI). Recently it was shown that the PS agent performs well in a number of simple task environments, also when compared to standard models of reinforcement learning (RL). In this paper we study the performance of the PS agent further in more complicated scenarios. To that end we chose two well-studied benchmarking problems, namely the "grid-world" and the "mountain-car" problem, which challenge the model with large and continuous input space. We compare the performance of the PS agent model with those of existing models and show that the PS agent exhibits competitive performance also in such scenarios.
Target Tracking via Crowdsourcing: A Mechanism Design Approach
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, we propose a crowdsourcing based framework for myopic target tracking by designing an incentive-compatible mechanism based optimal auction in a wireless sensor network (WSN) containing sensors that are selfish and profit-motivated. For typical WSNs which have limited bandwidth, the fusion center (FC) has to distribute the total number of bits that can be transmitted from the sensors to the FC among the sensors. To accomplish the task, the FC conducts an auction by soliciting bids from the selfish sensors, which reflect how much they value their energy cost. Furthermore, the rationality and truthfulness of the sensors are guaranteed in our model. The final problem is formulated as a multiple-choice knapsack problem (MCKP), which is solved by the dynamic programming method in pseudo-polynomial time. Simulation results show the effectiveness of our proposed approach in terms of both the tracking performance and lifetime of the sensor network.
From Finite Automata to Regular Expressions and Back--A Summary on Descriptional Complexity
Venue: arXiv cs.FL 2014
Year: 2014

The equivalence of finite automata and regular expressions dates back to the seminal paper of Kleene on events in nerve nets and finite automata from 1956. In the present paper we tour a fragment of the literature and summarize results on upper and lower bounds on the conversion of finite automata to regular expressions and vice versa. We also briefly recall the known bounds for the removal of spontaneous transitions (epsilon-transitions) on non-epsilon-free nondeterministic devices. Moreover, we report on recent results on the average case descriptional complexity bounds for the conversion of regular expressions to finite automata and brand new developments on the state elimination algorithm that converts finite automata to regular expressions.
Operations on Automata with All States Final
Venue: arXiv cs.FL 2014
Year: 2014

We study the complexity of basic regular operations on languages represented by incomplete deterministic or nondeterministic automata, in which all states are final. Such languages are known to be prefix-closed. We get tight bounds on both incomplete and nondeterministic state complexity of complement, intersection, union, concatenation, star, and reversal on prefix-closed languages.
Commutative Languages and their Composition by Consensual Methods
Venue: arXiv cs.FL 2014
Year: 2014

Commutative languages with the semilinear property (SLIP) can be naturally recognized by real-time NLOG-SPACE multi-counter machines. We show that unions and concatenations of such languages can be similarly recognized, relying on -- and further developing, our recent results on the family of consensually regular (CREG) languages. A CREG language is defined by a regular language on the alphabet that includes the terminal alphabet and its marked copy. New conditions, for ensuring that the union or concatenation of CREG languages is closed, are presented and applied to the commutative SLIP languages. The paper contributes to the knowledge of the CREG family, and introduces novel techniques for language composition, based on arithmetic congruences that act as language signatures. Open problems are listed.
Representations of Circular Words
Venue: arXiv cs.FL 2014
Year: 2014

In this article we give two different ways of representations of circular words. Representations with tuples are intended as a compact notation, while representations with trees give a way to easily process all conjugates of a word. The latter form can also be used as a graphical representation of periodic properties of finite (in some cases, infinite) words. We also define iterative representations which can be seen as an encoding utilizing the flexible properties of circular words. Every word over the two letter alphabet can be constructed starting from ab by applying the fractional power and the cyclic shift operators one after the other, iteratively.
Buffered Simulation Games for Büchi Automata
Venue: arXiv cs.FL 2014
Year: 2014

Simulation relations are an important tool in automata theory because they provide efficiently computable approximations to language inclusion. In recent years, extensions of ordinary simulations have been studied, for instance multi-pebble and multi-letter simulations which yield better approximations and are still polynomial-time computable. In this paper we study the limitations of approximating language inclusion in this way: we introduce a natural extension of multi-letter simulations called buffered simulations. They are based on a simulation game in which the two players share a FIFO buffer of unbounded size. We consider two variants of these buffered games called continuous and look-ahead simulation which differ in how elements can be removed from the FIFO buffer. We show that look-ahead simulation, the simpler one, is already PSPACE-hard, i.e. computationally as hard as language inclusion itself. Continuous simulation is even EXPTIME-hard. We also provide matching upper bounds for solving these games with infinite state spaces.
Improved Algorithms for Multiple Sink Location Problems in Dynamic Path Networks
Venue: arXiv cs.DS 2014
Year: 2014

This paper considers the k-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths, uniform edge capacity, and positive vertex supplies. Here, each vertex supply corresponds to a set of evacuees. Then, the problem requires to find the optimal location of $k$ sinks in a given path so that each evacuee is sent to one of k sinks. Let x denote a k-sink location. Under the optimal evacuation for a given x, there exists a (k-1)-dimensional vector d, called (k-1)-divider, such that each component represents the boundary dividing all evacuees between adjacent two sinks into two groups, i.e., all supplies in one group evacuate to the left sink and all supplies in the other group evacuate to the right sink. Therefore, the goal is to find x and d which minimize the maximum cost or the total cost, which are denoted by the minimax problem and the minisum problem, respectively. We study the k-sink location problem in dynamic path networks with continuous model, and prove that the minimax problem can be solved in O(kn) time and the minisum problem can be solved in O(n^2 min{k, 2^{sqrt{log k log log n}}}) time, where n is the number of vertices in the given network. Note that these improve the previous results by [6].
Small Stone in Pool
Venue: arXiv cs.LO 2014
Year: 2014

The Stone tautologies are known to have polynomial size resolution refutations and require exponential size regular refutations. We prove that the Stone tautologies also have polynomial size proofs in both pool resolution and the proof system of regular tree-like resolution with input lemmas (regRTI). Therefore, the Stone tautologies do not separate resolution from DPLL with clause learning.
Machine Translation Model based on Non-parallel Corpus and Semi-supervised Transductive Learning
Venue: arXiv cs.CL 2014
Year: 2014

Although the parallel corpus has an irreplaceable role in machine translation, its scale and coverage is still beyond the actual needs. Non-parallel corpus resources on the web have an inestimable potential value in machine translation and other natural language processing tasks. This article proposes a semi-supervised transductive learning method for expanding the training corpus in statistical machine translation system by extracting parallel sentences from the non-parallel corpus. This method only requires a small amount of labeled corpus and a large unlabeled corpus to build a high-performance classifier, especially for when there is short of labeled corpus. The experimental results show that by combining the non-parallel corpus alignment and the semi-supervised transductive learning method, we can more effectively use their respective strengths to improve the performance of machine translation system.
An Analytical Survey of Provenance Sanitization
Venue: arXiv cs.DB 2014
Year: 2014

Security is likely becoming a critical factor in the future adoption of provenance technology, because of the risk of inadvertent disclosure of sensitive information. In this survey paper we review the state of the art in secure provenance, considering mechanisms for controlling access, and the extent to which these mechanisms preserve provenance integrity. We examine seven systems or approaches, comparing features and identifying areas for future work.
Diferenciación Automática Anidada. Un enfoque algebraico
Venue: arXiv cs.SC 2014
Year: 2014

En este trabajo se presenta una propuesta para realizar Diferenciación Automática Anidada utilizando cualquier biblioteca de Diferenciación Automática que permita sobrecarga de operadores. Para calcular las derivadas anidadas en una misma evaluación de la función, la cual se asume que sea anal'itica, se trabaja con el modo forward utilizando una nueva estructura llamada SuperAdouble, que garantiza que se aplique correctamente la diferenciación automática y se calculen el valor y la derivada que se requiera. También se presenta un enfoque algebraico de la Diferenciación Automática y en particular del espacio de los SuperAdoubles. This paper proposes a framework to apply Nested Automatic Differentiation using any library of Automatic Differentiation which allows operator overloading. To compute nested derivatives of a function while it is being evaluated, which is assumed to be analytic, a new structure called SuperAdouble is used in the forward mode. This new class guarantees the correct application of Automatic Differentiation to calculate the value and derivative of a function where is required. Also, an Automatic Differentiation algebraic point of view is presented with particular emphasis in Nested Automatic Differentiation.
Caching Eliminates the Wireless Bottleneck in Video-Aware Wireless Networks
Venue: arXiv cs.IT 2014
Year: 2014

Cellular data traffic almost doubles every year, greatly straining network capacity. The main driver for this development is wireless video. Traditional methods for capacity increase (like using more spectrum and increasing base station density) are very costly, and do not exploit the unique features of video, in particular a high degree of {\em asynchronous content reuse}. In this paper we give an overview of our work that proposed and detailed a new transmission paradigm exploiting content reuse, and the fact that storage is the fastest-increasing quantity in modern hardware. Our network structure uses caching in helper stations (femto-caching) and/or devices, combined with highly spectrally efficient short-range communications to deliver video files. For femto-caching, we develop optimum storage schemes and dynamic streaming policies that optimize video quality. For caching on devices, combined with device-to-device communications, we show that communications within {\em clusters} of mobile stations should be used; the cluster size can be adjusted to optimize the tradeoff between frequency reuse and the probability that a device finds a desired file cached by another device in the same cluster. We show that in many situations the network throughput increases linearly with the number of users, and that D2D communications also is superior in providing a better tradeoff between throughput and outage than traditional base-station centric systems. Simulation results with realistic numbers of users and channel conditions show that network throughput (possibly with outage constraints) can be increased by two orders of magnitude compared to conventional schemes.
Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms
Venue: arXiv cs.GT 2014
Year: 2014

We provide polynomial-time approximately optimal Bayesian mechanisms for makespan minimization on unrelated machines as well as for max-min fair allocations of indivisible goods, with approximation factors of $2$ and $\min\{m-k+1, \tilde{O}(\sqrt{k})\}$ respectively, matching the approximation ratios of best known polynomial-time \emph{algorithms} (for max-min fairness, the latter claim is true for certain ratios of the number of goods $m$ to people $k$). Our mechanisms are obtained by establishing a polynomial-time approximation-sensitive reduction from the problem of designing approximately optimal {\em mechanisms} for some arbitrary objective ${\cal O}$ to that of designing bi-criterion approximation {\em algorithms} for the same objective ${\cal O}$ plus a linear allocation cost term. Our reduction is itself enabled by extending the celebrated "equivalence of separation and optimization"[GLSS81,KP80] to also accommodate bi-criterion approximations. Moreover, to apply the reduction to the specific problems of makespan and max-min fairness we develop polynomial-time bi-criterion approximation algorithms for makespan minimization with costs and max-min fairness with costs, adapting the algorithms of [ST93], [BD05] and [AS07] to the type of bi-criterion approximation that is required by the reduction.