OpenRaiser/Intern-Atlas huggingface dataset:
Intersection types for unbind and rebind
Venue: arXiv cs.LO 2011
Year: 2011

We define a type system with intersection types for an extension of lambda-calculus with unbind and rebind operators. In this calculus, a term with free variables, representing open code, can be packed into an "unbound" term, and passed around as a value. In order to execute inside code, an unbound term should be explicitly rebound at the point where it is used. Unbinding and rebinding are hierarchical, that is, the term can contain arbitrarily nested unbound terms, whose inside code can only be executed after a sequence of rebinds has been applied. Correspondingly, types are decorated with levels, and a term has type decorated with k if it needs k rebinds in order to reduce to a value. With intersection types we model the fact that a term can be used differently in contexts providing different numbers of unbinds. In particular, top-level terms, that is, terms not requiring unbinds to reduce to values, should have a value type, that is, an intersection type where at least one element has level 0. With the proposed intersection type system we get soundness under the call-by-value strategy, an issue which was not resolved by previous type systems.
Untangling Typechecking of Intersections and Unions
Venue: arXiv cs.PL 2011
Year: 2011

Intersection and union types denote conjunctions and disjunctions of properties. Using bidirectional typechecking, intersection types are relatively straightforward, but union types present challenges. For union types, we can case-analyze a subterm of union type when it appears in evaluation position (replacing the subterm with a variable, and checking that term twice under appropriate assumptions). This technique preserves soundness in a call-by-value semantics. Sadly, there are so many choices of subterms that a direct implementation is not practical. But carefully transforming programs into let-normal form drastically reduces the number of choices. The key results are soundness and completeness: a typing derivation (in the system with too many subterm choices) exists for a program if and only if a derivation exists for the let-normalized program.
Thermal Analysis of Climate Regions using Remote Sensing and Grid Computing
Venue: arXiv cs.DC 2011
Year: 2011

The analysis of climate regions is very important for designers and architects, because the increase in density and built up spaces and reduction in open spaces and green lands induce the increase of heat, especially in an urban area, deteriorating the environment and causing health problems. This study analyzes the Land Surface Temperature (LST) differences in the region of Dobrogea, Romania, and compares with the land use and land cover types using TM and ETM+ data of 1989 and 2000. As the analysis is performed on large data sets, we used Grid Computing to implement a service for using on Computational Grids with a Web-based client interface, which will be greatly useful and convenient for those who are studying the ground thermal environment and heat island effects by using Landsat TM/ETM+ bands, and have typical workstations, with no special computing and storing resources for computationally intensive satellite image processing and no license for a commercial image processing tool. Based on the satellite imagery, the paper also addresses a Supervised Classification algorithm and the computation of two indices of great value in water resources management, Normalized Difference Vegetation Index (NDVI), respectively Land Surface Emissivity (LSE).
Interface Theories for (A)synchronously Communicating Modal I/O-Transition Systems
Venue: arXiv cs.SE 2011
Year: 2011

Interface specifications play an important role in component-based software development. An interface theory is a formal framework supporting composition, refinement and compatibility of interface specifications. We present different interface theories which use modal I/O-transition systems as their underlying domain for interface specifications: synchronous interface theories, which employ a synchronous communication schema, as well as a novel interface theory for asynchronous communication where components communicate via FIFO-buffers.
Fractional counting of citations in research evaluation: A cross- and interdisciplinary assessment of the Tsinghua University in Beijing
Venue: arXiv cs.DL 2011
Year: 2011

In the case of the scientometric evaluation of multi- or interdisciplinary units one risks to compare apples with oranges: each paper has to be assessed in comparison to an appropriate reference set. We suggest that the set of citing papers can be considered as the relevant representation of the field of impact. In order to normalize for differences in citation behavior among fields, citations can be fractionally counted proportionately to the length of the reference lists in the citing papers. This new method enables us to compare among units with different disciplinary affiliations at the paper level and also to assess the statistical significance of differences among sets. Twenty-seven departments of the Tsinghua University in Beijing are thus compared. Among them, the Department of Chinese Language and Linguistics is upgraded from the 19th to the second position in the ranking. The overall impact of 19 of the 27 departments is not significantly different at the 5% level when thus normalized for different citation potentials.
A Generalized Method for Integrating Rule-based Knowledge into Inductive Methods Through Virtual Sample Creation
Venue: arXiv cs.LG 2011
Year: 2011

