OpenRaiser/Intern-Atlas huggingface dataset:
Watching the IPv6 Takeoff from an IXP's Viewpoint
Venue: arXiv cs.NI 2014
Year: 2014

The different level of interest in deploying the new Internet address space across network operators has kept IPv6 tardy in its deployment. However, since the last block of IPv4 addresses has been assigned, Internet communities took the concern of the address space scarcity seriously and started to move forward actively. After the successful IPv6 test on 8 June, 2011 (World IPv6 Day [1]), network operators and service/content providers were brought together for preparing the next step of the IPv6 global deployment (World IPv6 Launch on 6 June, 2012 [2]). The main purpose of the event was to permanently enable their IPv6 connectivity. In this paper, based on the Internet traffic collected from a large European Internet Exchange Point (IXP), we present the status of IPv6 traffic mainly focusing on the periods of the two global IPv6 events. Our results show that IPv6 traffic is responsible for a small fraction such as 0.5 % of the total traffic in the peak period. Nevertheless, we are positively impressed by the facts that the increase of IPv6 traffic/prefixes shows a steep increase and that the application mix of IPv6 traffic starts to imitate the one of IPv4-dominated Internet.
An Improved Algorithm for Fixed-Hub Single Allocation Problem
Venue: arXiv cs.DS 2014
Year: 2014

This paper discusses the fixed-hub single allocation problem (FHSAP). In this problem, a network consists of hub nodes and terminal nodes. Hubs are fixed and fully connected; each terminal node is connected to a single hub which routes all its traffic. The goal is to minimize the cost of routing the traffic in the network. In this paper, we propose a linear programming (LP)-based rounding algorithm. The algorithm is based on two ideas. First, we modify the LP relaxation formulation introduced in Ernst and Krishnamoorthy (1996, 1999) by incorporating a set of validity constraints. Then, after obtaining a fractional solution to the LP relaxation, we make use of a geometric rounding algorithm to obtain an integral solution. We show that by incorporating the validity constraints, the strengthened LP often provides much tighter upper bounds than the previous methods with a little more computational effort, and the solution obtained often has a much smaller gap with the optimal solution. We also formulate a robust version of the FHSAP and show that it can guard against data uncertainty with little cost.
On the Hardness of Signaling
Venue: arXiv cs.GT 2014
Year: 2014

There has been a recent surge of interest in the role of information in strategic interactions. Much of this work seeks to understand how the realized equilibrium of a game is influenced by uncertainty in the environment and the information available to players in the game. Lurking beneath this literature is a fundamental, yet largely unexplored, algorithmic question: how should a "market maker" who is privy to additional information, and equipped with a specified objective, inform the players in the game? This is an informational analogue of the mechanism design question, and views the information structure of a game as a mathematical object to be designed, rather than an exogenous variable. We initiate a complexity-theoretic examination of the design of optimal information structures in general Bayesian games, a task often referred to as signaling. We focus on one of the simplest instantiations of the signaling question: Bayesian zero-sum games, and a principal who must choose an information structure maximizing the equilibrium payoff of one of the players. In this setting, we show that optimal signaling is computationally intractable, and in some cases hard to approximate, assuming that it is hard to recover a planted clique from an Erdos-Renyi random graph. This is despite the fact that equilibria in these games are computable in polynomial time, and therefore suggests that the hardness of optimal signaling is a distinct phenomenon from the hardness of equilibrium computation. Necessitated by the non-local nature of information structures, en-route to our results we prove an "amplification lemma" for the planted clique problem which may be of independent interest.
Exploring gender differences on general and specific computer self-efficacy in mobile learning adoption
Venue: arXiv cs.CY 2014
Year: 2014

Reasons for contradictory findings regarding the gender moderate effect on computer self-efficacy in the adoption of e-learning/mobile learning are limited. Recognizing the multilevel nature of the computer self-efficacy (CSE), this study attempts to explore gender differences in the adoption of mobile learning, by extending the Technology Acceptance Model (TAM) with general and specific CSE. Data collected from 137 university students were tested against the research model using the structural equation modeling approach. The results suggest that there are significant gender differences in perceptions of general CSE, perceived ease of use and behavioral intention to use but no significant differences in specific CSE, perceived usefulness. Additionally, the findings reveal that specific CSE is more salient than general CSE in influencing perceived ease of use while general CSE seems to be the salient factor on perceived usefulness for both female and male combined. Moreover, general CSE was salient to determine the behavioral intention to use indirectly for female despite lower perception of general CSE than male's, and specific CSE exhibited stronger indirect effect on behavioral intention to use than general CSE for female despite similar perception of specific CSE as males'. These findings provide important implications for mobile learning adoption and usage.
Effects of Easy Hybrid Parallelization with CUDA for Numerical-Atomic-Orbital Density Functional Theory Calculation
Venue: arXiv cs.DC 2014
Year: 2014

