OpenRaiser/Intern-Atlas huggingface dataset:
On the Link Between Strongly Connected Iteration Graphs and Chaotic Boolean Discrete-Time Dynamical Systems
Venue: arXiv cs.DM 2011
Year: 2011

Chaotic functions are characterized by sensitivity to initial conditions, transitivity, and regularity. Providing new functions with such properties is a real challenge. This work shows that one can associate with any Boolean network a continuous function, whose discrete-time iterations are chaotic if and only if the iteration graph of the Boolean network is strongly connected. Then, sufficient conditions for this strong connectivity are expressed on the interaction graph of this network, leading to a constructive method of chaotic function computation. The whole approach is evaluated in the chaos-based pseudo-random number generation context.
Recovery of a Sparse Integer Solution to an Underdetermined System of Linear Equations
Venue: arXiv cs.IT 2011
Year: 2011

We consider a system of m linear equations in n variables Ax=b where A is a given m x n matrix and b is a given m-vector known to be equal to Ax' for some unknown solution x' that is integer and k-sparse: x' in {0,1}^n and exactly k entries of x' are 1. We give necessary and sufficient conditions for recovering the solution x exactly using an LP relaxation that minimizes l1 norm of x. When A is drawn from a distribution that has exchangeable columns, we show an interesting connection between the recovery probability and a well known problem in geometry, namely the k-set problem. To the best of our knowledge, this connection appears to be new in the compressive sensing literature. We empirically show that for large n if the elements of A are drawn i.i.d. from the normal distribution then the performance of the recovery LP exhibits a phase transition, i.e., for each k there exists a value m' of m such that the recovery always succeeds if m > m' and always fails if m < m'. Using the empirical data we conjecture that m' = nH(k/n)/2 where H(x) = -(x)log_2(x) - (1-x)log_2(1-x) is the binary entropy function.
(MC2)2: A Generic Decision-Making Framework and its Application to Cloud Computing
Venue: arXiv cs.DC 2011
Year: 2011

Cloud computing is a disruptive technology, representing a new model for information technology (IT) solution engineering and management that promises to introduce significant cost savings and other benefits. The adoption of Cloud computing requires a detailed comparison of infrastructure alternatives, taking a number of aspects into careful consideration. Existing methods of evaluation, however, limit decision making to the relative costs of cloud computing, but do not take a broader range of criteria into account. In this paper, we introduce a generic, multi-criteria-based decision framework and an application for Cloud Computing, the Multi-Criteria Comparison Method for Cloud Computing ((MC2)2). The framework and method allow organizations to determine what infrastructure best suits their needs by evaluating and ranking infrastructure alternatives using multiple criteria. Therefore, (MC2)2 offers a way to differentiate infrastructures not only by costs, but also in terms of benefits, opportunities and risks. (MC2)2 can be adapted to facilitate a wide array of decision-making scenarios within the domain of information technology infrastructures, depending on the criteria selected to support the framework.
Efficient Neighbor Discovery for Proximity-Aware Networks
Venue: arXiv cs.IT 2011
Year: 2011

In this work, we propose a fast and energy-efficient neighbor discovery scheme for proximity-aware networks such as wireless ad hoc networks. Discovery efficiency is accomplished by the use of a special discovery signal that provides random multiple access with low transmit power consumption and low synchronization requirement.
Programmable Cellular Automata Based Efficient Parallel AES Encryption Algorithm
Venue: arXiv cs.DC 2011
Year: 2011

