OpenRaiser/Intern-Atlas huggingface dataset:
An n log n Alogrithm for Deterministic Kripke Structure Minimization
Venue: arXiv cs.DS 2012
Year: 2012

We introduce an algorithm for the minimization of deterministic Kripke structures with O(kn log2 n) time complexity. We prove the correctness and complexity properties of this algorithm.
Computation Environments, An Interactive Semantics for Turing Machines (which P is not equal to NP considering it)
Venue: arXiv cs.CC 2012
Year: 2012

To scrutinize notions of computation and time complexity, we introduce and formally define an interactive model for computation that we call it the \emph{computation environment}. A computation environment consists of two main parts: i) a universal processor and ii) a computist who uses the computability power of the universal processor to perform effective procedures. The notion of computation finds it meaning, for the computist, through his \underline{interaction} with the universal processor. We are interested in those computation environments which can be considered as alternative for the real computation environment that the human being is its computist. These computation environments must have two properties: 1- being physically plausible, and 2- being enough powerful. Based on Copeland' criteria for effective procedures, we define what a \emph{physically plausible} computation environment is. We construct two \emph{physically plausible} and \emph{enough powerful} computation environments: 1- the Turing computation environment, denoted by $E_T$, and 2- a persistently evolutionary computation environment, denoted by $E_e$, which persistently evolve in the course of executing the computations. We prove that the equality of complexity classes $\mathrm{P}$ and $\mathrm{NP}$ in the computation environment $E_e$ conflicts with the \underline{free will} of the computist. We provide an axiomatic system $\mathcal{T}$ for Turing computability and prove that ignoring just one of the axiom of $\mathcal{T}$, it would not be possible to derive $\mathrm{P=NP}$ from the rest of axioms. We prove that the computist who lives inside the environment $E_T$, can never be confident that whether he lives in a static environment or a persistently evolutionary one.
Optimal Strategies for Communication and Remote Estimation with an Energy Harvesting Sensor
Venue: arXiv cs.SY 2012
Year: 2012

We consider a remote estimation problem with an energy harvesting sensor and a remote estimator. The sensor observes the state of a discrete-time source which may be a finite state Markov chain or a multi-dimensional linear Gaussian system. It harvests energy from its environment (say, for example, through a solar cell) and uses this energy for the purpose of communicating with the estimator. Due to the randomness of energy available for communication, the sensor may not be able to communicate all the time. The sensor may also want to save its energy for future communications. The estimator relies on messages communicated by the sensor to produce real-time estimates of the source state. We consider the problem of finding a communication scheduling strategy for the sensor and an estimation strategy for the estimator that jointly minimize an expected sum of communication and distortion costs over a finite time horizon. Our goal of joint optimization leads to a decentralized decision-making problem. By viewing the problem from the estimator's perspective, we obtain a dynamic programming characterization for the decentralized decision-making problem that involves optimization over functions. Under some symmetry assumptions on the source statistics and the distortion metric, we show that an optimal communication strategy is described by easily computable thresholds and that the optimal estimate is a simple function of the most recently received sensor observation.
Leader Election for Anonymous Asynchronous Agents in Arbitrary Networks
Venue: arXiv cs.DC 2012
Year: 2012

We study the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph and share it with other agents to accomplish leader election. This can be done using meetings of agents, which is difficult because of their asynchronous nature: an adversary has total control over the speed of agents. When can a leader be elected in this adversarial scenario and how to do it? We give a complete answer to this question by characterizing all initial configurations for which leader election is possible and by constructing an algorithm that accomplishes leader election for all configurations for which this can be done.
Generalized sequential tree-reweighted message passing
Venue: arXiv cs.CV 2012
Year: 2012

This paper addresses the problem of approximate MAP-MRF inference in general graphical models. Following [36], we consider a family of linear programming relaxations of the problem where each relaxation is specified by a set of nested pairs of factors for which the marginalization constraint needs to be enforced. We develop a generalization of the TRW-S algorithm [9] for this problem, where we use a decomposition into junction chains, monotonic w.r.t. some ordering on the nodes. This generalizes the monotonic chains in [9] in a natural way. We also show how to deal with nested factors in an efficient way. Experiments show an improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on a number of computer vision and natural language processing problems.
Effective Listings of Function Stop words for Twitter
Venue: arXiv cs.IR 2012
Year: 2012

