OpenRaiser/Intern-Atlas huggingface dataset:
Distinct word length frequencies: distributions and symbol entropies
Venue: arXiv cs.CL 2012
Year: 2012

The distribution of frequency counts of distinct words by length in a language's vocabulary will be analyzed using two methods. The first, will look at the empirical distributions of several languages and derive a distribution that reasonably explains the number of distinct words as a function of length. We will be able to derive the frequency count, mean word length, and variance of word length based on the marginal probability of letters and spaces. The second, based on information theory, will demonstrate that the conditional entropies can also be used to estimate the frequency of distinct words of a given length in a language. In addition, it will be shown how these techniques can also be applied to estimate higher order entropies using vocabulary word length.
SHO-FA: Robust compressive sensing with order-optimal complexity, measurements, and bits
Venue: arXiv cs.IT 2012
Year: 2012

Suppose x is any exactly k-sparse vector in R^n. We present a class of sparse matrices A, and a corresponding algorithm that we call SHO-FA (for Short and Fast) that, with high probability over A, can reconstruct x from Ax. The SHO-FA algorithm is related to the Invertible Bloom Lookup Tables recently introduced by Goodrich et al., with two important distinctions - SHO-FA relies on linear measurements, and is robust to noise. The SHO-FA algorithm is the first to simultaneously have the following properties: (a) it requires only O(k) measurements, (b) the bit-precision of each measurement and each arithmetic operation is O (log(n) + P) (here 2^{-P} is the desired relative error in the reconstruction of x), (c) the decoding complexity is O(k) arithmetic operations and encoding complexity is O(n) arithmetic operations, and (d) if the reconstruction goal is simply to recover a single component of x instead of all of x, with significant probability over A this can be done in constant time. All constants above are independent of all problem parameters other than the desired success probability. For a wide range of parameters these properties are information-theoretically order-optimal. In addition, our SHO-FA algorithm works over fairly general ensembles of "sparse random matrices", is robust to random noise, and (random) approximate sparsity for a large range of k. In particular, suppose the measured vector equals A(x+z)+e, where z and e correspond respectively to the source tail and measurement noise. Under reasonable statistical assumptions on z and e our decoding algorithm reconstructs x with an estimation error of O(||z||_2 +||e||_2). The SHO-FA algorithm works with high probability over A, z, and e, and still requires only O(k) steps and O(k) measurements over O(log n)-bit numbers. This is in contrast to the worst-case z model, where it is known O(k log n/k) measurements are necessary.
Dichotomy for Holant* Problems with a Function on Domain Size 3
Venue: arXiv cs.CC 2012
Year: 2012

Holant problems are a general framework to study the algorithmic complexity of counting problems. Both counting constraint satisfaction problems and graph homomorphisms are special cases. All previous results of Holant problems are over the Boolean domain. In this paper, we give the first dichotomy theorem for Holant problems for domain size $>2$. We discover unexpected tractable families of counting problems, by giving new polynomial time algorithms. This paper also initiates holographic reductions in domains of size $>2$. This is our main algorithmic technique, and is used for both tractable families and hardness reductions. The dichotomy theorem is the following: For any complex-valued symmetric function ${\bf F}$ with arity 3 on domain size 3, we give an explicit criterion on ${\bf F}$, such that if ${\bf F}$ satisfies the criterion then the problem ${\rm Holant}^*({\bf F})$ is computable in polynomial time, otherwise ${\rm Holant}^*({\bf F})$ is #P-hard.
A Spectral Learning Approach to Range-Only SLAM
Venue: arXiv cs.LG 2012
Year: 2012

We present a novel spectral learning algorithm for simultaneous localization and mapping (SLAM) from range data with known correspondences. This algorithm is an instance of a general spectral system identification framework, from which it inherits several desirable properties, including statistical consistency and no local optima. Compared with popular batch optimization or multiple-hypothesis tracking (MHT) methods for range-only SLAM, our spectral approach offers guaranteed low computational requirements and good tracking performance. Compared with popular extended Kalman filter (EKF) or extended information filter (EIF) approaches, and many MHT ones, our approach does not need to linearize a transition or measurement model; such linearizations can cause severe errors in EKFs and EIFs, and to a lesser extent MHT, particularly for the highly non-Gaussian posteriors encountered in range-only SLAM. We provide a theoretical analysis of our method, including finite-sample error bounds. Finally, we demonstrate on a real-world robotic SLAM problem that our algorithm is not only theoretically justified, but works well in practice: in a comparison of multiple methods, the lowest errors come from a combination of our algorithm with batch optimization, but our method alone produces nearly as good a result at far lower computational cost.
Resource Allocation: Realizing Mean-Variability-Fairness Tradeoffs
Venue: arXiv cs.SY 2012
Year: 2012

