OpenRaiser/Intern-Atlas huggingface dataset:
Provable Security of Networks
Venue: arXiv cs.SI 2013
Year: 2013

We propose a definition of {\it security} and a definition of {\it robustness} of networks against the cascading failure models of deliberate attacks and random errors respectively, and investigate the principles of the security and robustness of networks. We propose a {\it security model} such that networks constructed by the model are provably secure against any attacks of small sizes under the cascading failure models, and simultaneously follow a power law, and have the small world property with a navigating algorithm of time complex $O(\log n)$. It is shown that for any network $G$ constructed from the security model, $G$ satisfies some remarkable topological properties, including: (i) the {\it small community phenomenon}, that is, $G$ is rich in communities of the form $X$ of size poly logarithmic in $\log n$ with conductance bounded by $O(\frac{1}{|X|^β})$ for some constant $β$, (ii) small diameter property, with diameter $O(\log n)$ allowing a navigation by a $O(\log n)$ time algorithm to find a path for arbitrarily given two nodes, and (iii) power law distribution, and satisfies some probabilistic and combinatorial principles, including the {\it degree priority theorem}, and {\it infection-inclusion theorem}. By using these principles, we show that a network $G$ constructed from the security model is secure for any attacks of small scales under both the uniform threshold and random threshold cascading failure models. Our security theorems show that networks constructed from the security model are provably secure against any attacks of small sizes, for which natural selections of {\it homophyly, randomness} and {\it preferential attachment} are the underlying mechanisms.
Linear Convergence on Positively Homogeneous Functions of a Comparison Based Step-Size Adaptive Randomized Search: the (1+1) ES with Generalized One-fifth Success Rule
Venue: arXiv cs.NA 2013
Year: 2013

In the context of unconstraint numerical optimization, this paper investigates the global linear convergence of a simple probabilistic derivative-free optimization algorithm (DFO). The algorithm samples a candidate solution from a standard multivariate normal distribution scaled by a step-size and centered in the current solution. This solution is accepted if it has a better objective function value than the current one. Crucial to the algorithm is the adaptation of the step-size that is done in order to maintain a certain probability of success. The algorithm, already proposed in the 60's, is a generalization of the well-known Rechenberg's $(1+1)$ Evolution Strategy (ES) with one-fifth success rule which was also proposed by Devroye under the name compound random search or by Schumer and Steiglitz under the name step-size adaptive random search. In addition to be derivative-free, the algorithm is function-value-free: it exploits the objective function only through comparisons. It belongs to the class of comparison-based step-size adaptive randomized search (CB-SARS). For the convergence analysis, we follow the methodology developed in a companion paper for investigating linear convergence of CB-SARS: by exploiting invariance properties of the algorithm, we turn the study of global linear convergence on scaling-invariant functions into the study of the stability of an underlying normalized Markov chain (MC). We hence prove global linear convergence by studying the stability (irreducibility, recurrence, positivity, geometric ergodicity) of the normalized MC associated to the $(1+1)$-ES. More precisely, we prove that starting from any initial solution and any step-size, linear convergence with probability one and in expectation occurs. Our proof holds on unimodal functions that are the composite of strictly increasing functions by positively homogeneous functions with degree $α$ (assumed also to be continuously differentiable). This function class includes composite of norm functions but also non-quasi convex functions. Because of the composition by a strictly increasing function, it includes non continuous functions. We find that a sufficient condition for global linear convergence is the step-size increase on linear functions, a condition typically satisfied for standard parameter choices. While introduced more than 40 years ago, we provide here the first proof of global linear convergence for the $(1+1)$-ES with generalized one-fifth success rule and the first proof of linear convergence for a CB-SARS on such a class of functions that includes non-quasi convex and non-continuous functions. Our proof also holds on functions where linear convergence of some CB-SARS was previously proven, namely convex-quadratic functions (including the well-know sphere function).
Optimal Checkpointing Period: Time vs. Energy
Venue: arXiv cs.DC 2013
Year: 2013

This short paper deals with parallel scientific applications using non-blocking and periodic coordinated checkpointing to enforce resilience. We provide a model and detailed formulas for total execution time and consumed energy. We characterize the optimal period for both objectives, and we assess the range of time/energy trade-offs to be made by instantiating the model with a set of realistic scenarios for Exascale systems. We give a particular emphasis to I/O transfers, because the relative cost of communication is expected to dramatically increase, both in terms of latency and consumed energy, for future Exascale platforms.
Application of Data Mining In Marketing
Venue: arXiv cs.DB 2013
Year: 2013