Cellular Automata(CA) is a discrete computing model which provides simple, flexible and efficient platform for simulating complicated systems and performing complex computation based on the neighborhoods information. CA consists of two components 1) a set of cells and 2) a set of rules . Programmable Cellular Automata(PCA) employs some control signals on a Cellular Automata(CA) structure. Programmable Cellular Automata were successfully applied for simulation of biological systems, physical systems and recently to design parallel and distributed algorithms for solving task density and synchronization problems. In this paper PCA is applied to develop cryptography algorithms. This paper deals with the cryptography for a parallel AES encryption algorithm based on programmable cellular automata. This proposed algorithm based on symmetric key systems.
Symmetrical Dispersion Compensation For High Speed Optical Links
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, the performance of high speed optical fiber based network is analysed by using dispersion compensating module (DCM). The optimal operating condition of the DCM is obtained by considering dispersion management configurations for the symmetrical system i.e Pre-compensation & Post-compensation. The dispersion compensating fiber (DCF) is tested for a single span, single channel system operating at a speed of 10 Gb/s with a transmitting wavelength of 1550 nm, over 120 km single mode fibre by using the compensating fiber for 24 km,30km and 35Km. So far, most of the investigations for single mode fiber (SMF) transmission at high amplifier spacings in the order of 90 km to 120 km is focused on conventional Non Return to Zero(NRZ) format. The simulation results are validated by analysing the Q-factor and Bit error rate (BER) in the numerical simulator OptSim.
Thematic Analysis and Visualization of Textual Corpus
Venue: arXiv cs.IR 2011
Year: 2011

The semantic analysis of documents is a domain of intense research at present. The works in this domain can take several directions and touch several levels of granularity. In the present work we are exactly interested in the thematic analysis of the textual documents. In our approach, we suggest studying the variation of the theme relevance within a text to identify the major theme and all the minor themes evoked in the text. This allows us at the second level of analysis to identify the relations of thematic associations in a textual corpus. Through the identification and the analysis of these association relations we suggest generating thematic paths allowing users, within the frame work of information search system, to explore the corpus according to their themes of interest and to discover new knowledge by navigating in the thematic association relations.
Incremental Slow Feature Analysis: Adaptive and Episodic Learning from High-Dimensional Input Streams
Venue: arXiv cs.AI 2011
Year: 2011

Slow Feature Analysis (SFA) extracts features representing the underlying causes of changes within a temporally coherent high-dimensional raw sensory input signal. Our novel incremental version of SFA (IncSFA) combines incremental Principal Components Analysis and Minor Components Analysis. Unlike standard batch-based SFA, IncSFA adapts along with non-stationary environments, is amenable to episodic training, is not corrupted by outliers, and is covariance-free. These properties make IncSFA a generally useful unsupervised preprocessor for autonomous learning agents and robots. In IncSFA, the CCIPCA and MCA updates take the form of Hebbian and anti-Hebbian updating, extending the biological plausibility of SFA. In both single node and deep network versions, IncSFA learns to encode its input streams (such as high-dimensional video) by informative slow features representing meaningful abstract environmental properties. It can handle cases where batch SFA fails.
Efficiency Theory: a Unifying Theory for Information, Computation and Intelligence
Venue: arXiv cs.CC 2011
Year: 2011

The paper serves as the first contribution towards the development of the theory of efficiency: a unifying framework for the currently disjoint theories of information, complexity, communication and computation. Realizing the defining nature of the brute force approach in the fundamental concepts in all of the above mentioned fields, the paper suggests using efficiency or improvement over the brute force algorithm as a common unifying factor necessary for the creation of a unified theory of information manipulation. By defining such diverse terms as randomness, knowledge, intelligence and computability in terms of a common denominator we are able to bring together contributions from Shannon, Levin, Kolmogorov, Solomonoff, Chaitin, Yao and many others under a common umbrella of the efficiency theory.
A Novel Multipath Approach to Security in Mobile Ad Hoc Networks (MANETs)
Venue: arXiv cs.CR 2011
Year: 2011