Network Utility Maximization (NUM) provides a key conceptual framework to study reward allocation amongst a collection of users/entities across disciplines as diverse as economics, law and engineering. In network engineering, this framework has been particularly insightful towards understanding how Internet protocols allocate bandwidth, and motivated diverse research efforts on distributed mechanisms to maximize network utility while incorporating new relevant constraints, on energy, power, storage, stability, etc., e.g., for systems ranging from communication networks to the smart-grid. However when the available resources and/or users' utilities vary over time, reward allocations will tend to vary, which in turn may have a detrimental impact on the users' overall satisfaction or quality of experience. This paper introduces a generalization of NUM framework which explicitly incorporates the detrimental impact of temporal variability in a user's allocated rewards. It explicitly incorporates tradeoffs amongst the mean and variability in users' reward allocations, as well as fairness. We propose a simple online algorithm to realize these tradeoffs, which, under stationary ergodic assumptions, is shown to be asymptotically optimal, i.e., achieves a long term performance equal to that of an offline algorithm with knowledge of the future variability in the system. This substantially extends work on NUM to an interesting class of relevant problems where users/entities are sensitive to temporal variability in their service or allocated rewards.
The Cerny conjecture for automata respecting intervals of a directed graph
Venue: arXiv cs.FL 2012
Year: 2012

The Černý's conjecture states that for every synchronizing automaton with n states there exists a reset word of length not exceeding (n-11)^2. We prove this conjecture for a class of automata preserving certain properties of intervals of a directed graph. Our result unifies and generalizes some earlier results obtained by other authors.
Noise Filtering, Channel Modeling and Energy Utilization in Wireless Body Area Networks
Venue: arXiv cs.NI 2012
Year: 2012

Constant monitoring of patients without disturbing their daily activities can be achieved through mobile networks. Sensor nodes distributed in a home environment to provide home assistance gives concept of Wireless Wearable Body Area Networks. Gathering useful information and its transmission to the required destination may face several problems. In this paper we figure out different issues and discuss their possible solutions in order to obtain an optimized infrastructure for the care of elderly people. Different channel models along with their characteristics, noise filtering in different equalization techniques, energy consumption and effect of different impairments have been discussed in our paper. The novelty of this work is that we highlighted multiple issues along with their possible solutions that a BAN infrastructure is still facing.
Novel Grey Interval Weight Determining and Hybrid Grey Interval Relation Method in Multiple Attribute Decision-Making
Venue: arXiv cs.AI 2012
Year: 2012

This paper proposes a grey interval relation TOPSIS for the decision making in which all of the attribute weights and attribute values are given by the interval grey numbers. The feature of our method different from other grey relation decision-making is that all of the subjective and objective weights are obtained by interval grey number and that decisionmaking is performed based on the relative approach degree of grey TOPSIS, the relative approach degree of grey incidence and the relative membership degree of grey incidence using 2-dimensional Euclidean distance. The weighted Borda method is used for combining the results of three methods. An example shows the applicability of the proposed approach.
Hitting Sets Online and Unique-Max Coloring
Venue: arXiv cs.DS 2012
Year: 2012

We consider the problem of hitting sets online. The hypergraph (i.e., range-space consisting of points and ranges) is known in advance, and the ranges to be stabbed are input one-by-one in an online fashion. The online algorithm must stab each range upon arrival. An online algorithm may add points to the hitting set but may not remove already chosen points. The goal is to use the smallest number of points. The best known competitive ratio for hitting sets online by Alon et al. \cite{alon2009online} is $O(\log n \cdot \log m)$ for general hypergraphs, where $n$ and $m$ denote the number of points and the number of ranges, respectively. We consider hypergraphs in which the union of two intersecting ranges is also a range. Our main result for such hypergraphs is as follows. The competitive ratio of the online hitting set problem is at most the unique-max number and at least this number minus one.
A Review of Techniques to Mitigate Sybil Attacks
Venue: arXiv cs.CR 2012
Year: 2012

Any decentralised distributed network is particularly vulnerable to the Sybil attack wherein a malicious node masquerades as several different nodes, called Sybil nodes, simultaneously in an attempt to disrupt the proper functioning of the network. Such attacks may cause damage on a fairly large scale especially since they are difficult to detect and there has been no universally accepted scheme to counter them as yet. In this paper, we discuss the different kinds of Sybil attacks including those occurring in peer-to-peer reputation systems, self-organising networks and even social network systems. In addition, various methods that have been suggested over time to decrease or eliminate their risk completely are also analysed along with their modus operandi.
Camera identification by grouping images from database, based on shared noise patterns
Venue: arXiv cs.CV 2012
Year: 2012

