OpenRaiser/Intern-Atlas huggingface dataset:
Which weighted circulant networks have perfect state transfer?
Venue: arXiv cs.DM 2011
Year: 2011

The question of perfect state transfer existence in quantum spin networks based on weighted graphs has been recently presented by many authors. We give a simple condition for characterizing weighted circulant graphs allowing perfect state transfer in terms of their eigenvalues. This is done by extending the results about quantum periodicity existence in the networks obtained by Saxena, Severini and Shparlinski and characterizing integral graphs among weighted circulant graphs. Finally, classes of weighted circulant graphs supporting perfect state transfer are found. These classes completely cover the class of circulant graphs having perfect state transfer in the unweighted case. In fact, we show that there exists an weighted integral circulant graph with $n$ vertices having perfect state transfer if and only if $n$ is even. Moreover we prove the non-existence of perfect state transfer for several other classes of weighted integral circulant graphs of even order.
Characterization of circulant graphs having perfect state transfer
Venue: arXiv cs.DM 2011
Year: 2011

In this paper we answer the question of when circulant quantum spin networks with nearest-neighbor couplings can give perfect state transfer. The network is described by a circulant graph $G$, which is characterized by its circulant adjacency matrix $A$. Formally, we say that there exists a {\it perfect state transfer} (PST) between vertices $a,b\in V(G)$ if $|F(τ)_{ab}|=1$, for some positive real number $τ$, where $F(t)=\exp(ıAt)$. Saxena, Severini and Shparlinski ({\it International Journal of Quantum Information} 5 (2007), 417--430) proved that $|F(τ)_{aa}|=1$ for some $a\in V(G)$ and $τ\in \R^+$ if and only if all eigenvalues of $G$ are integer (that is, the graph is integral). The integral circulant graph $\ICG_n (D)$ has the vertex set $Z_n = \{0, 1, 2, ..., n - 1\}$ and vertices $a$ and $b$ are adjacent if $\gcd(a-b,n)\in D$, where $D \subseteq \{d : d \mid n,\ 1\leq d<n\}$. These graphs are highly symmetric and have important applications in chemical graph theory. We show that $\ICG_n (D)$ has PST if and only if $n\in 4\N$ and $D=\widetilde{D_3}\cup D_2\cup 2D_2\cup 4D_2\cup \{n/2^a\}$, where $\widetilde{D_3}=\{d\in D\ |\ n/d\in 8\N\}$, $D_2= \{d\in D\ |\ n/d\in 8\N+4\}\setminus \{n/4\}$ and $a\in\{1,2\}$. We have thus answered the question of complete characterization of perfect state transfer in integral circulant graphs raised in {\it Quantum Information and Computation}, Vol. 10, No. 3&4 (2010) 0325--0342 by Angeles-Canul {\it et al.} Furthermore, we also calculate perfect quantum communication distance (distance between vertices where PST occurs) and describe the spectra of integral circulant graphs having PST. We conclude by giving a closed form expression calculating the number of integral circulant graphs of a given order having PST.
Node coloring for dense wireless sensor networks
Venue: arXiv cs.NI 2011
Year: 2011

Coloring is used in wireless networks to improve communication efficiency, mainly in terms of bandwidth, energy and possibly end-to-end delays. In this research report, we define the h-hop node coloring problem, with h any positive integer. We prove that the associated decision problem is NP-complete. We then present a 3-hop distributed coloring algorithm that is optimized for dense networks: a node does not need to exchange the priorities and colors of its 2-hop neighbors. Through simulation results, we highlight the impact of priority assignment on the number of colors obtained for any network. We then focus on grids and identify a color pattern that can be reproduced to color the whole grid. We show how the coloring algorithm can use regularity properties to obtain a periodic color pattern with the optimal number of colors. We then consider grids with holes and study how to extend our results.
A simulation of the Neolithic transition in Western Eurasia
Venue: arXiv cs.MA 2011
Year: 2011

