OpenRaiser/Intern-Atlas huggingface dataset:
Polar Codes: Robustness of the Successive Cancellation Decoder with Respect to Quantization
Venue: arXiv cs.IT 2012
Year: 2012

Polar codes provably achieve the capacity of a wide array of channels under successive decoding. This assumes infinite precision arithmetic. Given the successive nature of the decoding algorithm, one might worry about the sensitivity of the performance to the precision of the computation. We show that even very coarsely quantized decoding algorithms lead to excellent performance. More concretely, we show that under successive decoding with an alphabet of cardinality only three, the decoder still has a threshold and this threshold is a sizable fraction of capacity. More generally, we show that if we are willing to transmit at a rate $δ$ below capacity, then we need only $c \log(1/δ)$ bits of precision, where $c$ is a universal constant.
Goldbach Circles and Balloons and Their Cross Correlation
Venue: arXiv cs.CR 2012
Year: 2012

Goldbach partitions can be used in creation of ellipses and circles on the number line. We extend this work and determine the count and other properties of concentric Goldbach circles for different values of n. The autocorrelation function of this sequence with respect to even and odd values suggests that it has excellent randomness properties. Cross correlation properties of ellipse and circle sequences are provided that indicate that these sequences have minimal dependencies and, therefore, they can be used in spread spectrum and other cryptographic applications.
DolNet: A Division Of Labour Based Distributed Object Oriented Software Process Model
Venue: arXiv cs.SE 2012
Year: 2012

Distributed Software Development today is in its childhood and not too widespread as a method of developing software in the global IT Industry. In this context, Petrinets are a mathematical model for describing distributed systems theoretically, whereas AttNets are one of their offshoots. But development of true distributed software is limited to network operating systems majorly. Software that runs on many machines with separate programs for each machine, are very few. This paper introduces and defines Distributed Object Oriented Software Engineering DOOSE as a new field in software engineering. The paper further gives a Distributed Object Oriented Software Process Model DOOSPM, called the DolNet, which describes how work may be done by a software development organization while working on Distributed Object Oriented DOO Projects.
On the Sensitivity of Shape Fitting Problems
Venue: arXiv cs.CG 2012
Year: 2012

In this article, we study shape fitting problems, $ε$-coresets, and total sensitivity. We focus on the $(j,k)$-projective clustering problems, including $k$-median/$k$-means, $k$-line clustering, $j$-subspace approximation, and the integer $(j,k)$-projective clustering problem. We derive upper bounds of total sensitivities for these problems, and obtain $ε$-coresets using these upper bounds. Using a dimension-reduction type argument, we are able to greatly simplify earlier results on total sensitivity for the $k$-median/$k$-means clustering problems, and obtain positively-weighted $ε$-coresets for several variants of the $(j,k)$-projective clustering problem. We also extend an earlier result on $ε$-coresets for the integer $(j,k)$-projective clustering problem in fixed dimension to the case of high dimension.
Matroidal structure of rough sets based on serial and transitive relations
Venue: arXiv cs.AI 2012
Year: 2012

The theory of rough sets is concerned with the lower and upper approximations of objects through a binary relation on a universe. It has been applied to machine learning, knowledge discovery and data mining. The theory of matroids is a generalization of linear independence in vector spaces. It has been used in combinatorial optimization and algorithm design. In order to take advantages of both rough sets and matroids, in this paper we propose a matroidal structure of rough sets based on a serial and transitive relation on a universe. We define the family of all minimal neighborhoods of a relation on a universe, and prove it satisfy the circuit axioms of matroids when the relation is serial and transitive. In order to further study this matroidal structure, we investigate the inverse of this construction: inducing a relation by a matroid. The relationships between the upper approximation operators of rough sets based on relations and the closure operators of matroids in the above two constructions are studied. Moreover, we investigate the connections between the above two constructions.
Efficient and Low-Cost RFID Authentication Schemes
Venue: arXiv cs.CR 2012
Year: 2012

