OpenRaiser/Intern-Atlas huggingface dataset:
The Complexity of Change
Venue: arXiv cs.DM 2013
Year: 2013

Many combinatorial problems can be formulated as "Can I transform configuration 1 into configuration 2, if certain transformations only are allowed?". An example of such a question is: given two k-colourings of a graph, can I transform the first k-colouring into the second one, by recolouring one vertex at a time, and always maintaining a proper k-colouring? Another example is: given two solutions of a SAT-instance, can I transform the first solution into the second one, by changing the truth value one variable at a time, and always maintaining a solution of the SAT-instance? Other examples can be found in many classical puzzles, such as the 15-Puzzle and Rubik's Cube. In this survey we shall give an overview of some older and more recent work on this type of problem. The emphasis will be on the computational complexity of the problems: how hard is it to decide if a certain transformation is possible or not?
3D Maps Registration and Path Planning for Autonomous Robot Navigation
Venue: arXiv cs.RO 2013
Year: 2013

Mobile robots dedicated in security tasks should be capable of clearly perceiving their environment to competently navigate within cluttered areas, so as to accomplish their assigned mission. The paper in hand describes such an autonomous agent designed to deploy competently in hazardous environments equipped with a laser scanner sensor. During the robot's motion, consecutive scans are obtained to produce dense 3D maps of the area. A 3D point cloud registration technique is exploited to merge the successively created maps during the robot's motion followed by an ICP refinement step. The reconstructed 3D area is then top-down projected with great resolution, to be fed in a path planning algorithm suitable to trace obstacle-free trajectories in the explored area. The main characteristic of the path planner is that the robot's embodiment is considered for producing detailed and safe trajectories of $1$ $cm$ resolution. The proposed method has been evaluated with our mobile robot in several outdoor scenarios revealing remarkable performance.
A Proposed NFC Payment Application
Venue: arXiv cs.CR 2013
Year: 2013

Near Field Communication (NFC) technology is based on a short range radio communication channel which enables users to exchange data between devices. With NFC technology, mobile services establish a contactless transaction system to make the payment methods easier for people. Although NFC mobile services have great potential for growth, they have raised several issues which have concerned the researches and prevented the adoption of this technology within societies. Reorganizing and describing what is required for the success of this technology have motivated us to extend the current NFC ecosystem models to accelerate the development of this business area. In this paper, we introduce a new NFC payment application, which is based on our previous NFC Cloud Wallet model to demonstrate a reliable structure of NFC ecosystem. We also describe the step by step execution of the proposed protocol in order to carefully analyse the payment application and our main focus will be on the Mobile Network Operator (MNO) as the main player within the ecosystem.
Advanced Antenna Techniques and High Order Sectorization with Novel Network Tessellation for Enhancing Macro Cell Capacity in DC-HSDPA Network
Venue: arXiv cs.NI 2013
Year: 2013

Mobile operators commonly use macro cells with traditional wide beam antennas for wider coverage in the cell, but future capacity demands cannot be achieved by using them only. It is required to achieve maximum practical capacity from macro cells by employing higher order sectorization and by utilizing all possible antenna solutions including smart antennas. This paper presents enhanced tessellation for 6-sector sites and proposes novel layout for 12-sector sites. The main target of this paper is to compare the performance of conventional wide beam antenna, switched beam smart antenna, adaptive beam antenna and different network layouts in terms of offering better received signal quality and user throughput. Splitting macro cell into smaller micro or pico cells can improve the capacity of network, but this paper highlights the importance of higher order sectorization and advance antenna techniques to attain high Signal to Interference plus Noise Ratio (SINR), along with improved network capacity. Monte Carlo simulations at system level were done for Dual Cell High Speed Downlink Packet Access (DC-HSDPA) technology with multiple (five) users per Transmission Time Interval (TTI) at different Intersite Distance (ISD). The obtained results validate and estimate the gain of using smart antennas and higher order sectorization with proposed network layout.
Active Player Modelling
Venue: arXiv cs.LG 2013
Year: 2013

