OpenRaiser/Intern-Atlas huggingface dataset:
On Generating Permutations Under User-Defined Constraints
Venue: arXiv cs.DM 2013
Year: 2013

In this paper, a method to generate permutations of a string under a set of constraints decided by the user is presented. The required permutations are generated without generating all the permutations.
MAC Address as a Key for Data Encryption
Venue: arXiv cs.CR 2013
Year: 2013

In computer networking, the Media Access Control (MAC) address is a unique value associated with a network adapter. MAC addresses are also known as hardware addresses or physical addresses. TCP/IP and other mainstream networking architectures generally adopt the OSI model. MAC addresses function at the data link layer (layer 2 in the OSI model). They allow computers to uniquely identify themselves on a network at this relatively low level. In this paper, suggested data encryption technique is presented by using the MAC address as a key that is used to authenticate the receiver device like PC, mobile phone, laptop or any other devices that is connected to the network. This technique was tested on some data, visual and numerical measurements were used to check the strength and performance of the technique. The experiments showed that the suggested technique can be used easily to encrypt data that is transmitted through networks.
Planning based on classification by induction graph
Venue: arXiv cs.AI 2013
Year: 2013

In Artificial Intelligence, planning refers to an area of research that proposes to develop systems that can automatically generate a result set, in the form of an integrated decision-making system through a formal procedure, known as plan. Instead of resorting to the scheduling algorithms to generate plans, it is proposed to operate the automatic learning by decision tree to optimize time. In this paper, we propose to build a classification model by induction graph from a learning sample containing plans that have an associated set of descriptors whose values change depending on each plan. This model will then operate for classifying new cases by assigning the appropriate plan.
Sampling Content Distributed Over Graphs
Venue: arXiv cs.SI 2013
Year: 2013

Despite recent effort to estimate topology characteristics of large graphs (i.e., online social networks and peer-to-peer networks), little attention has been given to develop a formal methodology to characterize the vast amount of content distributed over these networks. Due to the large scale nature of these networks, exhaustive enumeration of this content is computationally prohibitive. In this paper, we show how one can obtain content properties by sampling only a small fraction of vertices. We first show that when sampling is naively applied, this can produce a huge bias in content statistics (i.e., average number of content duplications). To remove this bias, one may use maximum likelihood estimation to estimate content characteristics. However our experimental results show that one needs to sample most vertices in the graph to obtain accurate statistics using such a method. To address this challenge, we propose two efficient estimators: special copy estimator (SCE) and weighted copy estimator (WCE) to measure content characteristics using available information in sampled contents. SCE uses the special content copy indicator to compute the estimate, while WCE derives the estimate based on meta-information in sampled vertices. We perform experiments to show WCE and SCE are cost effective and also ``{\em asymptotically unbiased}''. Our methodology provides a new tool for researchers to efficiently query content distributed in large scale networks.
A Categorical Theory of Patches
Venue: arXiv cs.LO 2013
Year: 2013

When working with distant collaborators on the same documents, one often uses a version control system, which is a program tracking the history of files and helping importing modifications brought by others as patches. The implementation of such a system requires to handle lots of situations depending on the operations performed by users on files, and it is thus difficult to ensure that all the corner cases have been correctly addressed. Here, instead of verifying the implementation of such a system, we adopt a complementary approach: we introduce a theoretical model, which is defined abstractly by the universal property that it should satisfy, and work out a concrete description of it. We begin by defining a category of files and patches, where the operation of merging the effect of two coinitial patches is defined by pushout. Since two patches can be incompatible, such a pushout does not necessarily exist in the category, which raises the question of which is the correct category to represent and manipulate files in conflicting state. We provide an answer by investigating the free completion of the category of files under finite colimits, and give an explicit description of this category: its objects are finite sets labeled by lines equipped with a transitive relation and morphisms are partial functions respecting labeling and relations.
Scheduling Meets Fixed-Parameter Tractability
Venue: arXiv cs.DS 2013
Year: 2013

Fixed-parameter tractability analysis and scheduling are two core domains of combinatorial optimization which led to deep understanding of many important algorithmic questions. However, even though fixed-parameter algorithms are appealing for many reasons, no such algorithms are known for many fundamental scheduling problems. In this paper we present the first fixed-parameter algorithms for classical scheduling problems such as makespan minimization, scheduling with job-dependent cost functions-one important example being weighted flow time-and scheduling with rejection. To this end, we identify crucial parameters that determine the problems' complexity. In particular, we manage to cope with the problem complexity stemming from numeric input values, such as job processing times, which is usually a core bottleneck in the design of fixed-parameter algorithms. We complement our algorithms with W[1]-hardness results showing that for smaller sets of parameters the respective problems do not allow FPT-algorithms. In particular, our positive and negative results for scheduling with rejection explore a research direction proposed by Dániel Marx. We hope that our contribution yields a new and fresh perspective on scheduling and fixed-parameter algorithms and will lead to further fruitful interdisciplinary research connecting these two areas.
Congestion Control Technique Using Intelligent Traffic and Vanet
Venue: arXiv cs.NI 2013
Year: 2013