We modified a MPI-friendly density functional theory (DFT) source code within hybrid parallelization including CUDA. Our objective is to find out how simple conversions within the hybrid parallelization with mid-range GPUs affect DFT code not originally suitable to CUDA. We settled several rules of hybrid parallelization for numerical-atomic-orbital (NAO) DFT codes. The test was performed on a magnetite material system with OpenMX code by utilizing a hardware system containing 2 Xeon E5606 CPUs and 2 Quadro 4000 GPUs. 3-way hybrid routines obtained a speedup of 7.55 while 2-way hybrid speedup by 10.94. GPUs with CUDA complement the efficiency of OpenMP and compensate CPUs' excessive competition within MPI.
Lossy Source Coding with Reconstruction Privacy
Venue: arXiv cs.IT 2014
Year: 2014

We consider the problem of lossy source coding with side information under a privacy constraint that the reconstruction sequence at a decoder should be kept secret to a certain extent from another terminal such as an eavesdropper, a sender, or a helper. We are interested in how the reconstruction privacy constraint at a particular terminal affects the rate-distortion tradeoff. In this work, we allow the decoder to use a random mapping, and give inner and outer bounds to the rate-distortion-equivocation region for different cases where the side information is available non-causally and causally at the decoder. In the special case where each reconstruction symbol depends only on the source description and current side information symbol, the complete rate-distortion-equivocation region is provided. A binary example illustrating a new tradeoff due to the new privacy constraint, and a gain from the use of a stochastic decoder is given.
Unification and Logarithmic Space
Venue: arXiv cs.LO 2014
Year: 2014

We present an algebraic characterization of the complexity classes Logspace and NLogspace, using an algebra with a composition law based on unification. This new bridge between unification and complexity classes is inspired from proof theory and more specifically linear logic and Geometry of Interaction. We show how unification can be used to build a model of computation by means of specific subalgebras associated to finite permutations groups. We then prove that whether an observation (the algebraic counterpart of a program) accepts a word can be decided within logarithmic space. We also show that the construction can naturally represent pointer machines, an intuitive way of understanding logarithmic space computing.
The Complexity of Ferromagnetic Two-spin Systems with External Fields
Venue: arXiv cs.CC 2014
Year: 2014

We study the approximability of computing the partition function for ferromagnetic two-state spin systems. The remarkable algorithm by Jerrum and Sinclair showed that there is a fully polynomial-time randomized approximation scheme (FPRAS) for the special ferromagnetic Ising model with any given uniform external field. Later, Goldberg and Jerrum proved that it is #BIS-hard for Ising model if we allow inconsistent external fields on different nodes. In contrast to these two results, we prove that for any ferromagnetic two-state spin systems except the Ising model, there exists a threshold for external fields beyond which the problem is #BIS-hard, even if the external field is uniform.
Morphing Planar Graph Drawings Optimally
Venue: arXiv cs.DS 2014
Year: 2014

We provide an algorithm for computing a planar morph between any two planar straight-line drawings of any $n$-vertex plane graph in $O(n)$ morphing steps, thus improving upon the previously best known $O(n^2)$ upper bound. Further, we prove that our algorithm is optimal, that is, we show that there exist two planar straight-line drawings $Γ_s$ and $Γ_t$ of an $n$-vertex plane graph $G$ such that any planar morph between $Γ_s$ and $Γ_t$ requires $Ω(n)$ morphing steps.
Automatic Detection of Font Size Straight from Run Length Compressed Text Documents
Venue: arXiv cs.CV 2014
Year: 2014

Automatic detection of font size finds many applications in the area of intelligent OCRing and document image analysis, which has been traditionally practiced over uncompressed documents, although in real life the documents exist in compressed form for efficient storage and transmission. It would be novel and intelligent if the task of font size detection could be carried out directly from the compressed data of these documents without decompressing, which would result in saving of considerable amount of processing time and space. Therefore, in this paper we present a novel idea of learning and detecting font size directly from run-length compressed text documents at line level using simple line height features, which paves the way for intelligent OCRing and document analysis directly from compressed documents. In the proposed model, the given mixed-case text documents of different font size are segmented into compressed text lines and the features extracted such as line height and ascender height are used to capture the pattern of font size in the form of a regression line, using which the automatic detection of font size is done during the recognition stage. The method is experimented with a dataset of 50 compressed documents consisting of 780 text lines of single font size and 375 text lines of mixed font size resulting in an overall accuracy of 99.67%.
Artificial Mutation inspired Hyper-heuristic for Runtime Usage of Multi-objective Algorithms
Venue: arXiv cs.SE 2014
Year: 2014