We argue for the use of active learning methods for player modelling. In active learning, the learning algorithm chooses where to sample the search space so as to optimise learning progress. We hypothesise that player modelling based on active learning could result in vastly more efficient learning, but will require big changes in how data is collected. Some example active player modelling scenarios are described. A particular form of active learning is also equivalent to an influential formalisation of (human and machine) curiosity, and games with active learning could therefore be seen as being curious about the player. We further hypothesise that this form of curiosity is symmetric, and therefore that games that explore their players based on the principles of active learning will turn out to select game configurations that are interesting to the player that is being explored.
A Survey of Embedded Software Profiling Methodologies
Venue: arXiv cs.PF 2013
Year: 2013

Embedded Systems combine one or more processor cores with dedicated logic running on an ASIC or FPGA to meet design goals at reasonable cost. It is achieved by profiling the application with variety of aspects like performance, memory usage, cache hit versus cache miss, energy consumption, etc. Out of these, performance estimation is more important than others. With ever increasing system complexities, it becomes quite necessary to carry out performance estimation of embedded software implemented in a particular processor for fast design space exploration. Such profiled data also guides the designer how to partition the system for Hardware (HW) and Software (SW) environments. In this paper, we propose a classification for currently available Embedded Software Profiling Tools, and we present different academic and industrial approaches in this context. Based on these observations, it will be easy to identify such common principles and needs which are required for a true Software Profiling Tool for a particular application.
Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture
Venue: arXiv cs.CC 2013
Year: 2013

Given $f:\{-1, 1\}^n \rightarrow \{-1, 1\}$, define the \emph{spectral distribution} of $f$ to be the distribution on subsets of $[n]$ in which the set $S$ is sampled with probability $\widehat{f}(S)^2$. Then the Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai (1996) states that there is some absolute constant $C$ such that $\operatorname{H}[\widehat{f}^2] \leq C\cdot\operatorname{Inf}[f]$. Here, $\operatorname{H}[\widehat{f}^2]$ denotes the Shannon entropy of $f$'s spectral distribution, and $\operatorname{Inf}[f]$ is the total influence of $f$. This conjecture is one of the major open problems in the analysis of Boolean functions, and settling it would have several interesting consequences. Previous results on the FEI conjecture have been largely through direct calculation. In this paper we study a natural interpretation of the conjecture, which states that there exists a communication protocol which, given subset $S$ of $[n]$ distributed as $\widehat{f}^2$, can communicate the value of $S$ using at most $C\cdot\operatorname{Inf}[f]$ bits in expectation. Using this interpretation, we are able show the following results: 1. First, if $f$ is computable by a read-$k$ decision tree, then $\operatorname{H}[\widehat{f}^2] \leq 9k\cdot \operatorname{Inf}[f]$. 2. Next, if $f$ has $\operatorname{Inf}[f] \geq 1$ and is computable by a decision tree with expected depth $d$, then $\operatorname{H}[\widehat{f}^2] \leq 12d\cdot \operatorname{Inf}[f]$. 3. Finally, we give a new proof of the main theorem of O'Donnell and Tan (ICALP 2013), i.e. that their FEI$^+$ conjecture composes. In addition, we show that natural improvements to our decision tree results would be sufficient to prove the FEI conjecture in its entirety. We believe that our methods give more illuminating proofs than previous results about the FEI conjecture.
Cross-Layer MIMO Transceiver Optimization for Multimedia Streaming in Interference Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider dynamic precoder/decorrelator optimization for multimedia streaming in MIMO interference networks. We propose a truly cross-layer framework in the sense that the optimization objective is the application level performance metrics for multimedia streaming, namely the playback interruption and buffer overflow probabilities. The optimization variables are the MIMO precoders/decorrelators at the transmitters and the receivers, which are adaptive to both the instantaneous channel condition and the playback queue length. The problem is a challenging multi-dimensional stochastic optimization problem and brute-force solution has exponential complexity. By exploiting the underlying timescale separation and special structure in the problem, we derive a closed-form approximation of the value function based on continuous time perturbation. Using this approximation, we propose a low complexity dynamic MIMO precoder/decorrelator control algorithm by solving an equivalent weighted MMSE problem. We also establish the technical conditions for asymptotic optimality of the low complexity control algorithm. Finally, the proposed scheme is compared with various baselines through simulations and it is shown that significant performance gain can be achieved.
A Decision Model for Supporting Task Allocation Processes in Global Software Development
Venue: arXiv cs.SE 2013
Year: 2013