Previous research showed that camera specific noise patterns, so-called PRNU-patterns, are extracted from images and related images could be found. In this particular research the focus is on grouping images from a database, based on a shared noise pattern as an identification method for cameras. Using the method as described in this article, groups of images, created using the same camera, could be linked from a large database of images. Using MATLAB programming, relevant image noise patterns are extracted from images much quicker than common methods by the use of faster noise extraction filters and improvements to reduce the calculation costs. Relating noise patterns, with a correlation above a certain threshold value, can quickly be matched. Hereby, from a database of images, groups of relating images could be linked and the method could be used to scan a large number of images for suspect noise patterns.
Strongly Complete Logics for Coalgebras
Venue: arXiv cs.LO 2012
Year: 2012

Coalgebras for a functor model different types of transition systems in a uniform way. This paper focuses on a uniform account of finitary logics for set-based coalgebras. In particular, a general construction of a logic from an arbitrary set-functor is given and proven to be strongly complete under additional assumptions. We proceed in three parts. Part I argues that sifted colimit preserving functors are those functors that preserve universal algebraic structure. Our main theorem here states that a functor preserves sifted colimits if and only if it has a finitary presentation by operations and equations. Moreover, the presentation of the category of algebras for the functor is obtained compositionally from the presentations of the underlying category and of the functor. Part II investigates algebras for a functor over ind-completions and extends the theorem of J{ó}nsson and Tarski on canonical extensions of Boolean algebras with operators to this setting. Part III shows, based on Part I, how to associate a finitary logic to any finite-sets preserving functor T. Based on Part II we prove the logic to be strongly complete under a reasonable condition on T.
Low Cost PC Based Real Time Data Logging System Using PCs Parallel Port For Slowly Varying Signals
Venue: arXiv cs.AR 2012
Year: 2012

A low cost PC based real time data logging system can be used in the laboratories for the measurement, monitoring and storage of the data for slowly varying signals in science and engineering stream. This can be designed and interfaced to the PCs Parallel Port, which is common to all desktop computers or Personal Computers (PCs). By the use of this data logging system one can monitor, measure and store data for slowly varying signals, which is hard to visualise the signal waveforms by ordinary CRO (Cathode Ray Oscilloscope) and DSO (Digital Storage Oscilloscope). The data so stored can be used for further study and analysis. It can be used for a wide range of applications to monitor and store data of temperature, humidity, light intensity, ECG signals etc. with proper signal conditioning circuitry.
E-banking and E-commerce in India and USA
Venue: arXiv cs.CY 2012
Year: 2012

Web based e-banking is becoming an important aspect of worldwide commerce. The United Nations predicts 17% of purchases by firms and individuals will be conducted online by 2006. The future of Web-based e-banking in developed areas appears bright but consumers and merchants in developing countries face in number of barriers to successful e-banking, including less reliable telecommunications infrastructure and power supplies, less access to online payment mechanisms, and relatively high costs for personal computers and Internet access. How should managers in charge of e-banking prepare for global implementation? What can they do reach consumers in developing countries? What factors influence the adoption of consumer-oriented e-banking in various countries? This research paper will give you the idea on the local conditions in India, the Hofstede's dimension of culture in India and USA, the Diffusion of Innovation theory and hence the hypotheses for the innovation characteristics of interest.
On Methods for the Formal Specification of Fault Tolerant Systems
Venue: arXiv cs.SE 2012
Year: 2012

This paper introduces different views for understanding problems and faults with the goal of defining a method for the formal specification of systems. The idea of Layered Fault Tolerant Specification (LFTS) is proposed to make the method extensible to fault tolerant systems. The principle is layering the specification in different levels, the first one for the normal behavior and the others for the abnormal. The abnormal behavior is described in terms of an Error Injector (EI), which represents a model of the erroneous interference coming from the environment. This structure has been inspired by the notion of idealized fault tolerant component but the combination of LFTS and EI using Rely/Guarantee reasoning to describe their interaction can be considered as a novel contribution. The progress toward this method and this way to organize fault tolerant specifications has been made experimenting on case studies and an example is presented.
Fast Subsequent Color Iris Matching in large Database
Venue: arXiv cs.GT 2012
Year: 2012

Databases play an important role in cyber world. It provides authenticity across the globe to the legitimate user. Biometrics is another important tool which recognizes humans using their physical statistics. Biometrics system requires speedy recognition that provides instant and accurate results. Biometric industry is looking for a new algorithm that interacts with biometric system reduces its recognition time while searching its record in large database. We propose a method which provides an appropriate solution for the aforementioned problem. Iris images database could be smart if iris image histogram ratio is used as its primary key. So, we have developed an algorithm that converts image histogram into eight byte code which will be used as primary key of a large database. Second part of this study explains how color iris image recognition can take place. For this a new and efficient algorithm is developed that segments the iris image and performs recognition in much less time. Our research proposes a fast and efficient algorithm that recognizes color irises from large database. We have already implemented this algorithm in Matlab. It provides real-time, high confidence recognition of a person's identity using mathematical analysis of the random patterns that are visible within the iris of an eye.
A Novel Process Mapping Strategy in Clustered Environments
Venue: arXiv cs.DC 2012
Year: 2012