Hybrid learning methods use theoretical knowledge of a domain and a set of classified examples to develop a method for classification. Methods that use domain knowledge have been shown to perform better than inductive learners. However, there is no general method to include domain knowledge into all inductive learning algorithms as all hybrid methods are highly specialized for a particular algorithm. We present an algorithm that will take domain knowledge in the form of propositional rules, generate artificial examples from the rules and also remove instances likely to be flawed. This enriched dataset then can be used by any learning algorithm. Experimental results of different scenarios are shown that demonstrate this method to be more effective than simple inductive learning.
Causal Dependence Tree Approximations of Joint Distributions for Multiple Random Processes
Venue: arXiv cs.IT 2011
Year: 2011

We investigate approximating joint distributions of random processes with causal dependence tree distributions. Such distributions are particularly useful in providing parsimonious representation when there exists causal dynamics among processes. By extending the results by Chow and Liu on dependence tree approximations, we show that the best causal dependence tree approximation is the one which maximizes the sum of directed informations on its edges, where best is defined in terms of minimizing the KL-divergence between the original and the approximate distribution. Moreover, we describe a low-complexity algorithm to efficiently pick this approximate distribution.
Analytical Evaluation of Fractional Frequency Reuse for OFDMA Cellular Networks
Venue: arXiv cs.IT 2011
Year: 2011

Fractional frequency reuse (FFR) is an interference management technique well-suited to OFDMA-based cellular networks wherein the cells are partitioned into spatial regions with different frequency reuse factors. To date, FFR techniques have been typically been evaluated through system-level simulations using a hexagonal grid for the base station locations. This paper instead focuses on analytically evaluating the two main types of FFR deployments - Strict FFR and Soft Frequency Reuse (SFR) - using a Poisson point process to model the base station locations. The results are compared with the standard grid model and an actual urban deployment. Under reasonable special cases for modern cellular networks, our results reduce to simple closed-form expressions, which provide insight into system design guidelines and the relative merits of Strict FFR, SFR, universal reuse, and fixed frequency reuse. We observe that FFR provides an increase in the sum-rate as well as the well-known benefit of improved coverage for cell-edge users. Finally, a SINR-proportional resource allocation strategy is proposed based on the analytical expressions, showing that Strict FFR provides greater overall network throughput at low traffic loads, while SFR better balances the requirements of interference reduction and resource efficiency when the traffic load is high.
Strict Authentication Watermarking with JPEG Compression (SAW-JPEG) for Medical Images
Venue: arXiv cs.CR 2011
Year: 2011

This paper proposes a strict authentication watermarking for medical images. In this scheme, we define region of interest (ROI) by taking the smallest rectangle around an image. The watermark is generated from hashing the area of interest. The embedding region is considered to be outside the region of interest as to preserve the area from distortion as a result from watermarking. The strict authentication watermarking is robust to some degree of JPEG compression (SAW-JPEG). JPEG compression will be reviewed. To embed a watermark in the spatial domain, we have to make sure that the embedded watermark will survive JPEG quantization process. The watermarking scheme, including data embedding, extracting and verifying procedure were presented. Experimental results showed that such a scheme could embed and extract the watermark at a high compression rate. The watermark is robust to a high compression rate up to 90.6%. The JPEG image quality threshold is 60 for the least significant bit embedding. The image quality threshold is increased to 61 for 2nd and 3rd LSB manipulations.
A Panorama on Multiscale Geometric Representations, Intertwining Spatial, Directional and Frequency Selectivity
Venue: arXiv cs.CV 2011
Year: 2011

The richness of natural images makes the quest for optimal representations in image processing and computer vision challenging. The latter observation has not prevented the design of image representations, which trade off between efficiency and complexity, while achieving accurate rendering of smooth regions as well as reproducing faithful contours and textures. The most recent ones, proposed in the past decade, share an hybrid heritage highlighting the multiscale and oriented nature of edges and patterns in images. This paper presents a panorama of the aforementioned literature on decompositions in multiscale, multi-orientation bases or dictionaries. They typically exhibit redundancy to improve sparsity in the transformed domain and sometimes its invariance with respect to simple geometric deformations (translation, rotation). Oriented multiscale dictionaries extend traditional wavelet processing and may offer rotation invariance. Highly redundant dictionaries require specific algorithms to simplify the search for an efficient (sparse) representation. We also discuss the extension of multiscale geometric decompositions to non-Euclidean domains such as the sphere or arbitrary meshed surfaces. The etymology of panorama suggests an overview, based on a choice of partially overlapping "pictures". We hope that this paper will contribute to the appreciation and apprehension of a stream of current research directions in image understanding.
Accurate Performance Analysis of Opportunistic Decode-and-Forward Relaying
Venue: arXiv cs.PF 2011
Year: 2011