Today, software-intensive systems are increasingly being developed in a globally distributed way. However, besides its benefit, global development also bears a set of risks and problems. One critical factor for successful project management of distributed software development is the allocation of tasks to sites, as this is assumed to have a major influence on the benefits and risks. We introduce a model that aims at improving management processes in globally distributed projects by giving decision support for task allocation that systematically regards multiple criteria. The criteria and causal relationships were identified in a literature study and refined in a qualitative interview study. The model uses existing approaches from distributed systems and statistical modeling. The article gives an overview of the problem and related work, introduces the empirical and theoretical foundations of the model, and shows the use of the model in an example scenario.
On The Center Sets and Center Numbers of Some Graph Classes
Venue: arXiv cs.DM 2013
Year: 2013

For a set $S$ of vertices and the vertex $v$ in a connected graph $G$, $\displaystyle\max_{x \in S}d(x,v)$ is called the $S$-eccentricity of $v$ in $G$. The set of vertices with minimum $S$-eccentricity is called the $S$-center of $G$. Any set $A$ of vertices of $G$ such that $A$ is an $S$-center for some set $S$ of vertices of $G$ is called a center set. We identify the center sets of certain classes of graphs namely, Block graphs, $K_{m,n}$, $K_n-e$, wheel graphs, odd cycles and symmetric even graphs and enumerate them for many of these graph classes. We also introduce the concept of center number which is defined as the number of distinct center sets of a graph and determine the center number of some graph classes.
Thickness Mapping of Eleven Retinal Layers in Normal Eyes Using Spectral Domain Optical Coherence Tomography
Venue: arXiv cs.CV 2013
Year: 2013

Purpose. This study was conducted to determine the thickness map of eleven retinal layers in normal subjects by spectral domain optical coherence tomography (SD-OCT) and evaluate their association with sex and age. Methods. Mean regional retinal thickness of 11 retinal layers were obtained by automatic three-dimensional diffusion-map-based method in 112 normal eyes of 76 Iranian subjects. Results. The thickness map of central foveal area in layer 1, 3, and 4 displayed the minimum thickness (P<0.005 for all). Maximum thickness was observed in nasal to the fovea of layer 1 (P<0.001) and in a circular pattern in the parafoveal retinal area of layers 2, 3 and 4 and in central foveal area of layer 6 (P<0.001). Temporal and inferior quadrants of the total retinal thickness and most of other quadrants of layer 1 were significantly greater in the men than in the women. Surrounding eight sectors of total retinal thickness and a limited number of sectors in layer 1 and 4 significantly correlated with age. Conclusion. SD-OCT demonstrated the three-dimensional thickness distribution of retinal layers in normal eyes. Thickness of layers varied with sex and age and in different sectors. These variables should be considered while evaluating macular thickness.
Matrix Product Codes over Finite Commutative Frobenius Rings
Venue: arXiv cs.IT 2013
Year: 2013

Properties of matrix product codes over finite commutative Frobenius rings are investigated. The minimum distance of matrix product codes constructed with several types of matrices is bounded in different ways. The duals of matrix product codes are also explicitly described in terms of matrix product codes.
One-Bit Compressed Sensing by Greedy Algorithms
Venue: arXiv cs.IT 2013
Year: 2013

Sign truncated matching pursuit (STrMP) algorithm is presented in this paper. STrMP is a new greedy algorithm for the recovery of sparse signals from the sign measurement, which combines the principle of consistent reconstruction with orthogonal matching pursuit (OMP). The main part of STrMP is as concise as OMP and hence STrMP is simple to implement. In contrast to previous greedy algorithms for one-bit compressed sensing, STrMP only need to solve a convex and unconstraint subproblem at each iteration. Numerical experiments show that STrMP is fast and accurate for one-bit compressed sensing compared with other algorithms.
Cloud Service-Aware Location Update in Mobile Cloud Computing
Venue: arXiv cs.NI 2013
Year: 2013