In this paper, we present a novel encryption-less algorithm to enhance security in transmission of data packets across mobile ad hoc networks. The paper hinges on the paradigm of multipath routing and exploits the properties of polynomials. The first step in the algorithm is to transform the data such that it is impossible to obtain any information without possessing the entire transformed data. The algorithm then uses an intuitively simple idea of a jigsaw puzzle to break the transformed data into multiple packets where these packets form the pieces of the puzzle. Then these packets are sent along disjoint paths to reach the receiver. A secure and efficient mechanism is provided to convey the information that is necessary for obtaining the original data at the receiver-end from its fragments in the packets, that is, for solving the jigsaw puzzle. The algorithm is designed to be secure so that no intermediate or unintended node can obtain the entire data. An authentication code is also used to ensure authenticity of every packet.
Decryptable to Your Eyes: Visualization of Security Protocols at the User Interface
Venue: arXiv cs.CR 2011
Year: 2011

The design of authentication protocols, for online banking services in particular and any service that is of sensitive nature in general, is quite challenging. Indeed, enforcing security guarantees has overhead thus imposing additional computation and design considerations that do not always meet usability and user requirements. On the other hand, relaxing assumptions and rigorous security design to improve the user experience can lead to security breaches that can harm the users' trust in the system. In this paper, we demonstrate how careful visualization design can enhance not only the security but also the usability of the authentication process. To that end, we propose a family of visualized authentication protocols, a visualized transaction verification, and a "decryptable to your eyes only" protocol. Through rigorous analysis, we verify that our protocols are immune to many of the challenging authentication attacks applicable in the literature. Furthermore, using an extensive case study on a prototype of our protocols, we highlight the potential of our approach for real-world deployment: we were able to achieve a high level of usability while satisfying stringent security requirements.
On Tractability Aspects of Optimal Resource Allocation in OFDMA Systems
Venue: arXiv cs.NI 2011
Year: 2011

Joint channel and rate allocation with power minimization in orthogonal frequency-division multiple access (OFDMA) has attracted extensive attention. Most of the research has dealt with the development of sub-optimal but low-complexity algorithms. In this paper, the contributions comprise new insights from revisiting tractability aspects of computing optimum. Previous complexity analyses have been limited by assumptions of fixed power on each subcarrier, or power-rate functions that locally grow arbitrarily fast. The analysis under the former assumption does not generalize to problem tractability with variable power, whereas the latter assumption prohibits the result from being applicable to well-behaved power-rate functions. As the first contribution, we overcome the previous limitations by rigorously proving the problem's NP-hardness for the representative logarithmic rate function. Next, we extend the proof to reach a much stronger result, namely that the problem remains NP-hard, even if the channels allocated to each user is restricted to a consecutive block with given size. We also prove that, under these restrictions, there is a special case with polynomial-time tractability. Then, we treat the problem class where the channels can be partitioned into an arbitrarily large but constant number of groups, each having uniform gain for every individual user. For this problem class, we present a polynomial-time algorithm and prove optimality guarantee. In addition, we prove that the recognition of this class is polynomial-time solvable.
Maximum Production of Transmission Messages Rate for Service Discovery Protocols
Venue: arXiv cs.NI 2011
Year: 2011