Farming and herding were introduced to Europe from the Near East and Anatolia; there are, however, considerable arguments about the mechanisms of this transition. Were it people who moved and outplaced the indigenous hunter- gatherer groups or admixed with them? Or was it just material and information that moved-the Neolithic Package-consisting of domesticated plants and animals and the knowledge of its use? The latter process is commonly referred to as cultural diffusion and the former as demic diffusion. Despite continuous and partly combined efforts by archaeologists, anthropologists, linguists, paleontologists and geneticists a final resolution of the debate has not yet been reached. In the present contribution we interpret results from the Global Land Use and technological Evolution Simulator (GLUES), a mathematical model for regional sociocultural development embedded in the western Eurasian geoenvironmental context during the Holocene. We demonstrate that the model is able to realistically hindcast the expansion speed and the inhomogeneous space-time evolution of the transition to agropastoralism in Europe. GLUES, in contrast to models that do not resolve endogenous sociocultural dynamics, also describes and explains how and why the Neolithic advanced in stages. In the model analysis, we uncouple the mechanisms of migration and information exchange. We find that (1) an indigenous form of agropastoralism could well have arisen in certain Mediterranean landscapes, but not in Northern and Central Europe, where it depended on imported technology and material, (2) both demic diffusion by migration or cultural diffusion by trade may explain the western European transition equally well, (3) [...]
Stability of Modified-CS and LS-CS for Recursive Reconstruction of Sparse Signal Sequences
Venue: arXiv cs.IT 2011
Year: 2011

In this work, we obtain sufficient conditions for the "stability" of our recently proposed algorithms, Least Squares Compressive Sensing residual (LS-CS) and modified-CS, for recursively reconstructing sparse signal sequences from noisy measurements. By "stability" we mean that the number of misses from the current support estimate and the number of extras in it remain bounded by a time-invariant value at all times. We show that, for a signal model with fixed signal power and support set size; support set changes allowed at every time; and gradual coefficient magnitude increase/decrease, "stability" holds under mild assumptions -- bounded noise, high enough minimum nonzero coefficient magnitude increase rate, and large enough number of measurements at every time. A direct corollary is that the reconstruction error is also bounded by a time-invariant value at all times. If the support set of the sparse signal sequence changes slowly over time, our results hold under weaker assumptions than what simple compressive sensing (CS) needs for the same error bound. Also, our support error bounds are small compared to the support size. Our discussion is backed up by Monte Carlo simulation based comparisons.
Elimination of Specular reflection and Identification of ROI: The First Step in Automated Detection of Cervical Cancer using Digital Colposcopy
Venue: arXiv cs.CV 2011
Year: 2011

Cervical Cancer is one of the most common forms of cancer in women worldwide. Most cases of cervical cancer can be prevented through screening programs aimed at detecting precancerous lesions. During Digital Colposcopy, Specular Reflections (SR) appear as bright spots heavily saturated with white light. These occur due to the presence of moisture on the uneven cervix surface, which act like mirrors reflecting light from the illumination source. Apart from camouflaging the actual features, the SR also affects subsequent segmentation routines and hence must be removed. Our novel technique eliminates the SR and makes the colposcopic images (cervigram) ready for segmentation algorithms. The cervix region occupies about half of the cervigram image. Other parts of the image contain irrelevant information, such as equipment, frames, text and non-cervix tissues. This irrelevant information can confuse automatic identification of the tissues within the cervix. The first step is, therefore, focusing on the cervical borders, so that we have a geometric boundary on the relevant image area. We have proposed a type of modified kmeans clustering algorithm to evaluate the region of interest.
Towards Normal Forms for GHZ/W Calculus
Venue: arXiv cs.LO 2011
Year: 2011