One of the most important problems in modern finance is finding efficient ways to summarize and visualize the stock market data to give individuals or institutions useful information about the market behavior for investment decisions. The enormous amount of valuable data generated by the stock market has attracted researchers to explore this problem domain using different methodologies. Potential significant benefits of solving these problems motivated extensive research for years. The research in data mining has gained a high attraction due to the importance of its applications and the increasing generation information. This paper provides an overview of application of data mining techniques such as decision tree. Also, this paper reveals progressive applications in addition to existing gap and less considered area and determines the future works for researchers.
Using Cache-coloring to Mitigate Inter-set Write Variation in Non-volatile Caches
Venue: arXiv cs.AR 2013
Year: 2013

In recent years, researchers have explored use of non-volatile devices such as STT-RAM (spin torque transfer RAM) for designing on-chip caches, since they provide high density and consume low leakage power. A common limitation of all non-volatile devices is their limited write endurance. Further, since existing cache management policies are write-variation unaware, excessive writes to a few blocks may lead to a quick failure of the whole cache. We propose an architectural technique for wear-leveling of non-volatile last level caches (LLCs). Our technique uses cache-coloring approach which adds a software-controlled mapping layer between groups of physical pages and cache sets. Periodically the mapping is altered to ensure that write-traffic can be spread uniformly to different sets of the cache to achieve wear-leveling. Simulations performed with an x86-64 simulator and SPEC2006 benchmarks show that our technique reduces the worst-case writes to cache blocks and thus improves the cache lifetime by 4.07X.
Majority is not Enough: Bitcoin Mining is Vulnerable
Venue: arXiv cs.CR 2013
Year: 2013

The Bitcoin cryptocurrency records its transactions in a public log called the blockchain. Its security rests critically on the distributed protocol that maintains the blockchain, run by participants called miners. Conventional wisdom asserts that the protocol is incentive-compatible and secure against colluding minority groups, i.e., it incentivizes miners to follow the protocol as prescribed. We show that the Bitcoin protocol is not incentive-compatible. We present an attack with which colluding miners obtain a revenue larger than their fair share. This attack can have significant consequences for Bitcoin: Rational miners will prefer to join the selfish miners, and the colluding group will increase in size until it becomes a majority. At this point, the Bitcoin system ceases to be a decentralized currency. Selfish mining is feasible for any group size of colluding miners. We propose a practical modification to the Bitcoin protocol that protects against selfish mining pools that command less than 1/4 of the resources. This threshold is lower than the wrongly assumed 1/2 bound, but better than the current reality where a group of any size can compromise the system.
Application of Cybernetics and Control Theory for a New Paradigm in Cybersecurity
Venue: arXiv cs.CR 2013
Year: 2013

A significant limitation of current cyber security research and techniques is its reactive and applied nature. This leads to a continuous 'cyber cycle' of attackers scanning networks, developing exploits and attacking systems, with defenders detecting attacks, analyzing exploits and patching systems. This reactive nature leaves sensitive systems highly vulnerable to attack due to un-patched systems and undetected exploits. Some current research attempts to address this major limitation by introducing systems that implement moving target defense. However, these ideas are typically based on the intuition that a moving target defense will make it much harder for attackers to find and scan vulnerable systems, and not on theoretical mathematical foundations. The continuing lack of fundamental science and principles for developing more secure systems has drawn increased interest into establishing a 'science of cyber security'. This paper introduces the concept of using cybernetics, an interdisciplinary approach of control theory, systems theory, information theory and game theory applied to regulatory systems, as a foundational approach for developing cyber security principles. It explores potential applications of cybernetics to cyber security from a defensive perspective, while suggesting the potential use for offensive applications. Additionally, this paper introduces the fundamental principles for building non-stationary systems, which is a more general solution than moving target defenses. Lastly, the paper discusses related works concerning the limitations of moving target defense and one implementation based on non-stationary principles.
Pebbling Arguments for Tree Evaluation
Venue: arXiv cs.CC 2013
Year: 2013

The Tree Evaluation Problem was introduced by Cook et al. in 2010 as a candidate for separating P from L and NL. The most general space lower bounds known for the Tree Evaluation Problem require a semantic restriction on the branching programs and use a connection to well-known pebble games to generate a bottleneck argument. These bounds are met by corresponding upper bounds generated by natural implementations of optimal pebbling algorithms. In this paper we extend these ideas to a variety of restricted families of both deterministic and non-deterministic branching programs, proving tight lower bounds under these restricted models. We also survey and unify known lower bounds in our "pebbling argument" framework.
Normal Numbers and the Borel Hierarchy
Venue: arXiv cs.LO 2013
Year: 2013

We show that the set of absolutely normal numbers is $\mathbf Π^0_3$-complete in the Borel hierarchy of subsets of real numbers. Similarly, the set of absolutely normal numbers is $Π^0_3$-complete in the effective Borel hierarchy.
Sequential Mining: Patterns and Algorithms Analysis
Venue: arXiv cs.DB 2013
Year: 2013