In the last years, multi-objective evolutionary algorithms (MOEA) have been applied to different software engineering problems where many conflicting objectives have to be optimized simultaneously. In theory, evolutionary algorithms feature a nice property for runtime optimization as they can provide a solution in any execution time. In practice, based on a Darwinian inspired natural selection, these evolutionary algorithms produce many deadborn solutions whose computation results in a computational resources wastage: natural selection is naturally slow. In this paper, we reconsider this founding analogy to accelerate convergence of MOEA, by looking at modern biology studies: artificial selection has been used to achieve an anticipated specific purpose instead of only relying on crossover and natural selection (i.e., Muller et al [18] research on artificial mutation of fruits with X-Ray). Putting aside the analogy with natural selection , the present paper proposes an hyper-heuristic for MOEA algorithms named Sputnik 1 that uses artificial selective mutation to improve the convergence speed of MOEA. Sputnik leverages the past history of mutation efficiency to select the most relevant mutations to perform. We evaluate Sputnik on a cloud-reasoning engine, which drives on-demand provisioning while considering conflicting performance and cost objectives. We have conducted experiments to highlight the significant performance improvement of Sputnik in terms of resolution time.
Growth rates of modern science: A bibliometric analysis based on the number of publications and cited references
Venue: arXiv cs.DL 2014
Year: 2014

Many studies in information science have looked at the growth of science. In this study, we re-examine the question of the growth of science. To do this we (i) use current data up to publication year 2012 and (ii) analyse it across all disciplines and also separately for the natural sciences and for the medical and health sciences. Furthermore, the data are analysed with an advanced statistical technique - segmented regression analysis - which can identify specific segments with similar growth rates in the history of science. The study is based on two different sets of bibliometric data: (1) The number of publications held as source items in the Web of Science (WoS, Thomson Reuters) per publication year and (2) the number of cited references in the publications of the source items per cited reference year. We have looked at the rate at which science has grown since the mid-1600s. In our analysis of cited references we identified three growth phases in the development of science, which each led to growth rates tripling in comparison with the previous phase: from less than 1% up to the middle of the 18th century, to 2 to 3% up to the period between the two world wars and 8 to 9% to 2012.
Standard protocol complexes for the immediate snapshot read/write model
Venue: arXiv cs.DC 2014
Year: 2014

In this paper we consider a family of abstract simplicial complexes which we call immediate snapshot complexes. Their definition is motivated by theoretical distributed computing. Specifically, these complexes appear as protocol complexes in the general immediate snapshot execution model. In order to define and to analyze the immediate snapshot complexes we use the novel language of witness structures. We develop the rigorous mathematical theory of witness structures and use it to prove several combinatorial as well as topological properties of the immediate snapshot complexes. In particular, we prove that these complexes are simplicially homeomorphic to simplices.
Diffusion Least Mean Square: Simulations
Venue: arXiv cs.LG 2014
Year: 2014

In this technical report we analyse the performance of diffusion strategies applied to the Least-Mean-Square adaptive filter. We configure a network of cooperative agents running adaptive filters and discuss their behaviour when compared with a non-cooperative agent which represents the average of the network. The analysis provides conditions under which diversity in the filter parameters is beneficial in terms of convergence and stability. Simulations drive and support the analysis.
An Upper Bound on the Number of Circular Transpositions to Sort a Permutation
Venue: arXiv cs.DM 2014
Year: 2014

We consider the problem of upper bounding the number of circular transpositions needed to sort a permutation. It is well known that any permutation can be sorted using at most $n(n-1)/2$ adjacent transpositions. We show that, if we allow all adjacent transpositions, as well as the transposition that interchanges the element in position 1 with the element in the last position, then the number of transpositions needed is at most $n^2/4$. This answers an open question posed by Feng, Chitturi and Sudborough (2010).
Sub-Modularity of Waterfilling with Applications to Online Basestation Allocation
Venue: arXiv cs.NI 2014
Year: 2014

We show that the popular water-filling algorithm for maximizing the mutual information in parallel Gaussian channels is sub-modular. The sub-modularity of water-filling algorithm is then used to derive online basestation allocation algorithms, where mobile users are assigned to one of many possible basestations immediately and irrevocably upon arrival without knowing the future user information. The goal of the allocation is to maximize the sum-rate of the system under power allocation at each basestation. We present online algorithms with competitive ratio of at most 2 when compared to offline algorithms that have knowledge of all future user arrivals.
Inequity aversion and the evolution of cooperation
Venue: arXiv cs.GT 2014
Year: 2014