Recently, a novel GHZ/W graphical calculus has been established to study and reason more intuitively about interacting quantum systems. The compositional structure of this calculus was shown to be well-equipped to sufficiently express arbitrary mutlipartite quantum states equivalent under stochastic local operations and classical communication (SLOCC). However, it is still not clear how to explicitly identify which graphical properties lead to what states. This can be achieved if we have well-behaved normal forms for arbitrary graphs within this calculus. This article lays down a first attempt at realizing such normal forms for a restricted class of such graphs, namely simple and regular graphs. These results should pave the way for the most general cases as part of future work.
Parallel calculation of the median and order statistics on GPUs with application to robust regression
Venue: arXiv cs.DC 2011
Year: 2011

We present and compare various approaches to a classical selection problem on Graphics Processing Units (GPUs). The selection problem consists in selecting the $k$-th smallest element from an array of size $n$, called $k$-th order statistic. We focus on calculating the median of a sample, the $n/2$-th order statistic. We introduce a new method based on minimization of a convex function, and show its numerical superiority when calculating the order statistics of very large arrays on GPUs. We outline an application of this approach to efficient estimation of model parameters in high breakdown robust regression.
Disconnected Skeleton: Shape at its Absolute Scale
Venue: arXiv cs.CV 2011
Year: 2011

We present a new skeletal representation along with a matching framework to address the deformable shape recognition problem. The disconnectedness arises as a result of excessive regularization that we use to describe a shape at an attainably coarse scale. Our motivation is to rely on the stable properties of the shape instead of inaccurately measured secondary details. The new representation does not suffer from the common instability problems of traditional connected skeletons, and the matching process gives quite successful results on a diverse database of 2D shapes. An important difference of our approach from the conventional use of the skeleton is that we replace the local coordinate frame with a global Euclidean frame supported by additional mechanisms to handle articulations and local boundary deformations. As a result, we can produce descriptions that are sensitive to any combination of changes in scale, position, orientation and articulation, as well as invariant ones.
Using Hashing to Solve the Dictionary Problem (In External Memory)
Venue: arXiv cs.DS 2011
Year: 2011

We consider the dictionary problem in external memory and improve the update time of the well-known buffer tree by roughly a logarithmic factor. For any λ>= max {lg lg n, log_{M/B} (n/B)}, we can support updates in time O(λ/ B) and queries in sublogarithmic time, O(log_λn). We also present a lower bound in the cell-probe model showing that our data structure is optimal. In the RAM, hash tables have been used to solve the dictionary problem faster than binary search for more than half a century. By contrast, our data structure is the first to beat the comparison barrier in external memory. Ours is also the first data structure to depart convincingly from the indivisibility paradigm.
SharedCanvas: A Collaborative Model for Medieval Manuscript Layout Dissemination
Venue: arXiv cs.DL 2011
Year: 2011

In this paper we present a model based on the principles of Linked Data that can be used to describe the interrelationships of images, texts and other resources to facilitate the interoperability of repositories of medieval manuscripts or other culturally important handwritten documents. The model is designed from a set of requirements derived from the real world use cases of some of the largest digitized medieval content holders, and instantiations of the model are intended as the input to collection-independent page turning and scholarly presentation interfaces. A canvas painting paradigm, such as in PDF and SVG, was selected based on the lack of a one to one correlation between image and page, and to fulfill complex requirements such as when the full text of a page is known, but only fragments of the physical object remain. The model is implemented using technologies such as OAI-ORE Aggregations and OAC Annotations, as the fundamental building blocks of emerging Linked Digital Libraries. The model and implementation are evaluated through prototypes of both content providing and consuming applications. Although the system was designed from requirements drawn from the medieval manuscript domain, it is applicable to any layout-oriented presentation of images of text.
Confluent Persistence Revisited
Venue: arXiv cs.DS 2011
Year: 2011

It is shown how to enhance any data structure in the pointer model to make it confluently persistent, with efficient query and update times and limited space overhead. Updates are performed in $O(\log n)$ amortized time, and following a pointer takes $O(\log c \log n)$ time where $c$ is the in-degree of a node in the data structure. In particular, this proves that confluent persistence can be achieved at a logarithmic cost in the bounded in-degree model used widely in previous work. This is a $O(n/\log n)$-factor improvement over the previous known transform to make a data structure confluently persistent.
Inplace Algorithm for Priority Search Tree and its use in Computing Largest Empty Axis-Parallel Rectangle
Venue: arXiv cs.CG 2011
Year: 2011