Many words in documents recur very frequently but are essentially meaningless as they are used to join words together in a sentence. It is commonly understood that stop words do not contribute to the context or content of textual documents. Due to their high frequency of occurrence, their presence in text mining presents an obstacle to the understanding of the content in the documents. To eliminate the bias effects, most text mining software or approaches make use of stop words list to identify and remove those words. However, the development of such top words list is difficult and inconsistent between textual sources. This problem is further aggravated by sources such as Twitter which are highly repetitive or similar in nature. In this paper, we will be examining the original work using term frequency, inverse document frequency and term adjacency for developing a stop words list for the Twitter data source. We propose a new technique using combinatorial values as an alternative measure to effectively list out stop words.
Algebraic symmetries of generic $(m+1)$ dimensional periodic Costas arrays
Venue: arXiv cs.IT 2012
Year: 2012

In this work we present two generators for the group of symmetries of the generic $(m+1)$ dimensional periodic Costas arrays over elementary abelian $(\mathbb{Z}_p)^m$ groups: one that is defined by multiplication on $m$ dimensions and the other by shear (addition) on $m$ dimensions. Through exhaustive search we observe that these two generators characterize the group of symmetries for the examples we were able to compute. Following the results, we conjecture that these generators characterize the group of symmetries of the generic $(m+1)$ dimensional periodic Costas arrays over elementary abelian $(\mathbb{Z}_p)^m$ groups.
Designing the Mode solving of the photonic crystal fiber via BPM and Exploring the Single-Mode Properties
Venue: arXiv cs.OH 2012
Year: 2012

Microstructured optical fibers (MOFs) are one of the most exciting recent developments in fiber optics. A MOF usually consists of a hexagonal arrangement of air holes running down the length of a silica fiber surrounding a central core of solid silica or, in some cases air. MOFs can exhibit a number of unique properties, including zero dispersion at visible wavelengths and low or high effective nonlinearity [3]-[17], By varying the size of the holes and their number and position, one can also design MOFs with carefully controlled dispersive and modal properties. In this paper, we analyze and modeling the behavior of the photonic crystal fiber (PCF) by using in the first step a propagator method based on the BPM method. With our BPM software, the electric field contour of the fundamental mode of PCF was demonstrated. We also used it to see the variation of the effective index; an effective index model confirms that such a fiber can be single mode for any wavelength. It would make a study of photonic crystal fibers, and a study of the numerical simulation methods allow the simulation of optical properties and has modeled the propagation of light in this fiber type. After that we use the V-parameter because it offers a simple way to design a photonic crystal fiber (PCF), by basing in a recent formulation of this parameter of a PCF, we provide numerically based empirical expression for this quantity only dependent on the two structural parameters, the air hole diameter and the hole-to-hole center spacing.
Modelling Chinese Smart Grid: A Stochastic Model Checking Case Study
Venue: arXiv cs.NI 2012
Year: 2012

Cyber-physical systems integrate information and communication technology functions to the physical elements of a system for monitoring and controlling purposes. The conversion of traditional power grid into a smart grid, a fundamental example of a cyber-physical system, raises a number of issues that require novel methods and applications. In this context, an important issue is the verification of certain quantitative properties of the system. In this technical report, we consider a specific Chinese Smart Grid implementation and try to address the verification problem for certain quantitative properties including performance and battery consumption. We employ stochastic model checking approach and present our modelling and analysis study using PRISM model checker.
Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets
Venue: arXiv cs.DB 2012
Year: 2012

With the advent of reliable positioning technologies and prevalence of location-based services, it is now feasible to accurately study the propagation of items such as infectious viruses, sensitive information pieces, and malwares through a population of moving objects, e.g., individuals, mobile devices, and vehicles. In such application scenarios, an item passes between two objects when the objects are sufficiently close (i.e., when they are, so-called, in contact), and hence once an item is initiated, it can penetrate the object population through the evolving network of contacts among objects, termed contact network. In this paper, for the first time we define and study reachability queries in large (i.e., disk-resident) contact datasets which record the movement of a (potentially large) set of objects moving in a spatial environment over an extended time period. A reachability query verifies whether two objects are "reachable" through the evolving contact network represented by such contact datasets. We propose two contact-dataset indexes that enable efficient evaluation of such queries despite the potentially humongous size of the contact datasets. With the first index, termed ReachGrid, at the query time only a small necessary portion of the contact network which is required for reachability evaluation is constructed and traversed. With the second approach, termed ReachGraph, we precompute reachability at different scales and leverage these precalculations at the query time for efficient query processing. We optimize the placement of both indexes on disk to enable efficient index traversal during query processing. We study the pros and cons of our proposed approaches by performing extensive experiments with both real and synthetic data. Based on our experimental results, our proposed approaches outperform existing reachability query processing techniques in contact n...[truncated].
Challenging the Long Tail Recommendation
Venue: arXiv cs.DB 2012
Year: 2012