Mobile devices are becoming the primary platforms for many users who always roam around when accessing the cloud computing services. From this, the cloud computing is integrated into the mobile environment by introducing a new paradigm, mobile cloud computing. In the context of mobile computing, the battery life of mobile device is limited, and it is important to balance the mobility performance and energy consumption. Fortunately, cloud services provide both opportunities and challenges for mobility management. Taking the activities of cloud services accessing into consideration, we propose a service-aware location update mechanism, which can detect the presence and location of the mobile device without traditional periodic registration update. Analytic model and simulation are developed to investigate the new mechanism. The results demonstrate that the service-aware location update management can reduce the location update times and handoff signaling, which can efficiently save power consumption for mobile devices.
Bisimulation equivalence of first-order grammars is Ackermann-hard
Venue: arXiv cs.LO 2013
Year: 2013

Bisimulation equivalence (or bisimilarity) of first-order grammars is decidable, as follows from the decidability result by Senizergues (1998, 2005) that has been given in an equivalent framework of equational graphs with finite out-degree, or of pushdown automata (PDA) with only deterministic and popping epsilon-transitions. Benedikt, Goeller, Kiefer, and Murawski (2013) have shown that the bisimilarity problem for PDA (even) without epsilon-transitions is nonelementary. Here we show Ackermann-hardness for bisimilarity of first-order grammars. The grammars do not use explicit epsilon-transitions, but they correspond to the above mentioned PDA with (deterministic and popping) epsilon-transitions, and this feature is substantial in the presented lower-bound proof. The proof is based on a (polynomial) reduction from the reachability problem of reset (or lossy) counter machines, for which the Ackermann-hardness has been shown by Schnoebelen (2010); in fact, this reachability problem is known to be Ackermann-complete in the hierarchy of fast-growing complexity classes defined by Schmitz (2013).
Achieving Fully Proportional Representation: Approximability Results
Venue: arXiv cs.AI 2013
Year: 2013

We study the complexity of (approximate) winner determination under the Monroe and Chamberlin--Courant multiwinner voting rules, which determine the set of representatives by optimizing the total (dis)satisfaction of the voters with their representatives. The total (dis)satisfaction is calculated either as the sum of individual (dis)satisfactions (the utilitarian case) or as the (dis)satisfaction of the worst off voter (the egalitarian case). We provide good approximation algorithms for the satisfaction-based utilitarian versions of the Monroe and Chamberlin--Courant rules, and inapproximability results for the dissatisfaction-based utilitarian versions of them and also for all egalitarian cases. Our algorithms are applicable and particularly appealing when voters submit truncated ballots. We provide experimental evaluation of the algorithms both on real-life preference-aggregation data and on synthetic data. These experiments show that our simple and fast algorithms can in many cases find near-perfect solutions.
Clustering using Vector Membership: An Extension of the Fuzzy C-Means Algorithm
Venue: arXiv cs.CV 2013
Year: 2013

Clustering is an important facet of explorative data mining and finds extensive use in several fields. In this paper, we propose an extension of the classical Fuzzy C-Means clustering algorithm. The proposed algorithm, abbreviated as VFC, adopts a multi-dimensional membership vector for each data point instead of the traditional, scalar membership value defined in the original algorithm. The membership vector for each point is obtained by considering each feature of that point separately and obtaining individual membership values for the same. We also propose an algorithm to efficiently allocate the initial cluster centers close to the actual centers, so as to facilitate rapid convergence. Further, we propose a scheme to achieve crisp clustering using the VFC algorithm. The proposed, novel clustering scheme has been tested on two standard data sets in order to analyze its performance. We also examine the efficacy of the proposed scheme by analyzing its performance on image segmentation examples and comparing it with the classical Fuzzy C-means clustering algorithm.
A natural-inspired optimization machine based on the annual migration of salmons in nature
Venue: arXiv cs.NE 2013
Year: 2013