Security in passive resource-constrained Radio Frequency Identification (RFID) tags is of much interest nowadays. Resistance against illegal tracking, cloning, timing, and replay attacks are necessary for a secure RFID authentication scheme. Reader authentication is also necessary to thwart any illegal attempt to read the tags. With an objective to design a secure and low-cost RFID authentication protocol, Gene Tsudik proposed a timestamp-based protocol using symmetric keys, named YA-TRAP*. Although YA-TRAP* achieves its target security properties, it is susceptible to timing attacks, where the timestamp to be sent by the reader to the tag can be freely selected by an adversary. Moreover, in YA-TRAP*, reader authentication is not provided, and a tag can become inoperative after exceeding its pre-stored threshold timestamp value. In this paper, we propose two mutual RFID authentication protocols that aim to improve YA-TRAP* by preventing timing attack, and by providing reader authentication. Also, a tag is allowed to refresh its pre-stored threshold value in our protocols, so that it does not become inoperative after exceeding the threshold. Our protocols also achieve other security properties like forward security, resistance against cloning, replay, and tracking attacks. Moreover, the computation and communication costs are kept as low as possible for the tags. It is important to keep the communication cost as low as possible when many tags are authenticated in batch-mode. By introducing aggregate function for the reader-to-server communication, the communication cost is reduced. We also discuss different possible applications of our protocols. Our protocols thus capture more security properties and more efficiency than YA-TRAP*. Finally, we show that our protocols can be implemented using the current standard low-cost RFID infrastructures.
A Logic for Correlating Temporal Properties across Program Transformations
Venue: arXiv cs.LO 2012
Year: 2012

Program transformations are widely used in synthesis, optimization, and maintenance of software. Correctness of program transformations depends on preservation of some important properties of the input program. By regarding programs as Kripke structures, many interesting properties of programs can be expressed in temporal logics. In temporal logic, a formula is interpreted on a single program. However, to prove correctness of transformations, we encounter formulae which contain some subformulae interpreted on the input program and some on the transformed program. An example where such a situation arises is verification of optimizing program transformations applied by compilers. In this paper, we present a logic called Temporal Transformation Logic (TTL) to reason about such formulae. We consider different types of primitive transformations and present TTL inference rules for them. Our definitions of program transformations and temporal logic operators are novel in their use of the boolean matrix algebra. This results in specifications that are succinct and constructive. Further, we use the boolean matrix algebra in a uniform manner to prove soundness of the TTL inference rules.
Information requirements for enterprise systems
Venue: arXiv cs.SE 2012
Year: 2012

In this paper, we discuss an approach to system requirements engineering, which is based on using models of the responsibilities assigned to agents in a multi-agency system of systems. The responsibility models serve as a basis for identifying the stakeholders that should be considered in establishing the requirements and provide a basis for a structured approach, described here, for information requirements elicitation. We illustrate this approach using a case study drawn from civil emergency management.
Reliability of swarming algorithms for mobile sensor network applications
Venue: arXiv cs.MA 2012
Year: 2012

There are many well-studied swarming algorithms which are often suited to very specific purposes. As mobile sensor networks become increasingly complex, and are comprised of more and more agents, it makes sense to consider swarming algorithms for movement control. We introduce a natural way to measure the reliability of various swarming algorithms so a balance can be struck between algorithmic complexity and sampling accuracy.
On some many-valued abstract logics and their Epsilon-T-style extensions
Venue: arXiv cs.LO 2012
Year: 2012

Logical systems with classical negation and means for sentential or propositional self-reference involve, in some way, paradoxical statements such as the liar. However, the paradox disappears if one replaces classical by an appropriate non-classical negation such as a paraconsistent one (no paradox arises if the liar is both true and false). We consider a non-Fregean logic which is a revised and extended version (Lewitzka 2012) of Epsilon-T-Logic originally introduced by (Straeter 1992) as a logic with a total truth predicate and propositional quantifiers. Self-reference is achieved by means of equations between formulas which are interpreted over a model-theoretic universe of propositions. Paradoxical statements, such as the liar, can be asserted only by unsatisfiable equations and do not correlate with propositions. In this paper, we generalize Epsilon-T-Logic to a four-valued logic related to Dunn/Belnap logic B_4. We also define three-valued versions related to Kleene's logic K_3 and Priest's Logic of Paradox P_3, respectively. In this many-valued setting, models may contain liars and other "paradoxical" propositions which are ruled out by the more restrictive classical semantics. We introduce these many-valued non-Fregean logics as extensions of abstract parameter logics such that parameter logic and extension are of the same logical type. For this purpose, we define and study abstract logics of type B_4, K_3 and P_3. Using semantic methods we show compactness of the consequence relation of abstract logics of type B_4, give a representation as minimally generated logics and establish a connection to the approach of (Font 1997). Finally, we present a complete sequent calculus for the Epsilon-T-style extension of classical abstract logics simplifying constructions originally developed by (Straeter 1992, Zeitz 2000, Lewitzka 1998).
Study of a new link layer security scheme in a wireless sensor network
Venue: arXiv cs.NI 2012
Year: 2012

Security of wireless sensor network (WSN) is always considered a critical issue and has a number of considerations that separate them from traditional wireless sensor network. First, sensor devices are typically vulnerable to physical compromise. Second, they have significant power and processing constraints. Third, the most critical security issue is protecting the aggregate output of the system, even if individual nodes may be compromised. While a variety of security techniques are being developed and lots of researches are going on security fields. In this paper we have proposed a new technique to provide data authentication and privacy in faster, scalable and cost effective way.
Predecessor search with distance-sensitive query time
Venue: arXiv cs.DS 2012
Year: 2012