This paper presents and analysis the common existing sequential pattern mining algorithms. It presents a classifying study of sequential pattern-mining algorithms into five extensive classes. First, on the basis of Apriori-based algorithm, second on Breadth First Search-based strategy, third on Depth First Search strategy, fourth on sequential closed-pattern algorithm and five on the basis of incremental pattern mining algorithms. At the end, a comparative analysis is done on the basis of important key features supported by various algorithms. This study gives an enhancement in the understanding of the approaches of sequential pattern mining.
Rough matroids based on coverings
Venue: arXiv cs.AI 2013
Year: 2013

The introduction of covering-based rough sets has made a substantial contribution to the classical rough sets. However, many vital problems in rough sets, including attribution reduction, are NP-hard and therefore the algorithms for solving them are usually greedy. Matroid, as a generalization of linear independence in vector spaces, it has a variety of applications in many fields such as algorithm design and combinatorial optimization. An excellent introduction to the topic of rough matroids is due to Zhu and Wang. On the basis of their work, we study the rough matroids based on coverings in this paper. First, we investigate some properties of the definable sets with respect to a covering. Specifically, it is interesting that the set of all definable sets with respect to a covering, equipped with the binary relation of inclusion $\subseteq$, constructs a lattice. Second, we propose the rough matroids based on coverings, which are a generalization of the rough matroids based on relations. Finally, some properties of rough matroids based on coverings are explored. Moreover, an equivalent formulation of rough matroids based on coverings is presented. These interesting and important results exhibit many potential connections between rough sets and matroids.
On the Lattice Isomorphism Problem
Venue: arXiv cs.DS 2013
Year: 2013

We study the Lattice Isomorphism Problem (LIP), in which given two lattices L_1 and L_2 the goal is to decide whether there exists an orthogonal linear transformation mapping L_1 to L_2. Our main result is an algorithm for this problem running in time n^{O(n)} times a polynomial in the input size, where n is the rank of the input lattices. A crucial component is a new generalized isolation lemma, which can isolate n linearly independent vectors in a given subset of Z^n and might be useful elsewhere. We also prove that LIP lies in the complexity class SZK.
Comparative Performance Analysis of Intel Xeon Phi, GPU, and CPU
Venue: arXiv cs.DC 2013
Year: 2013

We investigate and characterize the performance of an important class of operations on GPUs and Many Integrated Core (MIC) architectures. Our work is motivated by applications that analyze low-dimensional spatial datasets captured by high resolution sensors, such as image datasets obtained from whole slide tissue specimens using microscopy image scanners. We identify the data access and computation patterns of operations in object segmentation and feature computation categories. We systematically implement and evaluate the performance of these core operations on modern CPUs, GPUs, and MIC systems for a microscopy image analysis application. Our results show that (1) the data access pattern and parallelization strategy employed by the operations strongly affect their performance. While the performance on a MIC of operations that perform regular data access is comparable or sometimes better than that on a GPU; (2) GPUs are significantly more efficient than MICs for operations and algorithms that irregularly access data. This is a result of the low performance of the latter when it comes to random data access; (3) adequate coordinated execution on MICs and CPUs using a performance aware task scheduling strategy improves about 1.29x over a first-come-first-served strategy. The example application attained an efficiency of 84% in an execution with of 192 nodes (3072 CPU cores and 192 MICs).
An asymptotic formula in q for the number of [n,k] q-ary MDS codes
Venue: arXiv cs.IT 2013
Year: 2013

We obtain an asymptotic formula in q for the number of MDS codes of length n and dimension k over a finite field with q elements.
Idea Inheritance, Originality, and Collective Innovation
Venue: arXiv cs.HC 2013
Year: 2013

In order to create new products, inventors search and combine previous ideas. Few studies have examined the characteristics of search that lead to new products; most have focused on patent citations, which are often retrospective and may not reflect the usefulness of inventions. Through the analysis of collaborations in an online virtual community, the impact of originality on popularity and practicality is tested. These tests in turn are based on a method for measuring the distance between 3D shapes. In sum, this paper presents a new method for gauging innovation, and suggests ways of further understanding the role technology plays in encouraging creativity. From an organization perspective, this work provides insights into the creative process, and in particular the open innovation process, in which thousands of individuals together evolve designs, without belonging to the same corporate structure, without claiming IP rights, without exchanging money.
Resource Allocation for Cost Minimization in Limited Feedback MU-MIMO Systems with Delay Guarantee
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we design a resource allocation framework for the delay-sensitive Multi-User MIMO (MU-MIMO) broadcast system with limited feedback. Considering the scarcity and interrelation of the transmit power and feedback bandwidth, it is imperative to optimize the two resources in a joint and efficient manner while meeting the delay-QoS requirement. Based on the effective bandwidth theory, we first obtain a closed-form expression of average violation probability with respect to a given delay requirement as a function of transmit power and codebook size of feedback channel. By minimizing the total resource cost, we derive an optimal joint resource allocation scheme, which can flexibly adjust the transmit power and feedback bandwidth according to the characteristics of the system. Moreover, through asymptotic analysis, some simple resource allocation schemes are presented. Finally, the theoretical claims are validated by numerical results.
Connectivity for matroids based on rough sets
Venue: arXiv cs.AI 2013
Year: 2013