Bio inspiration is a branch of artificial simulation science that shows pervasive contributions to variety of engineering fields such as automate pattern recognition, systematic fault detection and applied optimization. In this paper, a new metaheuristic optimizing algorithm that is the simulation of The Great Salmon Run(TGSR) is developed. The obtained results imply on the acceptable performance of implemented method in optimization of complex non convex, multi dimensional and multi-modal problems. To prove the superiority of TGSR in both robustness and quality, it is also compared with most of the well known proposed optimizing techniques such as Simulated Annealing (SA), Parallel Migrating Genetic Algorithm (PMGA), Differential Evolutionary Algorithm (DEA), Particle Swarm Optimization (PSO), Bee Algorithm (BA), Artificial Bee Colony (ABC), Firefly Algorithm (FA) and Cuckoo Search (CS). The obtained results confirm the acceptable performance of the proposed method in both robustness and quality for different bench-mark optimizing problems and also prove the authors claim.
Trees and co-trees with constant maximum degree in planar 3-connected graphs
Venue: arXiv cs.DM 2013
Year: 2013

This paper considers the conjecture by Grünbaum that every planar 3-connected graph has a spanning tree $T$ such that both $T$ and its co-tree have maximum degree at most 3. Here, the co-tree of $T$ is the spanning tree of the dual obtained by taking the duals of the non-tree edges. While Grünbaum's conjecture remains open, we show that every planar 3-connected graph has a spanning tree $T$ such that both $T$ and its co-tree have maximum degree at most 5. It can be found in linear time.
A MapReduce based distributed SVM algorithm for binary classification
Venue: arXiv cs.LG 2013
Year: 2013

Although Support Vector Machine (SVM) algorithm has a high generalization property to classify for unseen examples after training phase and it has small loss value, the algorithm is not suitable for real-life classification and regression problems. SVMs cannot solve hundreds of thousands examples in training dataset. In previous studies on distributed machine learning algorithms, SVM is trained over a costly and preconfigured computer environment. In this research, we present a MapReduce based distributed parallel SVM training algorithm for binary classification problems. This work shows how to distribute optimization problem over cloud computing systems with MapReduce technique. In the second step of this work, we used statistical learning theory to find the predictive hypothesis that minimize our empirical risks from hypothesis spaces that created with reduce function of MapReduce. The results of this research are important for training of big datasets for SVM algorithm based classification problems. We provided that iterative training of split dataset with MapReduce technique; accuracy of the classifier function will converge to global optimal classifier function's accuracy in finite iteration size. The algorithm performance was measured on samples from letter recognition and pen-based recognition of handwritten digits dataset.
Towards slime mould chemical sensor: Mapping chemical inputs onto electrical potential dynamics of Physarum Polycephalum
Venue: arXiv cs.ET 2013
Year: 2013

We experimentally derived a unique one-to-one mapping between a range of selected bioactive chemicals and patterns of oscillations of the slime mould's extacellular electrical potential.
On Constraint Satisfaction Problems below P
Venue: arXiv cs.CC 2013
Year: 2013

Symmetric Datalog, a fragment of the logic programming language Datalog, is conjectured to capture all constraint satisfaction problems (CSP) in L. Therefore developing tools that help us understand whether or not a CSP can be defined in symmetric Datalog is an important task. It is widely known that a CSP is definable in Datalog and linear Datalog if and only if that CSP has bounded treewidth and bounded pathwidth duality, respectively. In the case of symmetric Datalog, Bulatov, Krokhin and Larose ask for such a duality (2008). We provide two such dualities, and give applications. In particular, we give a short and simple new proof of the result of Dalmau and Larose that "Maltsev + Datalog -> symmetric Datalog" (2008). In the second part of the paper, we provide some evidence for the conjecture of Dalmau (2002) that every CSP in NL is definable in linear Datalog. Our results also show that a wide class of CSPs-CSPs which do not have bounded pathwidth duality (e.g., the P-complete Horn-3Sat problem)-cannot be defined by any polynomial size family of monotone read-once nondeterministic branching programs.