OpenRaiser/Intern-Atlas huggingface dataset:
Competitive Ratio Analysis of Online Algorithms to Minimize Data Transmission Time in Energy Harvesting Communication System
Venue: arXiv cs.IT 2012
Year: 2012

We consider the optimal online packet scheduling problem in a single-user energy harvesting wireless communication system, where energy is harvested from natural renewable sources, making future energy arrivals instants and amounts random in nature. The most general case of arbitrary energy arrivals is considered where neither the future energy arrival instants or amount, nor their distribution is known. The problem considered is to adaptively change the transmission rate according to the causal energy arrival information, such that the time by which all packets are delivered is minimized. We assume that all bits have arrived and are ready at the source before the transmission begins. For a minimization problem, the utility of an online algorithm is tested by finding its competitive ratio or competitiveness that is defined to be the maximum of the ratio of the gain of the online algorithm with the optimal offline algorithm over all input sequences. We derive a lower and upper bound on the competitive ratio of any online algorithm to minimize the total transmission time in an energy harvesting system. The upper bound is obtained using a `lazy' transmission policy that chooses its transmission power to minimize the transmission time assuming that no further energy arrivals are going to occur in future. The lazy transmission policy is shown to be strictly two-competitive. We also derive an adversarial lower bound that shows that competitive ratio of any online algorithm is at least 1.325.
A comparison of two suffix tree-based document clustering algorithms
Venue: arXiv cs.IR 2012
Year: 2012

Document clustering as an unsupervised approach extensively used to navigate, filter, summarize and manage large collection of document repositories like the World Wide Web (WWW). Recently, focuses in this domain shifted from traditional vector based document similarity for clustering to suffix tree based document similarity, as it offers more semantic representation of the text present in the document. In this paper, we compare and contrast two recently introduced approaches to document clustering based on suffix tree data model. The first is an Efficient Phrase based document clustering, which extracts phrases from documents to form compact document representation and uses a similarity measure based on common suffix tree to cluster the documents. The second approach is a frequent word/word meaning sequence based document clustering, it similarly extracts the common word sequence from the document and uses the common sequence/ common word meaning sequence to perform the compact representation, and finally, it uses document clustering approach to cluster the compact documents. These algorithms are using agglomerative hierarchical document clustering to perform the actual clustering step, the difference in these approaches are mainly based on extraction of phrases, model representation as a compact document, and the similarity measures used for clustering. This paper investigates the computational aspect of the two algorithms, and the quality of results they produced.
Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
Venue: arXiv cs.CC 2012
Year: 2012

We consider chains of random constraint satisfaction models that are spatially coupled across a finite window along the chain direction. We investigate their phase diagram at zero temperature using the survey propagation formalism and the interpolation method. We prove that the SAT-UNSAT phase transition threshold of an infinite chain is identical to the one of the individual standard model, and is therefore not affected by spatial coupling. We compute the survey propagation complexity using population dynamics as well as large degree approximations, and determine the survey propagation threshold. We find that a clustering phase survives coupling. However, as one increases the range of the coupling window, the survey propagation threshold increases and saturates towards the phase transition threshold. We also briefly discuss other aspects of the problem. Namely, the condensation threshold is not affected by coupling, but the dynamic threshold displays saturation towards the condensation one. All these features may provide a new avenue for obtaining better provable algorithmic lower bounds on phase transition thresholds of the individual standard model.
Solving systems of transcendental equations involving the Heun functions
Venue: arXiv cs.NA 2012
Year: 2012

The Heun functions have wide application in modern physics and are expected to succeed the hypergeometrical functions in the physical problems of the 21st century. The numerical work with those functions, however, is complicated and requires filling the gaps in the theory of the Heun functions and also, creating new algorithms able to work with them efficiently. We propose a new algorithm for solving a system of two nonlinear transcendental equations with two complex variables based on the Müller algorithm. The new algorithm is particularly useful in systems featuring the Heun functions and for them, the new algorithm gives distinctly better results than Newton's and Broyden's methods. As an example for its application in physics, the new algorithm was used to find the quasi-normal modes (QNM) of Schwarzschild black hole described by the Regge-Wheeler equation. The numerical results obtained by our method are compared with the already published QNM frequencies and are found to coincide to a great extent with them. Also discussed are the QNM of the Kerr black hole, described by the Teukolsky Master equation.
Gossip on Weighted Networks
Venue: arXiv cs.SI 2012
Year: 2012

We investigate how suitable a weighted network is for gossip spreading. The proposed model is based on the gossip spreading model introduced by Lind et.al. on unweighted networks. Weight represents "friendship." Potential spreader prefers not to spread if the victim of gossip is a "close friend". Gossip spreading is related to the triangles and cascades of triangles. It gives more insight about the structure of a network. We analyze gossip spreading on real weighted networks of human interactions. 6 co-occurrence and 7 social pattern networks are investigated. Gossip propagation is found to be a good parameter to distinguish co-occurrence and social pattern networks. As a comparison some miscellaneous networks and computer generated networks based on ER, BA, WS models are also investigated. They are found to be quite different than the human interaction networks.
A note on anti-coordination and social interactions
Venue: arXiv cs.GT 2012
Year: 2012

This note confirms a conjecture of [Bramoullé, Anti-coordination and social interactions, Games and Economic Behavior, 58, 2007: 30-49]. The problem, which we name the maximum independent cut problem, is a restricted version of the MAX-CUT problem, requiring one side of the cut to be an independent set. We show that the maximum independent cut problem does not admit any polynomial time algorithm with approximation ratio better than $n^{1-ε}$, where $n$ is the number of nodes, and $ε$ arbitrarily small, unless P=NP. For the rather special case where each node has a degree of at most four, the problem is still MAXSNP-hard.
Interference-Aware Scheduling for Connectivity in MIMO Ad Hoc Multicast Networks
Venue: arXiv cs.IT 2012
Year: 2012

We consider a multicast scenario involving an ad hoc network of co-channel MIMO nodes in which a source node attempts to share a streaming message with all nodes in the network via some pre-defined multi-hop routing tree. The message is assumed to be broken down into packets, and the transmission is conducted over multiple frames. Each frame is divided into time slots, and each link in the routing tree is assigned one time slot in which to transmit its current packet. We present an algorithm for determining the number of time slots and the scheduling of the links in these time slots in order to optimize the connectivity of the network, which we define to be the probability that all links can achieve the required throughput. In addition to time multiplexing, the MIMO nodes also employ beamforming to manage interference when links are simultaneously active, and the beamformers are designed with the maximum connectivity metric in mind. The effects of outdated channel state information (CSI) are taken into account in both the scheduling and the beamforming designs. We also derive bounds on the network connectivity and sum transmit power in order to illustrate the impact of interference on network performance. Our simulation results demonstrate that the choice of the number of time slots is critical in optimizing network performance, and illustrate the significant advantage provided by multiple antennas in improving network connectivity.
Securing IEEE 802.11G WLAN Using OpenVPN and Its Impact Analysis
Venue: arXiv cs.CR 2012
Year: 2012

Like most advances, wireless LAN poses both opportunities and risks. The evolution of wireless networking in recent years has raised many serious security issues. These security issues are of great concern for this technology as it is being subjected to numerous attacks. Because of the free-space radio transmission in wireless networks, eavesdropping becomes easy and consequently a security breach may result in unauthorized access, information theft, interference and service degradation. Virtual Private Networks (VPNs) have emerged as an important solution to security threats surrounding the use of public networks for private communications. While VPNs for wired line networks have matured in both research and commercial environments, the design and deployment of VPNs for WLAN is still an evolving field. This paper presents an approach to secure IEEE 802.11g WLAN using OpenVPN, a transport layer VPN solution and its impact on performance of IEEE 802.11g WLAN.
Capacity Factors of a Point-to-point Network
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we investigate some properties on capacity factors, which were proposed to investigate the link failure problem from network coding. A capacity factor (CF) of a network is an edge set, deleting which will cause the maximum flow to decrease while deleting any proper subset will not. Generally, a $k$-CF is a minimal (not minimum) edge set which will cause the network maximum flow decrease by $k$. Under point to point acyclic scenario, we characterize all the edges which are contained in some CF, and propose an efficient algorithm to classify. And we show that all edges on some $s$-$t$ path in an acyclic point-to-point acyclic network are contained in some 2-CF. We also study some other properties of CF of point to point network, and a simple relationship with CF in multicast network. On the other hand, some computational hardness results relating to capacity factors are obtained. We prove that deciding whether there is a capacity factor of a cyclic network with size not less a given number is NP-complete, and the time complexity of calculating the capacity rank is lowered bounded by solving the maximal flow. Besides that, we propose the analogous definition of CF on vertices and show it captures edge capacity factors as a special case.
Evaluating polynomials in several variables and their derivatives on a GPU computing processor
Venue: arXiv cs.MS 2012
Year: 2012

In order to obtain more accurate solutions of polynomial systems with numerical continuation methods we use multiprecision arithmetic. Our goal is to offset the overhead of double double arithmetic accelerating the path trackers and in particular Newton's method with a general purpose graphics processing unit. In this paper we describe algorithms for the massively parallel evaluation and differentiation of sparse polynomials in several variables. We report on our implementation of the algorithmic differentiation of products of variables on the NVIDIA Tesla C2050 Computing Processor using the NVIDIA CUDA compiler tools.
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
Venue: arXiv cs.LO 2012
Year: 2012

The Algebraic Dichotomy Conjecture states that the Constraint Satisfaction Problem over a fixed template is solvable in polynomial time if the algebra of polymorphisms associated to the template lies in a Taylor variety, and is NP-complete otherwise. This paper provides two new characterizations of finitely generated Taylor varieties. The first characterization is using absorbing subalgebras and the second one cyclic terms. These new conditions allow us to reprove the conjecture of Bang-Jensen and Hell (proved by the authors) and the characterization of locally finite Taylor varieties using weak near-unanimity terms (proved by McKenzie and Maróti) in an elementary and self-contained way.
Expressing Reachability in Linear Recurrences, as Infinite Determinants and Rational Polynomial Equations
Venue: arXiv cs.DM 2012
Year: 2012

We present two tools, which could be useful in determining whether or not a non-Homogenous Linear Recurrence can reach a desired rational. First, we derive the determinant that is equal to the ith term in a non-Homogenous Linear Recurrence. We use this to derive the infinite determinant that is zero, if and only if, the desired rational can be reached by some term in the recurrence. Second, we derive an infinite summation of rational Polynomials, such that this summation can be equal to 1, if and only if, the desired rational can be reached by some term in the recurrence.
An extension of data automata that captures XPath
Venue: arXiv cs.LO 2012
Year: 2012

We define a new kind of automata recognizing properties of data words or data trees and prove that the automata capture all queries definable in Regular XPath. We show that the automata-theoretic approach may be applied to answer decidability and expressibility questions for XPath.
Topological Trends of Internet Content Providers
Venue: arXiv cs.NI 2012
Year: 2012

The Internet is constantly changing, and its hierarchy was recently shown to become flatter. Recent studies of inter-domain traffic showed that large content providers drive this change by bypassing tier-1 networks and reaching closer to their users, enabling them to save transit costs and reduce reliance of transit networks as new services are being deployed, and traffic shaping is becoming increasingly popular. In this paper we take a first look at the evolving connectivity of large content provider networks, from a topological point of view of the autonomous systems (AS) graph. We perform a 5-year longitudinal study of the topological trends of large content providers, by analyzing several large content providers and comparing these trends to those observed for large tier-1 networks. We study trends in the connectivity of the networks, neighbor diversity and geographical spread, their hierarchy, the adoption of IXPs as a convenient method for peering, and their centrality. Our observations indicate that content providers gradually increase and diversify their connectivity, enabling them to improve their centrality in the graph, and as a result, tier-1 networks lose dominance over time.
Order Handling in Convergent Environments
Venue: arXiv cs.SE 2012
Year: 2012

The rapid development of IT&T technology had big impact on the traditional telecommunications market, transforming it from monopolistic market to highly competitive high-tech market where new services are required to be created frequently. This paper aims to describe a design approach that puts order management process (as part of enterprise application integration) in function of rapid service creation. In the text we will present a framework for collaborative order handling supporting convergent services. The design splits the order handling processes in convergent environments in three business process groups: order capture, order management and order fulfillment. The paper establishes abstract framework for order handling and provides design guidelines for transaction handling implementation based on the checkpoint and inverse command strategy. The proposed design approach is based in a convergent telecommunication environment. Same principles are applicable in solving problems of collaboration in function of order processing in any given heterogeneous environment.
Average-case analysis of perfect sorting by reversals (Journal Version)
Venue: arXiv cs.DM 2012
Year: 2012

Perfect sorting by reversals, a problem originating in computational genomics, is the process of sorting a signed permutation to either the identity or to the reversed identity permutation, by a sequence of reversals that do not break any common interval. Bérard et al. (2007) make use of strong interval trees to describe an algorithm for sorting signed permutations by reversals. Combinatorial properties of this family of trees are essential to the algorithm analysis. Here, we use the expected value of certain tree parameters to prove that the average run-time of the algorithm is at worst, polynomial, and additionally, for sufficiently long permutations, the sorting algorithm runs in polynomial time with probability one. Furthermore, our analysis of the subclass of commuting scenarios yields precise results on the average length of a reversal, and the average number of reversals.
Some Recommended Protection Technologies for Cyber Crime Based on Social Engineering Techniques -- Phishing
Venue: arXiv cs.CR 2012
Year: 2012

Phishing (password + fishing) is a form of cyber crime based on social engineering and site spoofing techniques. The name of 'phishing' is a conscious misspelling of the word 'fishing' and involves stealing confidential data from a user's computer and subsequently using the data to steal the user's money. In this paper, we study, discuss and propose the phishing attack stages and types, technologies for detection of phishing web pages, and conclude our paper with some important recommendations for preventing phishing for both consumer and company.
Information Analysis Infrastructure for Diagnosis
Venue: arXiv cs.AR 2012
Year: 2012

A high-speed multiprocessor architecture for brain-like analyzing information represented in analytic, graph- and table forms of associative relations to search, recognize and make a decision in n-dimensional vector discrete space is offered. Vector-logical process models of actual applications, where the quality of solution is estimated by the proposed integral non-arithmetical metric of the interaction between binary vectors, are described. The theoretical proof of the metric for a vector logical space and the quality criteria for estimating solutions is created.
Network Coding Capacity Regions via Entropy Functions
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we use entropy functions to characterise the set of rate-capacity tuples achievable with either zero decoding error, or vanishing decoding error, for general network coding problems. We show that when sources are colocated, the outer bound obtained by Yeung, A First Course in Information Theory, Section 15.5 (2002) is tight and the sets of zero-error achievable and vanishing-error achievable rate-capacity tuples are the same. We also characterise the set of zero-error and vanishing-error achievable rate capacity tuples for network coding problems subject to linear encoding constraints, routing constraints (where some or all nodes can only perform routing) and secrecy constraints. Finally, we show that even for apparently simple networks, design of optimal codes may be difficult. In particular, we prove that for the incremental multicast problem and for the single-source secure network coding problem, characterisation of the achievable set is very hard and linear network codes may not be optimal.
Gibbs-Shannon Entropy and Related Measures: Tsallis Entropy
Venue: arXiv cs.IT 2012
Year: 2012

In this research paper, it is proved that an approximation to Gibbs-Shannon entropy measure naturally leads to Tsallis entropy for the real parameter q =2 . Several interesting measures based on the input as well as output of a discrete memoryless channel are provided and some of the properties of those measures are discussed. It is expected that these results will be of utility in Information Theoretic research.
A type system for PSPACE derived from light linear logic
Venue: arXiv cs.CC 2012
Year: 2012

We present a polymorphic type system for lambda calculus ensuring that well-typed programs can be executed in polynomial space: dual light affine logic with booleans (DLALB). To build DLALB we start from DLAL (which has a simple type language with a linear and an intuitionistic type arrow, as well as one modality) which characterizes FPTIME functions. In order to extend its expressiveness we add two boolean constants and a conditional constructor in the same way as with the system STAB. We show that the value of a well-typed term can be computed by an alternating machine in polynomial time, thus such a term represents a program of PSPACE (given that PSPACE = APTIME). We also prove that all polynomial space decision functions can be represented in DLALB. Therefore DLALB characterizes PSPACE predicates.
Formal security analysis of registration protocols for interactive systems: a methodology and a case of study
Venue: arXiv cs.CR 2012
Year: 2012

In this work we present and formally analyze CHAT-SRP (CHAos based Tickets-Secure Registration Protocol), a protocol to provide interactive and collaborative platforms with a cryptographically robust solution to classical security issues. Namely, we focus on the secrecy and authenticity properties while keeping a high usability. In this sense, users are forced to blindly trust the system administrators and developers. Moreover, as far as we know, the use of formal methodologies for the verification of security properties of communication protocols isn't yet a common practice. We propose here a methodology to fill this gap, i.e., to analyse both the security of the proposed protocol and the pertinence of the underlying premises. In this concern, we propose the definition and formal evaluation of a protocol for the distribution of digital identities. Once distributed, these identities can be used to verify integrity and source of information. We base our security analysis on tools for automatic verification of security protocols widely accepted by the scientific community, and on the principles they are based upon. In addition, it is assumed perfect cryptographic primitives in order to focus the analysis on the exchange of protocol messages. The main property of our protocol is the incorporation of tickets, created using digests of chaos based nonces (numbers used only once) and users' personal data. Combined with a multichannel authentication scheme with some previous knowledge, these tickets provide security during the whole protocol by univocally linking each registering user with a single request. [..]
Throughput Optimal Multi-user Scheduling via Hierarchical Modulation
Venue: arXiv cs.NI 2012
Year: 2012

We investigate the network stability problem when two users are scheduled simultaneously. The key idea is to simultaneously transmit to more than one users experiencing different channel conditions by employing hierarchical modulation. For two-user scheduling problem, we develop a throughput-optimal algorithm which can stabilize the network whenever this is possible. In addition, we analytically prove that the proposed algorithm achieves larger achievable rate region compared to the conventional Max-Weight algorithm which employs uniform modulation and transmits a single user. We demonstrate the efficacy of the algorithm on a realistic simulation environment using the parameters of High Data Rate protocol in a Code Division Multiple Access system. Simulation results show that with the proposed algorithm, the network can carry higher user traffic with lower delays.