There is a high demand of space-efficient algorithms in built-in or embedded softwares. In this paper, we consider the problem of designing space-efficient algorithms for computing the maximum area empty rectangle (MER) among a set of points inside a rectangular region $\cal R$ in 2D. We first propose an inplace algorithm for computing the priority search tree with a set of $n$ points in $\cal R$ using $O(\log n)$ extra bit space in $O(n\log n)$ time. It supports all the standard queries on priority search tree in $O(\log^2n)$ time. We also show an application of this algorithm in computing the largest empty axis-parallel rectangle. Our proposed algorithm needs $O(n\log^2n +m)$ time and $O(\log n)$ work-space apart from the array used for storing $n$ input points. Here $m$ is the number of maximal empty rectangles present in $\cal R$. Finally, we consider the problem of locating the maximum area empty rectangle of arbitrary orientation among a set of $n$ points, and propose an $O(n^3\log n)$ time in-place algorithm for that problem.
Noncooperatively Optimized Tolerance: Decentralized Strategic Optimization in Complex Systems
Venue: arXiv cs.GT 2011
Year: 2011

We introduce noncooperatively optimized tolerance (NOT), a generalization of highly optimized tolerance (HOT) that involves strategic (game theoretic) interactions between parties in a complex system. We illustrate our model in the forest fire (percolation) framework. As the number of players increases, our model retains features of HOT, such as robustness, high yield combined with high density, and self-dissimilar landscapes, but also develops features of self-organized criticality (SOC) when the number of players is large enough. For example, the forest landscape becomes increasingly homogeneous and protection from adverse events (lightning strikes) becomes less closely correlated with the spatial distribution of these events. While HOT is a special case of our model, the resemblance to SOC is only partial; for example, the distribution of cascades, while becoming increasingly heavy-tailed as the number of players increases, also deviates more significantly from a power law in this regime. Surprisingly, the system retains considerable robustness even as it becomes fractured, due in part to emergent cooperation between neighboring players. At the same time, increasing homogeneity promotes resilience against changes in the lightning distribution, giving rise to intermediate regimes where the system is robust to a particular distribution of adverse events, yet not very fragile to changes.
Polyethism in a colony of artificial ants
Venue: arXiv cs.AI 2011
Year: 2011

We explore self-organizing strategies for role assignment in a foraging task carried out by a colony of artificial agents. Our strategies are inspired by various mechanisms of division of labor (polyethism) observed in eusocial insects like ants, termites, or bees. Specifically we instantiate models of caste polyethism and age or temporal polyethism to evaluated the benefits to foraging in a dynamic environment. Our experiment is directly related to the exploration/exploitation trade of in machine learning.
Broadcast Analysis for Large Cooperative Wireless Networks
Venue: arXiv cs.IT 2011
Year: 2011

The capability of nodes to broadcast their message to the entire wireless network when nodes employ cooperation is considered. We employ an asymptotic analysis using an extended random network setting and show that the broadcast performance strongly depends on the path loss exponent of the medium. In particular, as the size of the random network grows, the probability of broadcast in a one-dimensional network goes to zero for path loss exponents larger than one, and goes to a nonzero value for path loss exponents less than one. In two-dimensional networks, the same behavior is observed for path loss exponents above and below two, respectively.
On Memoryless Quantitative Objectives
Venue: arXiv cs.GT 2011
Year: 2011

In two-player games on graph, the players construct an infinite path through the game graph and get a reward computed by a payoff function over infinite paths. Over weighted graphs, the typical and most studied payoff functions compute the limit-average or the discounted sum of the rewards along the path. Beside their simple definition, these two payoff functions enjoy the property that memoryless optimal strategies always exist. In an attempt to construct other simple payoff functions, we define a class of payoff functions which compute an (infinite) weighted average of the rewards. This new class contains both the limit-average and discounted sum functions, and we show that they are the only members of this class which induce memoryless optimal strategies, showing that there is essentially no other simple payoff functions.
Tuffy: Scaling up Statistical Inference in Markov Logic Networks using an RDBMS
Venue: arXiv cs.DB 2011
Year: 2011