In this paper, we investigate an opportunistic relaying scheme where the selected relay assists the source-destination (direct) communication. In our study, we consider a regenerative opportunistic relaying scheme in which the direct path can be considered unusable, and takes into account the effect of the possible erroneously detected and transmitted data at the best relay. We first derive statistics based on exact probability density function (PDF) of each hop. Then, the PDFs are used to determine accurate closed form expressions for end-to-end bit-error rate (BER) of binary phase-shift keying (BPSK) modulation. Furthermore, we evaluate the asymptotical performance analysis and the diversity order is deduced. Finally, we validate our analysis by showing that performance simulation results coincide with our analytical results over different network architectures.
RISC and CISC
Venue: arXiv cs.AR 2011
Year: 2011

Comparison of RISC & CISC in details, encompassing the addressing modes, evolution, definitions and characteristics. Pre - RISC design is also elaborated. Both the architectures are explained with the help of example. Analysis is made based on performance.
Ray-Based Reflectance Model for Diffraction
Venue: arXiv cs.GR 2011
Year: 2011

We present a novel method of simulating wave effects in graphics using ray--based renderers with a new function: the Wave BSDF (Bidirectional Scattering Distribution Function). Reflections from neighboring surface patches represented by local BSDFs are mutually independent. However, in many surfaces with wavelength-scale microstructures, interference and diffraction requires a joint analysis of reflected wavefronts from neighboring patches. We demonstrate a simple method to compute the BSDF for the entire microstructure, which can be used independently for each patch. This allows us to use traditional ray--based rendering pipelines to synthesize wave effects of light and sound. We exploit the Wigner Distribution Function (WDF) to create transmissive, reflective, and emissive BSDFs for various diffraction phenomena in a physically accurate way. In contrast to previous methods for computing interference, we circumvent the need to explicitly keep track of the phase of the wave by using BSDFs that include positive as well as negative coefficients. We describe and compare the theory in relation to well understood concepts in rendering and demonstrate a straightforward implementation. In conjunction with standard raytracers, such as PBRT, we demonstrate wave effects for a range of scenarios such as multi--bounce diffraction materials, holograms and reflection of high frequency surfaces.
Developing a New Approach for Arabic Morphological Analysis and Generation
Venue: arXiv cs.CL 2011
Year: 2011

Arabic morphological analysis is one of the essential stages in Arabic Natural Language Processing. In this paper we present an approach for Arabic morphological analysis. This approach is based on Arabic morphological automaton (AMAUT). The proposed technique uses a morphological database realized using XMODEL language. Arabic morphology represents a special type of morphological systems because it is based on the concept of scheme to represent Arabic words. We use this concept to develop the Arabic morphological automata. The proposed approach has development standardization aspect. It can be exploited by NLP applications such as syntactic and semantic analysis, information retrieval, machine translation and orthographical correction. The proposed approach is compared with Xerox Arabic Analyzer and Smrz Arabic Analyzer.
How Unique and Traceable are Usernames?
Venue: arXiv cs.CR 2011
Year: 2011

Suppose you find the same username on different online services, what is the probability that these usernames refer to the same physical person? This work addresses what appears to be a fairly simple question, which has many implications for anonymity and privacy on the Internet. One possible way of estimating this probability would be to look at the public information associated to the two accounts and try to match them. However, for most services, these information are chosen by the users themselves and are often very heterogeneous, possibly false and difficult to collect. Furthermore, several websites do not disclose any additional public information about users apart from their usernames (e.g., discus- sion forums or Blog comments), nonetheless, they might contain sensitive information about users. This paper explores the possibility of linking users profiles only by looking at their usernames. The intuition is that the probability that two usernames refer to the same physical person strongly depends on the "entropy" of the username string itself. Our experiments, based on crawls of real web services, show that a significant portion of the users' profiles can be linked using their usernames. To the best of our knowledge, this is the first time that usernames are considered as a source of information when profiling users on the Internet.
Using Planetlab to Implement Multicast at the Application Level
Venue: arXiv cs.DC 2011
Year: 2011

Application-layer multicast implements the multicast functionality at the application layer. The main goal of application-layer multicast is to construct and maintain efficient distribution structures between endhosts. In this paper we focus on the implementation of an application-layer multicast network using PlanetLab. We observe that the total time required to measure network latency over TCP is influenced dramatically by the TCP connection time. We argue that end-host distribution is not only influenced by the quality of network links but also by the time required to make connections between nodes. We provide several solutions to decrease the total end-host distribution time.
Dynamic Monopolies in Colored Tori
Venue: arXiv cs.SI 2011
Year: 2011