Minimizing the number of dropped User Datagram Protocol (UDP) messages in a network is regarded as a challenge by researchers. This issue represents serious problems for many protocols particularly those that depend on sending messages as part of their strategy, such us service discovery protocols. This paper proposes and evaluates an algorithm to predict the minimum period of time required between two or more consecutive messages and suggests the minimum queue sizes for the routers, to manage the traffic and minimise the number of dropped messages that has been caused by either congestion or queue overflow or both together. The algorithm has been applied to the Universal Plug and Play (UPnP) protocol using ns2 simulator. It was tested when the routers were connected in two configurations; as a centralized and de centralized. The message length and bandwidth of the links among the routers were taken in the consideration. The result shows Better improvement in number of dropped messages `among the routers.
Networks Utilization Improvements for Service Discovery Performance
Venue: arXiv cs.NI 2011
Year: 2011

Service discovery requests' messages have a vital role in sharing and locating resources in many of service discovery protocols. Sending more messages than a link can handle may cause congestion and loss of messages which dramatically influences the performance of these protocols. Re-send the lost messages result in latency and inefficiency in performing the tasks which user(s) require from the connected nodes. This issue become a serious problem in two cases: first, when the number of clients which performs a service discovery request is increasing, as this result in increasing in the number of sent discovery messages; second, when the network resources such as bandwidth capacity are consumed by other applications. These two cases lead to network congestion and loss of messages. This paper propose an algorithm to improve the services discovery protocols performance by separating each consecutive burst of messages with a specific period of time which calculated regarding the available network resources. It was tested when the routers were connected in two configurations; decentralised and centralised .In addition, this paper explains the impact of increasing the number of clients and the consumed network resources on the proposed algorithm.
The ViP2P Platform: XML Views in P2P
Venue: arXiv cs.DB 2011
Year: 2011

The growing volumes of XML data sources on the Web or produced by enterprises, organizations etc. raise many performance challenges for data management applications. In this work, we are concerned with the distributed, peer-to-peer management of large corpora of XML documents, based on distributed hash table (or DHT, in short) overlay networks. We present ViP2P (standing for Views in Peer-to-Peer), a distributed platform for sharing XML documents based on a structured P2P network infrastructure (DHT). At the core of ViP2P stand distributed materialized XML views, defined by arbitrary XML queries, filled in with data published anywhere in the network, and exploited to efficiently answer queries issued by any network peer. ViP2P allows user queries to be evaluated over XML documents published by peers in two modes. First, a long-running subscription mode, when a query can be registered in the system and receive answers incrementally when and if published data matches the query. Second, queries can also be asked in an ad-hoc, snapshot mode, where results are required immediately and must be computed based on the results of other long-running, subscription queries. ViP2P innovates over other similar DHT-based XML sharing platforms by using a very expressive structured XML query language. This expressivity leads to a very flexible distribution of XML content in the ViP2P network, and to efficient snapshot query execution. ViP2P has been tested in real deployments of hundreds of computers. We present the platform architecture, its internal algorithms, and demonstrate its efficiency and scalability through a set of experiments. Our experimental results outgrow by orders of magnitude similar competitor systems in terms of data volumes, network size and data dissemination throughput.
Fast Hybrid PSO and Tabu Search Approach for Optimization of a Fuzzy Controller
Venue: arXiv cs.SY 2011
Year: 2011

In this paper, a fuzzy controller type Takagi_Sugeno zero order is optimized by the method of hybrid Particle Swarm Optimization (PSO) and Tabu Search (TS). The algorithm automatically adjusts the membership functions of fuzzy controller inputs and the conclusions of fuzzy rules. At each iteration of PSO, we calculate the best solution and we seek the best neighbor by Tabu search, this operation minimizes the number of iterations and computation time while maintaining accuracy and minimum response time. We apply this algorithm to optimize a fuzzy controller for a simple inverted pendulum with three rules.
Using Proximity to Predict Activity in Social Networks
Venue: arXiv cs.SI 2011
Year: 2011

The structure of a social network contains information useful for predicting its evolution. Nodes that are "close" in some sense are more likely to become linked in the future than more distant nodes. We show that structural information can also help predict node activity. We use proximity to capture the degree to which two nodes are "close" to each other in the network. In addition to standard proximity metrics used in the link prediction task, such as neighborhood overlap, we introduce new metrics that model different types of interactions that can occur between network nodes. We argue that the "closer" nodes are in a social network, the more similar will be their activity. We study this claim using data about URL recommendation on social media sites Digg and Twitter. We show that structural proximity of two users in the follower graph is related to similarity of their activity, i.e., how many URLs they both recommend. We also show that given friends' activity, knowing their proximity to the user can help better predict which URLs the user will recommend. We compare the performance of different proximity metrics on the activity prediction task and find that some metrics lead to substantial performance improvements.
Large Scale Correlation Clustering Optimization
Venue: arXiv cs.CV 2011
Year: 2011

Clustering is a fundamental task in unsupervised learning. The focus of this paper is the Correlation Clustering functional which combines positive and negative affinities between the data points. The contribution of this paper is two fold: (i) Provide a theoretic analysis of the functional. (ii) New optimization algorithms which can cope with large scale problems (>100K variables) that are infeasible using existing methods. Our theoretic analysis provides a probabilistic generative interpretation for the functional, and justifies its intrinsic "model-selection" capability. Furthermore, we draw an analogy between optimizing this functional and the well known Potts energy minimization. This analogy allows us to suggest several new optimization algorithms, which exploit the intrinsic "model-selection" capability of the functional to automatically recover the underlying number of clusters. We compare our algorithms to existing methods on both synthetic and real data. In addition we suggest two new applications that are made possible by our algorithms: unsupervised face identification and interactive multi-object segmentation by rough boundary delineation.
Constraint Satisfaction with Counting Quantifiers
Venue: arXiv cs.CC 2011
Year: 2011

We initiate the study of constraint satisfaction problems (CSPs) in the presence of counting quantifiers, which may be seen as variants of CSPs in the mould of quantified CSPs (QCSPs). We show that a single counting quantifier strictly between exists^1:=exists and exists^n:=forall (the domain being of size n) already affords the maximal possible complexity of QCSPs (which have both exists and forall), being Pspace-complete for a suitably chosen template. Next, we focus on the complexity of subsets of counting quantifiers on clique and cycle templates. For cycles we give a full trichotomy -- all such problems are in L, NP-complete or Pspace-complete. For cliques we come close to a similar trichotomy, but one case remains outstanding. Afterwards, we consider the generalisation of CSPs in which we augment the extant quantifier exists^1:=exists with the quantifier exists^j (j not 1). Such a CSP is already NP-hard on non-bipartite graph templates. We explore the situation of this generalised CSP on bipartite templates, giving various conditions for both tractability and hardness -- culminating in a classification theorem for general graphs. Finally, we use counting quantifiers to solve the complexity of a concrete QCSP whose complexity was previously open.
An Alternative Interpretation of Linguistic Variables as Linguistic Finite Automata
Venue: arXiv cs.FL 2011
Year: 2011

Linguistic variables represent crisp information in a form and precision appropriate for the problem. For example, to answer the question "How are you?" one may say "I am fine." the linguistic variables like "fine", so common in everyday speech. In this paper an alternative interpretation of linguistic variables is introduced with the notion of a linguistic description of a value or set of values. The use of linguistic variables in many applications reduces the overall computation complexity of the application. Linguistic variables have been shown to be particularly useful in complex non-linear applications. Here we are applying the concept of reasoning with Linguistic Quantifiers to define the Linguistic Finite Automata along with the expansion of δ^{\box} and λ^{\box} over δand λ.
Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points
Venue: arXiv cs.DM 2011
Year: 2011

Given a set $P$ of $n$ points in the plane, we solve the problems of constructing a geometric planar graph spanning $P$ 1) of minimum degree 2, and 2) which is 2-edge connected, respectively, and has max edge length bounded by a factor of 2 times the optimal; we also show that the factor 2 is best possible given appropriate connectivity conditions on the set $P$, respectively. First, we construct in $O(n\log{n})$ time a geometric planar graph of minimum degree 2 and max edge length bounded by 2 times the optimal. This is then used to construct in $O(n\log n)$ time a 2-edge connected geometric planar graph spanning $P$ with max edge length bounded by $\sqrt{5}$ times the optimal, assuming that the set $P$ forms a connected Unit Disk Graph. Second, we prove that 2 times the optimal is always sufficient if the set of points forms a 2 edge connected Unit Disk Graph and give an algorithm that runs in $O(n^2)$ time. We also show that for $k \in O(\sqrt{n})$, there exists a set $P$ of $n$ points in the plane such that even though the Unit Disk Graph spanning $P$ is $k$-vertex connected, there is no 2-edge connected geometric planar graph spanning $P$ even if the length of its edges is allowed to be up to 17/16.