Markov Logic Networks (MLNs) have emerged as a powerful framework that combines statistical and logical reasoning; they have been applied to many data intensive problems including information extraction, entity resolution, and text mining. Current implementations of MLNs do not scale to large real-world data sets, which is preventing their wide-spread adoption. We present Tuffy that achieves scalability via three novel contributions: (1) a bottom-up approach to grounding that allows us to leverage the full power of the relational optimizer, (2) a novel hybrid architecture that allows us to perform AI-style local search efficiently using an RDBMS, and (3) a theoretical insight that shows when one can (exponentially) improve the efficiency of stochastic local search. We leverage (3) to build novel partitioning, loading, and parallel algorithms. We show that our approach outperforms state-of-the-art implementations in both quality and speed on several publicly available datasets.
Quantum Structure in Cognition: Fundamentals and Applications
Venue: arXiv cs.AI 2011
Year: 2011

Experiments in cognitive science and decision theory show that the ways in which people combine concepts and make decisions cannot be described by classical logic and probability theory. This has serious implications for applied disciplines such as information retrieval, artificial intelligence and robotics. Inspired by a mathematical formalism that generalizes quantum mechanics the authors have constructed a contextual framework for both concept representation and decision making, together with quantum models that are in strong alignment with experimental data. The results can be interpreted by assuming the existence in human thought of a double-layered structure, a 'classical logical thought' and a 'quantum conceptual thought', the latter being responsible of the above paradoxes and nonclassical effects. The presence of a quantum structure in cognition is relevant, for it shows that quantum mechanics provides not only a useful modeling tool for experimental data but also supplies a structural model for human and artificial thought processes. This approach has strong connections with theories formalizing meaning, such as semantic analysis, and has also a deep impact on computer science, information retrieval and artificial intelligence. More specifically, the links with information retrieval are discussed in this paper.
An Optimal Real-Time Scheduling Approach: From Multiprocessor to Uniprocessor
Venue: arXiv cs.OS 2011
Year: 2011

An optimal solution to the problem of scheduling real-time tasks on a set of identical processors is derived. The described approach is based on solving an equivalent uniprocessor real-time scheduling problem. Although there are other scheduling algorithms that achieve optimality, they usually impose prohibitive preemption costs. Unlike these algorithms, it is observed through simulation that the proposed approach produces no more than three preemptions points per job.
Non-Shannon Information Inequalities in Four Random Variables
Venue: arXiv cs.IT 2011
Year: 2011

Any unconstrained information inequality in three or fewer random variables can be written as a linear combination of instances of Shannon's inequality I(A;B|C) >= 0 . Such inequalities are sometimes referred to as "Shannon" inequalities. In 1998, Zhang and Yeung gave the first example of a "non-Shannon" information inequality in four variables. Their technique was to add two auxiliary variables with special properties and then apply Shannon inequalities to the enlarged list. Here we will show that the Zhang-Yeung inequality can actually be derived from just one auxiliary variable. Then we use their same basic technique of adding auxiliary variables to give many other non-Shannon inequalities in four variables. Our list includes the inequalities found by Xu, Wang, and Sun, but it is by no means exhaustive. Furthermore, some of the inequalities obtained may be superseded by stronger inequalities that have yet to be found. Indeed, we show that the Zhang-Yeung inequality is one of those that is superseded. We also present several infinite families of inequalities. This list includes some, but not all of the infinite families found by Matus. Then we will give a description of what additional information these inequalities tell us about entropy space. This will include a conjecture on the maximum possible failure of Ingleton's inequality. Finally, we will present an application of non-Shannon inequalities to network coding. We will demonstrate how these inequalities are useful in finding bounds on the information that can flow through a particular network called the Vamos network.