The {\em information diffusion} has been modeled as the spread of an information within a group through a process of social influence, where the diffusion is driven by the so called {\em influential network}. Such a process, which has been intensively studied under the name of {\em viral marketing}, has the goal to select an initial good set of individuals that will promote a new idea (or message) by spreading the "rumor" within the entire social network through the word-of-mouth. Several studies used the {\em linear threshold model} where the group is represented by a graph, nodes have two possible states (active, non-active), and the threshold triggering the adoption (activation) of a new idea to a node is given by the number of the active neighbors. The problem of detecting in a graph the presence of the minimal number of nodes that will be able to activate the entire network is called {\em target set selection} (TSS). In this paper we extend TSS by allowing nodes to have more than two colors. The multicolored version of the TSS can be described as follows: let $G$ be a torus where every node is assigned a color from a finite set of colors. At each local time step, each node can recolor itself, depending on the local configurations, with the color held by the majority of its neighbors. We study the initial distributions of colors leading the system to a monochromatic configuration of color $k$, focusing on the minimum number of initial $k$-colored nodes. We conclude the paper by providing the time complexity to achieve the monochromatic configuration.
Some More Functions That Are Not APN Infinitely Often. The Case of Kasami exponents
Venue: arXiv cs.IT 2011
Year: 2011

We prove a necessary condition for some polynomials of Kasami degree to be APN over F_{q^n} for large n.
Information-theoretic measures associated with rough set approximations
Venue: arXiv cs.AI 2011
Year: 2011

Although some information-theoretic measures of uncertainty or granularity have been proposed in rough set theory, these measures are only dependent on the underlying partition and the cardinality of the universe, independent of the lower and upper approximations. It seems somewhat unreasonable since the basic idea of rough set theory aims at describing vague concepts by the lower and upper approximations. In this paper, we thus define new information-theoretic entropy and co-entropy functions associated to the partition and the approximations to measure the uncertainty and granularity of an approximation space. After introducing the novel notions of entropy and co-entropy, we then examine their properties. In particular, we discuss the relationship of co-entropies between different universes. The theoretical development is accompanied by illustrative numerical examples.
High-Performance Neural Networks for Visual Object Classification
Venue: arXiv cs.AI 2011
Year: 2011

We present a fast, fully parameterizable GPU implementation of Convolutional Neural Network variants. Our feature extractors are neither carefully designed nor pre-wired, but rather learned in a supervised way. Our deep hierarchical architectures achieve the best published results on benchmarks for object classification (NORB, CIFAR10) and handwritten digit recognition (MNIST), with error rates of 2.53%, 19.51%, 0.35%, respectively. Deep nets trained by simple back-propagation perform better than more shallow ones. Learning is surprisingly rapid. NORB is completely trained within five epochs. Test error rates on MNIST drop to 2.42%, 0.97% and 0.48% after 1, 3 and 17 epochs, respectively.
A Primer on Strategic Games
Venue: arXiv cs.GT 2011
Year: 2011

This is a short introduction to the subject of strategic games. We focus on the concepts of best response, Nash equilibrium, strict and weak dominance, and mixed strategies, and study the relation between these concepts in the context of the iterated elimination of strategies. Also, we discuss some variants of the original definition of a strategic game. Finally, we introduce the basics of mechanism design and use pre-Bayesian games to explain it.
Information-Theoretic Viewpoints on Optimal Causal Coding-Decoding Problems
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we consider an interacting two-agent sequential decision-making problem consisting of a Markov source process, a causal encoder with feedback, and a causal decoder. Motivated by a desire to foster links between control and information theory, we augment the standard formulation by considering general alphabets and a cost function operating on current and previous symbols. Using dynamic programming, we provide a structural result whereby an optimal scheme exists that operates on appropriate sufficient statistics. We emphasize an example where the decoder alphabet lies in a space of beliefs on the source alphabet, and the additive cost function is a log likelihood ratio pertaining to sequential information gain. We also consider the inverse optimal control problem, where a fixed encoder/decoder pair satisfying statistical conditions is shown to be optimal for some cost function, using probabilistic matching. We provide examples of the applicability of this framework to communication with feedback, hidden Markov models and the nonlinear filter, decentralized control, brain-machine interfaces, and queuing theory.
Design of Finite-Length Irregular Protograph Codes with Low Error Floors over the Binary-Input AWGN Channel Using Cyclic Liftings
Venue: arXiv cs.IT 2011
Year: 2011

We propose a technique to design finite-length irregular low-density parity-check (LDPC) codes over the binary-input additive white Gaussian noise (AWGN) channel with good performance in both the waterfall and the error floor region. The design process starts from a protograph which embodies a desirable degree distribution. This protograph is then lifted cyclically to a certain block length of interest. The lift is designed carefully to satisfy a certain approximate cycle extrinsic message degree (ACE) spectrum. The target ACE spectrum is one with extremal properties, implying a good error floor performance for the designed code. The proposed construction results in quasi-cyclic codes which are attractive in practice due to simple encoder and decoder implementation. Simulation results are provided to demonstrate the effectiveness of the proposed construction in comparison with similar existing constructions.