The success of "infinite-inventory" retailers such as Amazon.com and Netflix has been largely attributed to a "long tail" phenomenon. Although the majority of their inventory is not in high demand, these niche products, unavailable at limited-inventory competitors, generate a significant fraction of total revenue in aggregate. In addition, tail product availability can boost head sales by offering consumers the convenience of "one-stop shopping" for both their mainstream and niche tastes. However, most of existing recommender systems, especially collaborative filter based methods, can not recommend tail products due to the data sparsity issue. It has been widely acknowledged that to recommend popular products is easier yet more trivial while to recommend long tail products adds more novelty yet it is also a more challenging task. In this paper, we propose a novel suite of graph-based algorithms for the long tail recommendation. We first represent user-item information with undirected edge-weighted graph and investigate the theoretical foundation of applying Hitting Time algorithm for long tail item recommendation. To improve recommendation diversity and accuracy, we extend Hitting Time and propose efficient Absorbing Time algorithm to help users find their favorite long tail items. Finally, we refine the Absorbing Time algorithm and propose two entropy-biased Absorbing Cost algorithms to distinguish the variation on different user-item rating pairs, which further enhances the effectiveness of long tail recommendation. Empirical experiments on two real life datasets show that our proposed algorithms are effective to recommend long tail items and outperform state-of-the-art recommendation techniques.
Fingerprint Gender Classification using Wavelet Transform and Singular Value Decomposition
Venue: arXiv cs.CV 2012
Year: 2012

A novel method of gender Classification from fingerprint is proposed based on discrete wavelet transform (DWT) and singular value decomposition (SVD). The classification is achieved by extracting the energy computed from all the sub-bands of DWT combined with the spatial features of non-zero singular values obtained from the SVD of fingerprint images. K nearest neighbor (KNN) used as a classifier. This method is experimented with the internal database of 3570 fingerprints finger prints in which 1980 were male fingerprints and 1590 were female fingerprints. Finger-wise gender classification is achieved which is 94.32% for the left hand little fingers of female persons and 95.46% for the left hand index finger of male persons. Gender classification for any finger of male persons tested is attained as 91.67% and 84.69% for female persons respectively. Overall classification rate is 88.28% has been achieved.
Lyndon Words and Short Superstrings
Venue: arXiv cs.DS 2012
Year: 2012

In the Shortest-Superstring problem, we are given a set of strings S and want to find a string that contains all strings in S as substrings and has minimum length. This is a classical problem in approximation and the best known approximation factor is 2 1/2, given by Sweedyk in 1999. Since then no improvement has been made, howerever two other approaches yielding a 2 1/2-approximation algorithms have been proposed by Kaplan et al. and recently by Paluch et al., both based on a reduction to maximum asymmetric TSP path (Max-ATSP-Path) and structural results of Breslauer et al. In this paper we give an algorithm that achieves an approximation ratio of 2 11/23, breaking through the long-standing bound of 2 1/2. We use the standard reduction of Shortest-Superstring to Max-ATSP-Path. The new, somewhat surprising, algorithmic idea is to take the better of the two solutions obtained by using: (a) the currently best 2/3-approximation algorithm for Max-ATSP-Path and (b) a naive cycle-cover based 1/2-approximation algorithm. To prove that this indeed results in an improvement, we further develop a theory of string overlaps, extending the results of Breslauer et al. This theory is based on the novel use of Lyndon words, as a substitute for generic unbordered rotations and critical factorizations, as used by Breslauer et al.
Weighted-{$\ell_1$} minimization with multiple weighting sets
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we study the support recovery conditions of weighted $\ell_1$ minimization for signal reconstruction from compressed sensing measurements when multiple support estimate sets with different accuracy are available. We identify a class of signals for which the recovered vector from $\ell_1$ minimization provides an accurate support estimate. We then derive stability and robustness guarantees for the weighted $\ell_1$ minimization problem with more than one support estimate. We show that applying a smaller weight to support estimate that enjoy higher accuracy improves the recovery conditions compared with the case of a single support estimate and the case with standard, i.e., non-weighted, $\ell_1$ minimization. Our theoretical results are supported by numerical simulations on synthetic signals and real audio signals.
A Study of "Churn" in Tweets and Real-Time Search Queries (Extended Version)
Venue: arXiv cs.IR 2012
Year: 2012