Road traffic jams is a most important problem in nearly all cities around the world, especially in developing regions resulting in enormous delays, increased fuel wastage and monetary losses. In this paper, we have obtained an in-sight idea of simulating real world scenario of a critical region where traffic congestion is very high. As it is not easy to set up and implement such a complicated system in real world before knowing the impact of all parameters used in Vehicle Ad hoc Network (VANET), a small real world area i.e. Jamshedpur Regal area was taken into consideration, for studying the impact of mobility in the VANET. Traffic movement has been deployed across the area under consideration using one of the realistic vehicular mobility models. The behavior of this network was simulated using SUMO and NS2 to study the impact of traffic and traffic lights at the intersection on packet transmission over Vehicle to Vehicle (V2V) communication using Ad hoc On Demand Vector (AODV) routing protocol and IEEE 802.11 standard. From the traffic simulation results, it is proved that congestion problem for the given sample map with traffic lights and predefined flow can be solved. There was negligible congestion at lanes when traffic logic was changed in accordance with allowing flow with high traffic overload to have high priority than those with low load.
A Novel Multifactor Authentication System Ensuring Usability and Security
Venue: arXiv cs.CR 2013
Year: 2013

User authentication is one of the most important part of information security. Computer security most commonly depends on passwords to authenticate human users. Password authentication systems will be either been usable but not secure, or secure but not usable. While there are different types of authentication systems available alphanumeric password is the most commonly used authentication mechanism. But this method has significant drawbacks. An alternative solution to the text based authentication is Graphical User Authentication based on the fact that humans tends to remember images better than text. Graphical password authentication systems provide passwords which are easy to be created and remembered by the user. However, the main issues of simple graphical password techniques are shoulder surfing attack and image gallery attack. Studies reveals that most of the graphical passwords are either secure but not usable or usable but not secure. In this paper, a new technique that uses cued click point graphical password method along with the one-time session key is proposed. The goal is to propose a new authentication mechanism using graphical password to achieve higher security and better usability levels. The result of the system testing is evaluated and it reveals that the proposed system ensures security and usability to a great extent.
Synthesis for Polynomial Lasso Programs
Venue: arXiv cs.LO 2013
Year: 2013

We present a method for the synthesis of polynomial lasso programs. These programs consist of a program stem, a set of transitions, and an exit condition, all in the form of algebraic assertions (conjunctions of polynomial equalities). Central to this approach is the discovery of non-linear (algebraic) loop invariants. We extend Sankaranarayanan, Sipma, and Manna's template-based approach and prove a completeness criterion. We perform program synthesis by generating a constraint whose solution is a synthesized program together with a loop invariant that proves the program's correctness. This constraint is non-linear and is passed to an SMT solver. Moreover, we can enforce the termination of the synthesized program with the support of test cases.
Largest chordal and interval subgraphs faster than 2^n
Venue: arXiv cs.DS 2013
Year: 2013

We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time $O(2^{λn})$ for some $λ<1$. These are the first algorithms breaking the trivial $2^n n^{O(1)}$ bound of the brute-force search for these problems.
A generalized evidence distance
Venue: arXiv cs.AI 2013
Year: 2013

Dempster-Shafer theory of evidence (D-S theory) is widely used in uncertain information process. The basic probability assignment(BPA) is a key element in D-S theory. How to measure the distance between two BPAs is an open issue. In this paper, a new method to measure the distance of two BPAs is proposed. The proposed method is a generalized of existing evidence distance. Numerical examples are illustrated that the proposed method can overcome the shortcomings of existing methods.
A hybrid decision support system : application on healthcare
Venue: arXiv cs.AI 2013
Year: 2013

Many systems based on knowledge, especially expert systems for medical decision support have been developed. Only systems are based on production rules, and cannot learn and evolve only by updating them. In addition, taking into account several criteria induces an exorbitant number of rules to be injected into the system. It becomes difficult to translate medical knowledge or a support decision as a simple rule. Moreover, reasoning based on generic cases became classic and can even reduce the range of possible solutions. To remedy that, we propose an approach based on using a multi-criteria decision guided by a case-based reasoning (CBR) approach.
A Visibility Graph Averaging Aggregation Operator
Venue: arXiv cs.AI 2013
Year: 2013