In mathematics and computer science, connectivity is one of the basic concepts of matroid theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems. The connectivity of a matroid is an important measure of its robustness as a network. Therefore, it is very necessary to investigate the conditions under which a matroid is connected. In this paper, the connectivity for matroids is studied through relation-based rough sets. First, a symmetric and transitive relation is introduced from a general matroid and its properties are explored from the viewpoint of matroids. Moreover, through the relation introduced by a general matroid, an undirected graph is generalized. Specifically, the connection of the graph can be investigated by the relation-based rough sets. Second, we study the connectivity for matroids by means of relation-based rough sets and some conditions under which a general matroid is connected are presented. Finally, it is easy to prove that the connectivity for a general matroid with some special properties and its induced undirected graph is equivalent. These results show an important application of relation-based rough sets to matroids.
A Dual-Beam Method-of-Images 3D Searchlight BSSRDF
Venue: arXiv cs.GR 2013
Year: 2013

We present a novel BSSRDF for rendering translucent materials. Angular effects lacking in previous BSSRDF models are incorporated by using a dual-beam formulation. We employ a Placzek's Lemma interpretation of the method of images and discard diffusion theory. Instead, we derive a plane-parallel transformation of the BSSRDF to form the associated BRDF and optimize the image confiurations such that the BRDF is close to the known analytic solutions for the associated albedo problem. This ensures reciprocity, accurate colors, and provides an automatic level-of-detail transition for translucent objects that appear at various distances in an image. Despite optimizing the subsurface fluence in a plane-parallel setting, we find that this also leads to fairly accurate fluence distributions throughout the volume in the original 3D searchlight problem. Our method-of-images modifications can also improve the accuracy of previous BSSRDFs.
Validation of a Control Algorithm for Human-like Reaching Motion using 7-DOF Arm and 19-DOF Hand-Arm Systems
Venue: arXiv cs.RO 2013
Year: 2013

This technical report gives an overview of our work on control algorithms dealing with redundant robot systems for achieving human-like motion characteristics. Previously, we developed a novel control law to exhibit human-motion characteristics in redundant robot arm systems as well as arm-trunk systems for reaching tasks [1], [2]. This newly developed method nullifies the need for the computation of pseudo-inverse of Jacobian while the formulation and optimization of any artificial performance index is not necessary. The time-varying properties of the muscle stiffness and damping as well as the low-pass filter characteristics of human muscles have been modeled by the proposed control law to generate human-motion characteristics for reaching motion like quasi-straight line trajectory of the end-effector and symmetric bell shaped velocity profile. This report focuses on the experiments performed using a 7-DOF redundant robot-arm system which proved the effectiveness of this algorithm in imitating human-like motion characteristics. In addition, we extended this algorithm to a 19-DOF Hand-Arm System for a reach-to-grasp task. Simulations using the 19-DOF Hand-Arm System show the effectiveness of the proposed scheme for effective human-like hand-arm coordination in reach-to-grasp tasks for pinch and envelope grasps on objects of different shapes such as a box, a cylinder, and a sphere.
Polyhedrons and Perceptrons Are Functionally Equivalent
Venue: arXiv cs.NE 2013
Year: 2013

Mathematical definitions of polyhedrons and perceptron networks are discussed. The formalization of polyhedrons is done in a rather traditional way. For networks, previously proposed systems are developed. Perceptron networks in disjunctive normal form (DNF) and conjunctive normal forms (CNF) are introduced. The main theme is that single output perceptron neural networks and characteristic functions of polyhedrons are one and the same class of functions. A rigorous formulation and proof that three layers suffice is obtained. The various constructions and results are among several steps required for algorithms that replace incremental and statistical learning with more efficient, direct and exact geometric methods for calculation of perceptron architecture and weights.
Performance Modeling of BitTorrent Peer-to-Peer File Sharing Networks
Venue: arXiv cs.NI 2013
Year: 2013

BitTorrent is undoubtedly the most popular P2P file sharing application on today's Internet. The widespread popularity of BitTorrent has attracted a great deal of attention from networking researchers who conducted various performance studies on it. This paper presents a comprehensive survey of analytical performance modeling techniques for BitTorrent networks. The performance models examined in this study include deterministic models, Markov chain models, fluid flow models, and queuing network models. These models evaluate the performance metrics of BitTorrent networks at different regimes with various realistic factors considered. Furthermore, a comparative analysis is conducted on those modeling techniques in the aspects of complexity, accuracy, extensibility, and scalability.