A predecessor (successor) search finds the largest element $x^-$ smaller than the input string $x$ (the smallest element $x^+$ larger than or equal to $x$, respectively) out of a given set $S$; in this paper, we consider the static case (i.e., $S$ is fixed and does not change over time) and assume that the $n$ elements of $S$ are available for inspection. We present a number of algorithms that, with a small additional index (usually of O(n log w) bits, where $w$ is the string length), can answer predecessor/successor queries quickly and with time bounds that depend on different kinds of distance, improving significantly several results that appeared in the recent literature. Intuitively, our first result has a running time that depends on the distance between $x$ and $x^\pm$: it is especially efficient when the input $x$ is either very close to or very far from $x^-$ or $x^+$; our second result depends on some global notion of distance in the set $S$, and is fast when the elements of $S$ are more or less equally spaced in the universe; finally, for our third result we rely on a finger (i.e., an element of $S$) to improve upon the first one; its running time depends on the distance between the input and the finger.
On Capacity of Large-Scale MIMO Multiple Access Channels with Distributed Sets of Correlated Antennas
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, a deterministic equivalent of ergodic sum rate and an algorithm for evaluating the capacity-achieving input covariance matrices for the uplink large-scale multiple-input multiple-output (MIMO) antenna channels are proposed. We consider a large-scale MIMO system consisting of multiple users and one base station with several distributed antenna sets. Each link between a user and an antenna set forms a two-sided spatially correlated MIMO channel with line-of-sight (LOS) components. Our derivations are based on novel techniques from large dimensional random matrix theory (RMT) under the assumption that the numbers of antennas at the terminals approach to infinity with a fixed ratio. The deterministic equivalent results (the deterministic equivalent of ergodic sum rate and the capacity-achieving input covariance matrices) are easy to compute and shown to be accurate for realistic system dimensions. In addition, they are shown to be invariant to several types of fading distribution.
Defect Management Strategies in Software Development
Venue: arXiv cs.SE 2012
Year: 2012

Software is a unique entity that has laid a strong impact on all other fields either related or not related to software. These include medical, scientific, business, educational, defence, transport, telecommunication to name a few. State-of-the-art professional domain activities demands the development of high quality software. High quality software attributes to a defect-free product, which is competent of producing predictable results and remains deliverable within time and cost constraints. It should be manageable with minimum interferences. It should also be maintainable, dependable, understandable and efficient. Thus, a systematic approach towards high quality software development is required due to increased competitiveness in today's business world, technological advances, hardware complexity and frequently changing business requirements.
The Feasibility of Scalable Video Streaming over Femtocell Networks
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider femtocell CR networks, where femto base stations (FBS) are deployed to greatly improve network coverage and capacity. We investigate the problem of generic data multicast in femtocell networks. We reformulate the resulting MINLP problem into a simpler form, and derive upper and lower performance bounds. Then we consider three typical connection scenarios in the femtocell network, and develop optimal and near-optimal algorithms for the three scenarios. Second, we tackle the problem of streaming scalable videos in femtocell CR networks. A framework is developed to captures the key design issues and trade-offs with a stochastic programming problem formulation. In the case of a single FBS, we develop an optimum-achieving distributed algorithm, which is shown also optimal for the case of multiple non-interfering FBS's. In the case of interfering FBS's, we develop a greedy algorithm that can compute near-opitmal solutions, and prove a closed-form lower bound on its performance.
Fast Point-Feature Label Placement for Dynamic Visualizations (2007)
Venue: arXiv cs.DS 2012
Year: 2012

This paper describes a fast approach to automatic point label de-confliction on interactive maps. The general Map Labeling problem is NP-hard and has been the subject of much study for decades. Computerized maps have introduced interactive zooming and panning, which has intensified the problem. Providing dynamic labels for such maps typically requires a time-consuming pre-processing phase. In the realm of visual analytics, however, the labeling of interactive maps is further complicated by the use of massive datasets laid out in arbitrary configurations, thus rendering reliance on a pre-processing phase untenable. This paper offers a method for labeling point-features on dynamic maps in real time without pre-processing. The algorithm presented is efficient, scalable, and exceptionally fast; it can label interactive charts and diagrams at speeds of multiple frames per second on maps with tens of thousands of nodes. To accomplish this, the algorithm employs a novel geometric de-confliction approach, the 'trellis strategy,' along with a unique label candidate cost analysis to determine the 'least expensive' label configuration. The speed and scalability of this approach make it well-suited for visual analytic applications.
Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs
Venue: arXiv cs.DS 2012
Year: 2012