The problem of aggregation is considerable importance in many disciplines. In this paper, a new type of operator called visibility graph averaging (VGA) aggregation operator is proposed. This proposed operator is based on the visibility graph which can convert a time series into a graph. The weights are obtained according to the importance of the data in the visibility graph. Finally, the VGA operator is used in the analysis of the TAIEX database to illustrate that it is practical and compared with the classic aggregation operators, it shows its advantage that it not only implements the aggregation of the data purely, but also conserves the time information, and meanwhile, the determination of the weights is more reasonable.
Towards a New Science of a Clinical Data Intelligence
Venue: arXiv cs.CY 2013
Year: 2013

In this paper we define Clinical Data Intelligence as the analysis of data generated in the clinical routine with the goal of improving patient care. We define a science of a Clinical Data Intelligence as a data analysis that permits the derivation of scientific, i.e., generalizable and reliable results. We argue that a science of a Clinical Data Intelligence is sensible in the context of a Big Data analysis, i.e., with data from many patients and with complete patient information. We discuss that Clinical Data Intelligence requires the joint efforts of knowledge engineering, information extraction (from textual and other unstructured data), and statistics and statistical machine learning. We describe some of our main results as conjectures and relate them to a recently funded research project involving two major German university hospitals.
Resolving and Exploiting the $k$-CFA Paradox
Venue: arXiv cs.PL 2013
Year: 2013

Low-level program analysis is a fundamental problem, taking the shape of "flow analysis" in functional languages and "points-to" analysis in imperative and object-oriented languages. Despite the similarities, the vocabulary and results in the two communities remain largely distinct, with limited cross-understanding. One of the few links is Shivers's $k$-CFA work, which has advanced the concept of "context-sensitive analysis" and is widely known in both communities. Recent results indicate that the relationship between the functional and object-oriented incarnations of $k$-CFA is not as well understood as thought. Van Horn and Mairson proved $k$-CFA for $k \geq 1$ to be EXPTIME-complete; hence, no polynomial-time algorithm can exist. Yet, there are several polynomial-time formulations of context-sensitive points-to analyses in object-oriented languages. Thus, it seems that functional $k$-CFA may actually be a profoundly different analysis from object-oriented $k$-CFA. We resolve this paradox by showing that the exact same specification of $k$-CFA is polynomial-time for object-oriented languages yet exponential- time for functional ones: objects and closures are subtly different, in a way that interacts crucially with context-sensitivity and complexity. This illumination leads to an immediate payoff: by projecting the object-oriented treatment of objects onto closures, we derive a polynomial-time hierarchy of context-sensitive CFAs for functional programs.
Applying Formal Methods to Networking: Theory, Techniques and Applications
Venue: arXiv cs.NI 2013
Year: 2013

Despite its great importance, modern network infrastructure is remarkable for the lack of rigor in its engineering. The Internet which began as a research experiment was never designed to handle the users and applications it hosts today. The lack of formalization of the Internet architecture meant limited abstractions and modularity, especially for the control and management planes, thus requiring for every new need a new protocol built from scratch. This led to an unwieldy ossified Internet architecture resistant to any attempts at formal verification, and an Internet culture where expediency and pragmatism are favored over formal correctness. Fortunately, recent work in the space of clean slate Internet design---especially, the software defined networking (SDN) paradigm---offers the Internet community another chance to develop the right kind of architecture and abstractions. This has also led to a great resurgence in interest of applying formal methods to specification, verification, and synthesis of networking protocols and applications. In this paper, we present a self-contained tutorial of the formidable amount of work that has been done in formal methods, and present a survey of its applications to networking.
Achievable Rate Region of the Bidirectional Buffer-Aided Relay Channel with Block Fading
Venue: arXiv cs.IT 2013
Year: 2013