The real-time nature of Twitter means that term distributions in tweets and in search queries change rapidly: the most frequent terms in one hour may look very different from those in the next. Informally, we call this phenomenon "churn". Our interest in analyzing churn stems from the perspective of real-time search. Nearly all ranking functions, machine-learned or otherwise, depend on term statistics such as term frequency, document frequency, as well as query frequencies. In the real-time context, how do we compute these statistics, considering that the underlying distributions change rapidly? In this paper, we present an analysis of tweet and query churn on Twitter, as a first step to answering this question. Analyses reveal interesting insights on the temporal dynamics of term distributions on Twitter and hold implications for the design of search systems.
Cramér-Rao Bounds for Polynomial Signal Estimation using Sensors with AR(1) Drift
Venue: arXiv cs.IT 2012
Year: 2012

We seek to characterize the estimation performance of a sensor network where the individual sensors exhibit the phenomenon of drift, i.e., a gradual change of the bias. Though estimation in the presence of random errors has been extensively studied in the literature, the loss of estimation performance due to systematic errors like drift have rarely been looked into. In this paper, we derive closed-form Fisher Information matrix and subsequently Cramér-Rao bounds (upto reasonable approximation) for the estimation accuracy of drift-corrupted signals. We assume a polynomial time-series as the representative signal and an autoregressive process model for the drift. When the Markov parameter for drift ρ<1, we show that the first-order effect of drift is asymptotically equivalent to scaling the measurement noise by an appropriate factor. For ρ=1, i.e., when the drift is non-stationary, we show that the constant part of a signal can only be estimated inconsistently (non-zero asymptotic variance). Practical usage of the results are demonstrated through the analysis of 1) networks with multiple sensors and 2) bandwidth limited networks communicating only quantized observations.
Clinical Productivity System - A Decision Support Model
Venue: arXiv cs.DB 2012
Year: 2012

Purpose: This goal of this study was to evaluate the effects of a data-driven clinical productivity system that leverages Electronic Health Record (EHR) data to provide productivity decision support functionality in a real-world clinical setting. The system was implemented for a large behavioral health care provider seeing over 75,000 distinct clients a year. Design/methodology/approach: The key metric in this system is a "VPU", which simultaneously optimizes multiple aspects of clinical care. The resulting mathematical value of clinical productivity was hypothesized to tightly link the organization's performance to its expectations and, through transparency and decision support tools at the clinician level, affect significant changes in productivity, quality, and consistency relative to traditional models of clinical productivity. Findings: In only 3 months, every single variable integrated into the VPU system showed significant improvement, including a 30% rise in revenue, 10% rise in clinical percentage, a 25% rise in treatment plan completion, a 20% rise in case rate eligibility, along with similar improvements in compliance/audit issues, outcomes collection, access, etc. Practical implications: A data-driven clinical productivity system employing decision support functionality is effective because of the impact on clinician behavior relative to traditional clinical productivity systems. Critically, the model is also extensible to integration with outcomes-based productivity. Originality/Value: EHR's are only a first step - the problem is turning that data into useful information. Technology can leverage the data in order to produce actionable information that can inform clinical practice and decision-making. Without additional technology, EHR's are essentially just copies of paper-based records stored in electronic form.
Cooperation in Carrier Sense Based Wireless Ad Hoc Networks - Part II: Proactive Schemes
Venue: arXiv cs.NI 2012
Year: 2012

This work is the second of a two-part series of papers on the effectiveness of cooperative techniques in non-centralized carrier sense-based ad hoc wireless networks. While Part I extensively discussed reactive cooperation, characterized by relayed transmissions triggered by failure events at the intended receiver, Part II investigates in depth proactive solutions, in which the source of a packet exploits channel state information to preemptively coordinate with relays in order to achieve the optimal overall rate to the destination. In particular, this work shows by means of both analysis and simulation that the performance of reactive cooperation is reduced by the intrinsic nature of the considered medium access policy, which biases the distribution of the available relays, locating them in unfavorable positions for rate optimization. Moreover, the highly dynamic nature of interference that characterizes non-infrastructured ad hoc networks is proved to hamper the efficacy and the reliability of preemptively allocated cooperative links, as unpredicted births and deaths of surrounding transmissions may force relays to abort their support and/or change the maximum achievable rate at the intended receiver. As a general conclusion, our work extensively suggests that CSMA-based link layers are not apt to effectively support cooperative strategies in large-scale non-centralized ad hoc networks.