Nowadays the number of available processing cores within computing nodes which are used in recent clustered environments, are growing up with a rapid rate. Despite this trend, the number of available network interfaces in such computing nodes has almost been remained unchanged. This issue can lead to high usage of network interface in many workloads, especially in heavy-communicating workloads. As a result, network interface may raise as a performance bottleneck and can drastically degrade the performance. The goal of this paper is to introduce a new process mapping strategy in multi-core clusters aimed at reducing network interface contention and improving inter-node communication performance of parallel applications. Performance evaluation of the new mapping algorithm in synthetic and real workloads indicates that the new strategy can achieve 5% to 90% performance improvement in heavy communicating workloads, compared to other well-known methods.
Effective Capacity of a Rayleigh Fading Channel in the Presence of Interference
Venue: arXiv cs.NI 2012
Year: 2012

In recent years the concept of the effective capacity that relates the physical layer characteristics of a wireless channel to the data link layer has gained a lot of attraction in wireless networking research community. The effective capacity is based on Gärtner-Ellis' large deviation theorem and it is used to provide the statistical QoS provisioning in the wireless networks. Effective capacity also helps in the analysis of the resource allocation or scheduling policies in various wireless systems such as Relay networks, multi-user systems and multi-carrier systems subject to statistical QoS requirements. The effective capacity in noise limited wireless network has already been investigated in the recent works. Considering the interference limited wireless channels, in this paper we propose an analytical approach based on Laplace's method for the effective capacity of uncorrelated Rayleigh fading channel in the presence of uncorrelated Rayleigh fading interference. The accuracy of the analytical model for the effective capacity is validated by numerical simulations. We also provide the evaluation of tail probability of the delay and maximum sustainable rate. The validation results reveal that the proposed mathematical approach to the effective capacity can open the path for further researches in statistical QoS provisioning in interference limited wireless networks.
New Symmetric and Asymmetric Quantum Codes
Venue: arXiv cs.IT 2012
Year: 2012

New infinite families of quantum symmetric and asymmetric codes are constructed. Several of these are MDS. The codes obtained are shown to have parameters which are better than previously known. A number of known codes are special cases of the codes given here.
The Sufficiency Principle for Decentralized Data Reduction
Venue: arXiv cs.IT 2012
Year: 2012

This paper develops the sufficiency principle suitable for data reduction in decentralized inference systems. Both parallel and tandem networks are studied and we focus on the cases where observations at decentralized nodes are conditionally dependent. For a parallel network, through the introduction of a hidden variable that induces conditional independence among the observations, the locally sufficient statistics, defined with respect to the hidden variable, are shown to be globally sufficient for the parameter of inference interest. For a tandem network, the notion of conditional sufficiency is introduced and the related theories and tools are developed. Finally, connections between the sufficiency principle and some distributed source coding problems are explored.
Google matrix of Twitter
Venue: arXiv cs.SI 2012
Year: 2012

We construct the Google matrix of the entire Twitter network, dated by July 2009, and analyze its spectrum and eigenstate properties including the PageRank and CheiRank vectors and 2DRanking of all nodes. Our studies show much stronger inter-connectivity between top PageRank nodes for the Twitter network compared to the networks of Wikipedia and British Universities studied previously. Our analysis allows to locate the top Twitter users which control the information flow on the network. We argue that this small fraction of the whole number of users, which can be viewed as the social network elite, plays the dominant role in the process of opinion formation on the network.
Visualising Virtual Communities: From Erdős to the Arts
Venue: arXiv cs.CY 2012
Year: 2012

Monitoring communities has become increasingly easy on the web as the number of visualisation tools and amount of data available about communities increase. It is possible to visualise connections on social and professional networks such as Facebook in the form of mathematical graphs. It is also possible to visualise connections between authors of papers. In particular, Microsoft Academic Search now has a large corpus of information on publications, together with author and citation information, that can be visualised in a number of ways. In mathematical circles, the concept of the "Erdős number" has been introduced, in honour of the Hungarian mathematician Paul Erdős, measuring the "collaborative distance" of a person away from Erdős through links by co-author. Similar metrics have been proposed in other fields, including acting. The possibility of exploring and visualising such links in arts fields is proposed in this paper.