The bidirectional relay channel, in which two users communicate with each other through a relay node, is a simple but fundamental and practical network architecture. In this paper, we consider the block fading bidirectional relay channel and propose efficient transmission strategies that exploit the block fading property of the channel. Thereby, we consider a decode-and-forward relay and assume that a direct link between the two users is not present. Our aim is to characterize the long-term achievable rate region and to develop protocols which achieve all points of the obtained rate region. Specifically, in the bidirectional relay channel, there exist six possible transmission modes: four point-to-point modes (user 1-to-relay, user 2-to-relay, relay-to-user 1, relay-to-user 2), a multiple-access mode (both users to the relay), and a broadcast mode (the relay to both users). Most existing protocols assume a fixed schedule for using a subset of the aforementioned transmission modes. Motivated by this limitation, we develop protocols which are not restricted to adhere to a predefined schedule for using the transmission modes. In fact, based on the instantaneous channel state information (CSI) of the involved links, the proposed protocol selects the optimal transmission mode in each time slot to maximize the long-term achievable rate region. Thereby, we consider two different types of transmit power constraints: 1) a joint long-term power constraint for all nodes, and 2) a fixed transmit power for each node. Furthermore, to enable the use of a non-predefined schedule for transmission mode selection, the relay has to be equipped with two buffers for storage of the information received from both users. As data buffering increases the end-to-end delay, we consider both delay-unconstrained and delay-constrained transmission in the paper.
Ranking Algorithms by Performance
Venue: arXiv cs.AI 2013
Year: 2013

A common way of doing algorithm selection is to train a machine learning model and predict the best algorithm from a portfolio to solve a particular problem. While this method has been highly successful, choosing only a single algorithm has inherent limitations -- if the choice was bad, no remedial action can be taken and parallelism cannot be exploited, to name but a few problems. In this paper, we investigate how to predict the ranking of the portfolio algorithms on a particular problem. This information can be used to choose the single best algorithm, but also to allocate resources to the algorithms according to their rank. We evaluate a range of approaches to predict the ranking of a set of algorithms on a problem. We furthermore introduce a framework for categorizing ranking predictions that allows to judge the expressiveness of the predictive output. Our experimental evaluation demonstrates on a range of data sets from the literature that it is beneficial to consider the relationship between algorithms when predicting rankings. We furthermore show that relatively naive approaches deliver rankings of good quality already.
The CAITLIN Auralization System: Hierarchical Leitmotif Design as a Clue to Program Comprehension
Venue: arXiv cs.HC 2013
Year: 2013

Early experiments have suggested that program auralization can convey information about program structure [8]. Languages like Pascal contain classes of construct that are similar in nature allowing hierarchical classification of their features. This taxonomy can be reflected in the design of musical signatures which are used within the CAITLIN program auralization system. Experiments using these hierarchical leitmotifs indicate whether or not their similarities can be put to good use in communicating information about program structure and state. (Note, at time of going to press experimental results could not be included. These will be presented at the conference and included later.)
Perception and Steering Control in Paired Bat Flight
Venue: arXiv cs.SY 2013
Year: 2013

Animals within groups need to coordinate their reactions to perceived environmental features and to each other in order to safely move from one point to another. This paper extends our previously published work on the flight patterns of Myotis velifer that have been observed in a habitat near Johnson City, Texas. Each evening, these bats emerge from a cave in sequences of small groups that typically contain no more than three or four individuals, and they thus provide ideal subjects for studying leader-follower behaviors. By analyzing the flight paths of a group of M. velifer, the data show that the flight behavior of a follower bat is influenced by the flight behavior of a leader bat in a way that is not well explained by existing pursuit laws, such as classical pursuit, constant bearing and motion camouflage. Thus we propose an alternative steering law based on virtual loom, a concept we introduce to capture the geometrical configuration of the leader-follower pair. It is shown that this law may be integrated with our previously proposed vision-enabled steering laws to synthesize trajectories, the statistics of which fit with those of the bats in our data set. The results suggest that bats use perceived information of both the environment and their neighbors for navigation.
Mathematical Foundations for Information Theory in Diffusion-Based Molecular Communications
Venue: arXiv cs.IT 2013
Year: 2013

Molecular communication emerges as a promising communication paradigm for nanotechnology. However, solid mathematical foundations for information-theoretic analysis of molecular communication have not yet been built. In particular, no one has ever proven that the channel coding theorem applies for molecular communication, and no relationship between information rate capacity (maximum mutual information) and code rate capacity (supremum achievable code rate) has been established. In this paper, we focus on a major subclass of molecular communication - the diffusion-based molecular communication. We provide solid mathematical foundations for information theory in diffusion-based molecular communication by creating a general diffusion-based molecular channel model in measure-theoretic form and prove its channel coding theorems. Various equivalence relationships between statistical and operational definitions of channel capacity are also established, including the most classic information rate capacity and code rate capacity. As byproducts, we have shown that the diffusion-based molecular channel is with "asymptotically decreasing input memory and anticipation" and "d-continuous". Other properties of diffusion-based molecular channel such as stationarity or ergodicity are also proven.