Evolution of cooperation is a widely studied problem in biology, social science, economics, and artificial intelligence. Most of the existing approaches that explain cooperation rely on some notion of direct or indirect reciprocity. These reciprocity based models assume agents recognize their partner and know their previous interactions, which requires advanced cognitive abilities. In this paper we are interested in developing a model that produces cooperation without requiring any explicit memory of previous game plays. Our model is based on the notion of, a concept introduced within behavioral economics, whereby individuals care about payoff equality in outcomes. Here we explore the effect of using income inequality to guide partner selection and interaction. We study our model by considering both the well-mixed and the spatially structured population and present the conditions under which cooperation becomes dominant. Our results support the hypothesis that inequity aversion promotes cooperative relationship among nonkin.
Performance Impact of Data Layout on the GPU-accelerated IDW Interpolation
Venue: arXiv cs.DC 2014
Year: 2014

This paper focuses on evaluating the performance impact of different data layouts on the GPU-accelerated IDW interpolation. First, we redesign and improve our previous GPU implementation that was performed by exploiting the feature CUDA Dynamic Parallel (CDP). And then, we implement three versions of GPU implementations, i.e., the naive version, the tiled version, and the improved CDP version, based on five layouts including the Structure of Arrays (SoA), the Array of Sturcutes (AoS), the Array of aligned Sturcutes (AoaS), the Structure of Arrays of aligned Structures (SoAoS), and the Hybrid layout. Experimental results show that: the layouts AoS and AoaS achieve better performance than the layout SoA for both the naive version and tiled version, while the layout SoA is the best choice for the improved CDP version. We also observe that: for the two combined data layouts (the SoAoS and the Hybrid), there are no notable performance gains when compared to other three basic layouts. We recommend that: in practical applications, the layout AoaS is the best choice since the tiled version is the fastest one among the three versions of GPU implementations, especially on single precision.
Minimizing Running Costs in Consumption Systems
Venue: arXiv cs.SY 2014
Year: 2014

A standard approach to optimizing long-run running costs of discrete systems is based on minimizing the mean-payoff, i.e., the long-run average amount of resources ("energy") consumed per transition. However, this approach inherently assumes that the energy source has an unbounded capacity, which is not always realistic. For example, an autonomous robotic device has a battery of finite capacity that has to be recharged periodically, and the total amount of energy consumed between two successive charging cycles is bounded by the capacity. Hence, a controller minimizing the mean-payoff must obey this restriction. In this paper we study the controller synthesis problem for consumption systems with a finite battery capacity, where the task of the controller is to minimize the mean-payoff while preserving the functionality of the system encoded by a given linear-time property. We show that an optimal controller always exists, and it may either need only finite memory or require infinite memory (it is decidable in polynomial time which of the two cases holds). Further, we show how to compute an effective description of an optimal controller in polynomial time. Finally, we consider the limit values achievable by larger and larger battery capacity, show that these values are computable in polynomial time, and we also analyze the corresponding rate of convergence. To the best of our knowledge, these are the first results about optimizing the long-run running costs in systems with bounded energy stores.
Beyond Geometry : Towards Fully Realistic Wireless Models
Venue: arXiv cs.NI 2014
Year: 2014

Signal-strength models of wireless communications capture the gradual fading of signals and the additivity of interference. As such, they are closer to reality than other models. However, nearly all theoretic work in the SINR model depends on the assumption of smooth geometric decay, one that is true in free space but is far off in actual environments. The challenge is to model realistic environments, including walls, obstacles, reflections and anisotropic antennas, without making the models algorithmically impractical or analytically intractable. We present a simple solution that allows the modeling of arbitrary static situations by moving from geometry to arbitrary decay spaces. The complexity of a setting is captured by a metricity parameter Z that indicates how far the decay space is from satisfying the triangular inequality. All results that hold in the SINR model in general metrics carry over to decay spaces, with the resulting time complexity and approximation depending on Z in the same way that the original results depends on the path loss term alpha. For distributed algorithms, that to date have appeared to necessarily depend on the planarity, we indicate how they can be adapted to arbitrary decay spaces. Finally, we explore the dependence on Z in the approximability of core problems. In particular, we observe that the capacity maximization problem has exponential upper and lower bounds in terms of Z in general decay spaces. In Euclidean metrics and related growth-bounded decay spaces, the performance depends on the exact metricity definition, with a polynomial upper bound in terms of Z, but an exponential lower bound in terms of a variant parameter phi. On the plane, the upper bound result actually yields the first approximation of a capacity-type SINR problem that is subexponential in alpha.