The maximum clique problem is a well known NP-Hard problem with applications in data mining, network analysis, informatics, and many other areas. Although there exist several algorithms with acceptable runtimes for certain classes of graphs, many of them are infeasible for massive graphs. We present a new exact algorithm that employs novel pruning techniques to very quickly find maximum cliques in large sparse graphs. Extensive experiments on several types of synthetic and real-world graphs show that our new algorithm is up to several orders of magnitude faster than existing algorithms for most instances. We also present a heuristic variant that runs orders of magnitude faster than the exact algorithm, while providing optimal or near-optimal solutions.
PlaceRaider: Virtual Theft in Physical Spaces with Smartphones
Venue: arXiv cs.CR 2012
Year: 2012

As smartphones become more pervasive, they are increasingly targeted by malware. At the same time, each new generation of smartphone features increasingly powerful onboard sensor suites. A new strain of sensor malware has been developing that leverages these sensors to steal information from the physical environment (e.g., researchers have recently demonstrated how malware can listen for spoken credit card numbers through the microphone, or feel keystroke vibrations using the accelerometer). Yet the possibilities of what malware can see through a camera have been understudied. This paper introduces a novel visual malware called PlaceRaider, which allows remote attackers to engage in remote reconnaissance and what we call virtual theft. Through completely opportunistic use of the camera on the phone and other sensors, PlaceRaider constructs rich, three dimensional models of indoor environments. Remote burglars can thus download the physical space, study the environment carefully, and steal virtual objects from the environment (such as financial documents, information on computer monitors, and personally identifiable information). Through two human subject studies we demonstrate the effectiveness of using mobile devices as powerful surveillance and virtual theft platforms, and we suggest several possible defenses against visual malware.
A New Middle Path Approach For Alignements In Blast
Venue: arXiv cs.DS 2012
Year: 2012

This paper deals with a new middle path approach developed for reducing alignment calculations in BLAST algorithm. This is a new step which is introduced in BLAST algorithm in between the ungapped and gapped alignments. This step of middle path approach between the ungapped and gapped alignments reduces the number of sequences going for gapped alignment. This results in the improvement in speed for alignment up to 30 percent.
Natural Language Processing - A Survey
Venue: arXiv cs.CL 2012
Year: 2012

The utility and power of Natural Language Processing (NLP) seems destined to change our technological society in profound and fundamental ways. However there are, to date, few accessible descriptions of the science of NLP that have been written for a popular audience, or even for an audience of intelligent, but uninitiated scientists. This paper aims to provide just such an overview. In short, the objective of this article is to describe the purpose, procedures and practical applications of NLP in a clear, balanced, and readable way. We will examine the most recent literature describing the methods and processes of NLP, analyze some of the challenges that researchers are faced with, and briefly survey some of the current and future applications of this science to IT research in general.
SEGNET: Secure Geo-Sensor Network Model
Venue: arXiv cs.NI 2012
Year: 2012

Wireless Geo-Sensor Networks (GEONET) are suitable for critical applications in hostile environments due to its flexibility in deployment. But low power geo-sensor nodes are easily compromised by security threats like battery exhaustion attack which may give rise to unavoidable circumstances. In this type of attack, intruder forcefully resists legitimate sensor nodes from going into low-power sleep state. So that compromised sensor node's battery power is drained out and it stops working. Due to the limited capability of sensor nodes, it is very difficult to prevent a sensor node from this type of attack which apparently appears as innocent interaction. In this paper, a framework of secure GEONET model (SEGNET) is proposed, based on dynamic load distribution mechanism for heterogeneous environment. It considers hybrid detection approach using three modules for anomaly detection, intrusion confirmation and decision making to reduce the probability of false detection, compared to other existing approaches.
An Efficient Algorithm for Mining Multilevel Association Rule Based on Pincer Search
Venue: arXiv cs.DB 2012
Year: 2012

Discovering frequent itemset is a key difficulty in significant data mining applications, such as the discovery of association rules, strong rules, episodes, and minimal keys. The problem of developing models and algorithms for multilevel association mining poses for new challenges for mathematics and computer science. In this paper, we present a model of mining multilevel association rules which satisfies the different minimum support at each level, we have employed princer search concepts, multilevel taxonomy and different minimum supports to find multilevel association rules in a given transaction data set. This search is used only for maintaining and updating a new data structure. It is used to prune early candidates that would normally encounter in the top-down search. A main characteristic of the algorithms is that it does not require explicit examination of every frequent itemsets, an example is also given to demonstrate and support that the proposed mining algorithm can derive the multiple-level association rules under different supports in a simple and effective manner