Search

Information theory has provided foundations for the theories of several application areas critical for modern society, including communications, computer storage, and AI. A key aspect of Shannon's 1948 theory is a sharp lower bound on the number of bits needed to encode and communicate a string of symbols. When he introduced the theory, Shannon famously excluded any notion of semantics behind the symbols being communicated. This semantics-free notion went on to have massive impact on communication and computing technologies, even as multiple proposals for reintroducing semantics in a theory of information were being made, notably one where Carnap and Bar-Hillel used logic and reasoning to capture semantics. In this paper we present, for the first time, a Shannon-style analysis of a communication system equipped with a deductive reasoning capability, implemented using logical inference. We use some of the most important techniques developed in information theory to demonstrate significant and sometimes surprising gains in communication efficiency availed to us through such capability, demonstrated also through practical codes. We thus argue that proposals for a semantic information theory should include the power of deductive reasoning to magnify the value of transmitted bits as we strive to fully unlock the inherent potential of semantics.

In an increasingly interconnected world, a key scientific challenge is to examine mechanisms that lead to the widespread propagation of contagions, such as misinformation and pathogens, and identify risk factors that can trigger large-scale outbreaks. Underlying both the spread of disease and misinformation epidemics is the evolution of the contagion as it propagates, leading to the emergence of different strains, e.g., through genetic mutations in pathogens and alterations in the information content. Recent studies have revealed that models that do not account for heterogeneity in transmission risks associated with different strains of the circulating contagion can lead to inaccurate predictions. However, existing results on multi-strain spreading assume that the network has a vanishingly small clustering coefficient, whereas clustering is widely known to be a fundamental property of real-world social networks. In this work, we investigate spreading processes that entail evolutionary adaptations on random graphs with tunable clustering and arbitrary degree distributions. We derive a mathematical framework to quantify the epidemic characteristics of a contagion that evolves as it spreads, with the structure of the underlying network as given via arbitrary {\em joint} degree distributions of single-edges and triangles. To the best of our knowledge, our work is the first to jointly analyze the impact of clustering and evolution on the emergence of epidemic outbreaks. We supplement our theoretical finding with numerical simulations and case studies, shedding light on the impact of clustering on contagion spread.

Finding the n-th positive square number is easy, as it is simply $n^2$. But how do we find the complementary sequence, i.e. the n-th positive nonsquare number? For this case there is an explicit formula. However, for general constraints on a number, this is harder to find. In this paper, we study how to compute the n-th integer that does (or does not) satisfy a certain condition. In particular, we consider it as a fixed point problem, relate it to the iterative method of Lambek and Moser, study a bisection approach to this problem and provide formulas for various complementary sequences such as the non-k-gonal numbers, non-k-gonal pyramidal numbers, non-k-simplex numbers, non-sum-of-k-th powers and non-k-th powers. For example, we show that the n-th non k-gonal number is given by $n+round(\sqrt{\frac{2n-2+\lfloor\frac{k+1}{4}\rfloor}{k-2}})$., Comment: 16 pages, 2 figures

We study the square of opposition and its various geometric generalizations from an algebraic viewpoint. In particular, we show how the various shapes of oppositions can be framed under an algebraic framework and we illustrate this approach with algebraic structures beyond the traditional logical structures., Comment: 8 pages, 5 figures

We devise a control-theoretic reinforcement learning approach to support direct learning of the optimal policy. We establish various theoretical properties of our approach, such as convergence and optimality of our analog of the Bellman operator and Q-learning, a new control-policy-variable gradient theorem, and a specific gradient ascent algorithm based on this theorem within the context of a specific control-theoretic framework. We empirically evaluate the performance of our control theoretic approach on several classical reinforcement learning tasks, demonstrating significant improvements in solution quality, sample complexity, and running time of our approach over state-of-the-art methods.

Pandigital and penholodigital numbers are numbers that contain every digit or nonzero digit respectively. We study properties of pandigital or penholodigital numbers that are also squares or prime., Comment: 6 pages, 1 table, corrected Conjecture 1 and added Conjectures 2-4

In modern usage the Bernoulli numbers and polynomials follow Euler's approach and are defined using generating functions. We consider the functional equation $f(x)+x^k=f(x+1)$ and show that a solution can be derived from Faulhaber's formula for the sum of powers. We show how these solutions provide a characterization of Bernoulli numbers and related results., Comment: 4 pages

Numerical computation is essential to many areas of artificial intelligence (AI), whose computing demands continue to grow dramatically, yet their continued scaling is jeopardized by the slowdown in Moore's law. Multi-function multi-way analog (MFMWA) technology, a computing architecture comprising arrays of memristors supporting in-memory computation of matrix operations, can offer tremendous improvements in computation and energy, but at the expense of inherent unpredictability and noise. We devise novel randomized algorithms tailored to MFMWA architectures that mitigate the detrimental impact of imperfect analog computations while realizing their potential benefits across various areas of AI, such as applications in computer vision. Through analysis, measurements from analog devices, and simulations of larger systems, we demonstrate orders of magnitude reduction in both computation and energy with accuracy similar to digital computers.

Iterative refinement (IR) is a popular scheme for solving a linear system of equations based on gradually improving the accuracy of an initial approximation. Originally developed to improve upon the accuracy of Gaussian elimination, interest in IR has been revived because of its suitability for execution on fast low-precision hardware such as analog devices and graphics processing units. IR generally converges when the error associated with the solution method is small, but is known to diverge when this error is large. We propose and analyze a novel enhancement to the IR algorithm by adding a line search optimization step that guarantees the algorithm will not diverge. Numerical experiments verify our theoretical results and illustrate the effectiveness of our proposed scheme., Comment: 6 pages, 8 figures, added additional results with real-world matrices

Between the poker hands of straight, flush, and full house, which hand is more common? In standard 5-card poker, the order from most common to least common is straight, flush, full house. The same order is true for 7-card poker such as Texas hold'em. However, is the same true for n-card poker for larger n? We study the probability of obtaining these various hands for n-card poker for various values of $n\geq 5$. In particular, we derive equations for the probability of flush, straight and full house and show that the probability of flush is less than a straight when $n\leq 11$, and is more than a straight when n>11. Similarly, we show that the probability of full house is less than a straight when $n\leq 19$, and is more than a straight when n>19. This means that for games such as Big Two where the ordering of 13-card hands depends on the ordering in 5-card poker, the ranking ordering does not follow the occurrence probability ordering, contrary to what intuition suggests., Comment: 7 pages, 1 figure, 1 table, 3 program listings

Today, the vast majority of the world's digital information is represented using the fundamental assumption, introduced by Claude Shannon in 1948, that ``...the semantic aspects of communication are irrelevant to the engineering problem (of the design of communication systems)...''. Consider, nonetheless, the observation that we often combine a message with other information in order to deduce new facts, thereby expanding the value of such a message. It is noteworthy that to-date, no rigorous theory of communication has been put forth which postulates the existence of deductive capabilities on the receiver's side. The purpose of this paper is to present such a theory. We formally model such deductive capabilities using logic reasoning, and present a rigorous theory which covers the following generic scenario: Alice and Bob each have knowledge of some logic sentence, and they wish to communicate as efficiently as possible with the shared goal that, following their communication, Bob should be able to deduce a particular logic sentence that Alice knows to be true, but that Bob currently cannot prove. Many variants of this general setup are considered in this article; in all cases we are able to provide sharp upper and lower bounds. Our contribution includes the identification of the most fundamental requirements that we place on a logic and associated logical language for all of our results to apply. Practical algorithms that are in some cases asymptotically optimal are provided, and we illustrate the potential practical value of the design of communication systems that incorporate the assumption of deductive capabilities at the receiver using experimental results that suggest significant possible gains compared to classical systems.

A key scientific challenge during the outbreak of novel infectious diseases is to predict how the course of the epidemic changes under different countermeasures that limit interaction in the population. Most epidemiological models do not consider the role of mutations and heterogeneity in the type of contact events. However, pathogens have the capacity to mutate in response to changing environments, especially caused by the increase in population immunity to existing strains and the emergence of new pathogen strains poses a continued threat to public health. Further, in light of differing transmission risks in different congregate settings (e.g., schools and offices), different mitigation strategies may need to be adopted to control the spread of infection. We analyze a multi-layer multi-strain model by simultaneously accounting for i) pathways for mutations in the pathogen leading to the emergence of new pathogen strains, and ii) differing transmission risks in different congregate settings, modeled as network-layers. Assuming complete cross-immunity among strains, namely, recovery from any infection prevents infection with any other (an assumption that will need to be relaxed to deal with COVID-19 or influenza), we derive the key epidemiological parameters for the proposed multi-layer multi-strain framework. We demonstrate that reductions to existing network-based models that discount heterogeneity in either the strain or the network layers can lead to incorrect predictions for the course of the outbreak. In addition, our results highlight that the impact of imposing/lifting mitigation measures concerning different contact network layers (e.g., school closures or work-from-home policies) should be evaluated in connection with their effect on the likelihood of the emergence of new pathogen strains.

The rearrangement inequality states that the sum of products of permutations of 2 sequences of real numbers are maximized when the terms are similarly ordered and minimized when the terms are ordered in opposite order. We show that similar inequalities exist for multi-valued logic with the multiplication and addition operation replaced with various T-norms and T-conorms respectively. For instance, we show that the rearrangement inequality holds when the T-norms and T-conorms are derived from Archimedean copulas., Comment: 13 pages, 3 tables, corrected minor typos

Hamiltonian learning is an important procedure in quantum system identification, calibration, and successful operation of quantum computers. Through queries to the quantum system, this procedure seeks to obtain the parameters of a given Hamiltonian model and description of noise sources. Standard techniques for Hamiltonian learning require careful design of queries and $O(\epsilon^{-2})$ queries in achieving learning error $\epsilon$ due to the standard quantum limit. With the goal of efficiently and accurately estimating the Hamiltonian parameters within learning error $\epsilon$ through minimal queries, we introduce an active learner that is given an initial set of training examples and the ability to interactively query the quantum system to generate new training data. We formally specify and experimentally assess the performance of this Hamiltonian active learning (HAL) algorithm for learning the six parameters of a two-qubit cross-resonance Hamiltonian on four different superconducting IBM Quantum devices. Compared with standard techniques for the same problem and a specified learning error, HAL achieves up to a $99.8\%$ reduction in queries required, and a $99.1\%$ reduction over the comparable non-adaptive learning algorithm. Moreover, with access to prior information on a subset of Hamiltonian parameters and given the ability to select queries with linearly (or exponentially) longer system interaction times during learning, HAL can exceed the standard quantum limit and achieve Heisenberg (or super-Heisenberg) limited convergence rates during learning., Comment: 53 pages, 21 figures

Masks have remained an important mitigation strategy in the fight against COVID-19 due to their ability to prevent the transmission of respiratory droplets between individuals. In this work, we provide a comprehensive quantitative analysis of the impact of mask-wearing. To this end, we propose a novel agent-based model of viral spread on networks where agents may either wear no mask or wear one of several types of masks with different properties (e.g., cloth or surgical). We derive analytical expressions for three key epidemiological quantities: the probability of emergence, the epidemic threshold, and the expected epidemic size. In particular, we show how the aforementioned quantities depend on the structure of the contact network, viral transmission dynamics, and the distribution of the different types of masks within the population. Through extensive simulations, we then investigate the impact of different allocations of masks within the population and trade-offs between the outward efficiency and inward efficiency of the masks. Interestingly, we find that masks with high outward efficiency and low inward efficiency are most useful for controlling the spread in the early stages of an epidemic, while masks with high inward efficiency but low outward efficiency are most useful in reducing the size of an already large spread. Lastly, we study whether degree-based mask allocation is more effective in reducing the probability of epidemic as well as epidemic size compared to random allocation. The result echoes the previous findings that mitigation strategies should differ based on the stage of the spreading process, focusing on source control before the epidemic emerges and on self-protection after the emergence., Comment: Accepted at Physical Review E

Sparse linear system solvers are computationally expensive kernels that lie at the heart of numerous applications. This paper proposes a flexible preconditioning framework to substantially reduce the time and energy requirements of this task by utilizing a hybrid architecture that combines conventional digital microprocessors with analog crossbar array accelerators. Our analysis and experiments with a simulator for analog hardware demonstrate that an order of magnitude speedup is readily attainable without much impact on convergence, despite the noise in analog computations.

Stochastic computing has a long history as an alternative method of performing arithmetic on a computer. While it can be considered an unbiased estimator of real numbers, it has a variance and MSE on the order of $\Omega(\frac{1}{N})$. On the other hand, deterministic variants of stochastic computing remove the stochastic aspect, but cannot approximate arbitrary real numbers with arbitrary precision and are biased estimators. However, they have an asymptotically superior MSE on the order of $O(\frac{1}{N^2})$. Recent results in deep learning with stochastic rounding suggest that the bias in the rounding can degrade performance. We proposed an alternative framework, called dither computing, that combines aspects of stochastic computing and its deterministic variants and that can perform computing with similar efficiency, is unbiased, and with a variance and MSE also on the optimal order of $\Theta(\frac{1}{N^2})$. We also show that it can be beneficial in stochastic rounding applications as well. We provide implementation details and give experimental results to comparatively show the benefits of the proposed scheme., Comment: 8 pages, 16 figures, 1 table

We study synchronization and consensus in a group of dynamical systems coupled via multiple directed networks. We show that even though the coupling in a single network may not be sufficient to synchronize the systems, combination of multiple networks can contribute to synchronization. We illustrate how the effectiveness of a collection of networks to synchronize the coupled systems depends on the graph topology. In particular, we show that if the graph sum is a directed graph whose reversal contains a spanning directed tree, then the network synchronizes if the coupling is strong enough. This is intuitive as there is a root node that influence every other node via a set of edges where each edge in the set is in one of the networks., Comment: 6 pages, 2 figures, fixed figure 1 formatting

Schur's inequality for the sum of products of the differences of real numbers states that for $x,y,z,t\geq 0$, $x^t(x-y)(x-z) + y^t(y-z)(y-x) + z^t(z-x)(z-y) \geq 0$. In this paper we study a generalization of this inequality to more terms, more general functions of the variables and algebraic structures such as vectors and Hermitian matrices., Comment: 17 pages, 1 table

The classical rearrangement inequality provides bounds for the sum of products of two sequences under permutations of terms and show that similarly ordered sequences provide the largest value whereas opposite ordered sequences provide the smallest value. This has been generalized to multiple sequences to show that similarly ordered sequences provide the largest value. However, the permutations of the sequences that result in the smallest value are generally not known. We show a variant of the rearrangement inequality for which a lower bound can be obtained and conditions for which this bound is achieved for a sequence of permutations. We also study a generalization of the rearrangement inequality and a variation where the permutations of terms can be across the various sequences. For this variation, we can also find the minimizing and maximizing sequences under certain conditions. Finally, we also look at rearrangement inequalities of other objects that can be ordered such as functions and matrices., Comment: 21 pages. Minor corrections and added Lemma 12 and Theorem 23

We consider a new form of reinforcement learning (RL) that is based on opportunities to directly learn the optimal control policy and a general Markov decision process (MDP) framework devised to support these opportunities. Derivations of general classes of our control-based RL methods are presented, together with forms of exploration and exploitation in learning and applying the optimal control policy over time. Our general MDP framework extends the classical Bellman operator and optimality criteria by generalizing the definition and scope of a policy for any given state. We establish the convergence and optimality-both in general and within various control paradigms (e.g., piecewise linear control policies)-of our control-based methods through this general MDP framework, including convergence of $Q$-learning within the context of our MDP framework. Our empirical results demonstrate and quantify the significant benefits of our approach.

We consider the use of look-up tables (LUT) to simplify the hardware implementation of a deep learning network for inferencing after weights have been successfully trained. The use of LUT replaces the matrix multiply and add operations with a small number of LUTs and addition operations resulting in a completely multiplier-less implementation. We compare the different tradeoffs of this approach in terms of accuracy versus LUT size and the number of operations and show that similar performance can be obtained with a comparable memory footprint as a full precision deep neural network, but without the use of any multipliers. We illustrate this with several architectures such as MLP and CNN., Comment: 7 pages, 8 figures

Recent work shows unequal performance of commercial face classification services in the gender classification task across intersectional groups defined by skin type and gender. Accuracy on dark-skinned females is significantly worse than on any other group. In this paper, we conduct several analyses to try to uncover the reason for this gap. The main finding, perhaps surprisingly, is that skin type is not the driver. This conclusion is reached via stability experiments that vary an image's skin type via color-theoretic methods, namely luminance mode-shift and optimal transport. A second suspect, hair length, is also shown not to be the driver via experiments on face images cropped to exclude the hair. Finally, using contrastive post-hoc explanation techniques for neural networks, we bring forth evidence suggesting that differences in lip, eye and cheek structure across ethnicity lead to the differences. Further, lip and eye makeup are seen as strong predictors for a female face, which is a troubling propagation of a gender stereotype.

In this short note, we show a simple characterization of integers that reach records for a sequence described by adding binary strings to runs of 1's and 0's in a binary representation. In particular, we show that this set does not depend on the added strings as long as they are nonempty and of the same length., Comment: 4 pages, minor edits and corrected typos

We consider a general framework for reducing the number of trainable model parameters in deep learning networks by decomposing linear operators as a product of sums of simpler linear operators. Recently proposed deep learning architectures such as CNN, KFC, Dilated CNN, etc. are all subsumed in this framework and we illustrate other types of neural network architectures within this framework. We show that good accuracy on MNIST and Fashion MNIST can be obtained using a relatively small number of trainable parameters. In addition, since implementation of the convolutional layer is resource-heavy, we consider an approach in the transform domain that obviates the need for convolutional layers. One of the advantages of this general framework over prior approaches is that the number of trainable parameters is not fixed and can be varied arbitrarily. In particular, we illustrate the tradeoff of varying the number of trainable variables and the corresponding error rate. As an example, by using this decomposition on a reference CNN architecture for MNIST with over 3x10^6 trainable parameters, we are able to obtain an accuracy of 98.44% using only 3554 trainable parameters., Comment: 10 pages, 4 figures

We consider a new family of operators for reinforcement learning with the goal of alleviating the negative effects and becoming more robust to approximation or estimation errors. Various theoretical results are established, which include showing on a sample path basis that our family of operators preserve optimality and increase the action gap. Our empirical results illustrate the strong benefits of our family of operators, significantly outperforming the classical Bellman operator and recently proposed operators., Comment: 12 pages

We explore the possibility of using machine learning to identify interesting mathematical structures by using certain quantities that serve as fingerprints. In particular, we extract features from integer sequences using two empirical laws: Benford's law and Taylor's law and experiment with various classifiers to identify whether a sequence is, for example, nice, important, multiplicative, easy to compute or related to primes or palindromes., Comment: 9 pages, minor edits and fixed typos

In most error correction coding (ECC) frameworks, the typical error metric is the bit error rate (BER) which measures the number of bit errors. For this metric, the positions of the bits are not relevant to the decoding, and in many noise models, not relevant to the BER either. In many applications this is unsatisfactory as typically all bits are not equal and have different significance. We consider the problem of bit error correction and mitigation where bits in different positions have different importance. For error correction, we look at ECC from a Bayesian perspective and introduce Bayes estimators with general loss functions to take into account the bit significance. We propose ECC schemes that optimize this error metric. As the problem is highly nonlinear, traditional ECC construction techniques are not applicable. Using exhaustive search is cost prohibitive, and thus we use iterative improvement search techniques to find good codebooks. We optimize both general codebooks and linear codes. We provide numerical experiments to show that they can be superior to classical linear block codes such as Hamming codes and decoding methods such as minimum distance decoding. For error mitigation, we study the case where ECC is not possible or not desirable, but significance aware encoding of information is still beneficial in reducing the average error. We propose a novel number presentation format suitable for emerging storage media where the noise magnitude is unknown and possibly large and show that it has lower mean error than the traditional number format., Comment: 24 pages, added Sections 10 and 11

The optimal control of epidemic-like stochastic processes is important both historically and for emerging applications today, where it can be especially important to include time-varying parameters that impact viral epidemic-like propagation. We connect the control of such stochastic processes with time-varying behavior to the stochastic shortest path problem and obtain solutions for various cost functions. Then, under a mean-field scaling, this general class of stochastic processes is shown to converge to a corresponding dynamical system. We analogously establish that the optimal control of this class of processes converges to the optimal control of the limiting dynamical system. Consequently, we study the optimal control of the dynamical system where the comparison of both controlled systems renders various important mathematical properties of interest., Comment: arXiv admin note: substantial text overlap with arXiv:1709.07988

The study of density-dependent stochastic population processes is important from a historical perspective as well as from the perspective of a number of existing and emerging applications today. In more recent applications of these processes, it can be especially important to include time-varying parameters for the rates that impact the density-dependent population structures and behaviors. Under a mean-field scaling, we show that such density-dependent stochastic population processes with time-varying behavior converge to a corresponding dynamical system. We analogously establish that the optimal control of such density-dependent stochastic population processes converges to the optimal control of the limiting dynamical system. An analysis of both the dynamical system and its optimal control renders various important mathematical properties of interest.

We consider the optimal allocation of generic resources among multiple generic entities of interest over a finite planning horizon, where each entity generates stochastic returns as a function of its resource allocation during each period. The main objective is to maximize the expected return while at the same time managing risk to an acceptable level for each period. We devise a general solution framework and establish how to obtain the optimal dynamic resource allocation., Comment: 19 pages

We study properties of functions of binomial coefficients mod 2 and derive a set of recurrence relations for sums of products of binomial coefficients mod 2. We show that they result in sequences that are the run length transforms of well known basic sequences. In particular, we obtain formulas for the run length transform of the positive integers, Fibonacci numbers, extended Lucas numbers and Narayana's cows sequence., Comment: 22 pages, 1 table, minor edits

We consider the minimal number of points on a regular grid on the plane that generates $n$ line segments of points of exactly length $k$. We illustrate how this is related to the $n$-queens problem on the toroidal chessboard and show that this number is upper bounded by $kn/3$ and approaches $kn/4$ as $n\rightarrow\infty$ when $k+1$ is coprime with $6$ or when $k$ is large., Comment: 9 pages, 6 figures

In general graph theory, the only relationship between vertices are expressed via the edges. When the vertices are embedded in an Euclidean space, the geometric relationships between vertices and edges can be interesting objects of study. We look at the number of isosceles triangles where the vertices are points on a regular grid and show that they satisfy a recurrence relation when the grid is large enough. We also derive recurrence relations for the number of acute, obtuse and right isosceles triangles., Comment: corrected minor typos

In 1998, Bird introduced Meertens numbers as numbers that are invariant under a map similar to the Godel encoding. In base 10, the only known Meertens number is 81312000. We look at some properties of Meertens numbers and consider variations of this concept. In particular, we consider variations where there is a finite time algorithm to decide whether such numbers exist.

We consider the problem of finding the set of permutations $r_j$ of $\{1,\cdots , n\}$ such that $\sum_{i=1}^n \prod_{j=1}^k r_j(i)$ is maximized or minimized. While the set of permutations maximizing this value are easily determined, finding the set of permutations minimizing this value appears to be an open problem. We show values of $k$ and $n$ for which an explicit solution exists and comment on computational issues in determining the general problem. We also look at the dual problem of finding the permutations such that $\prod_{i=1}^n \sum_{j=1}^k r_j(i)$ is maximized or minimized. As part of this study we also look at a variant of a rearrangement inequality., Comment: 16 pages. Added Theorem 10

Consider the operation of adding the same number of identical digits to the left and to the right of a number n. In OEIS sequence A090287, it was conjectured that this operation will not produce a prime if and only if n is a palindrome with an even number of digits. We show that this conjecture is false by showing that this property also holds for n=231, n=420, and an infinite number of other values of n., Comment: Minor changes and added section on other bases

Recently normalized Laplacian matrices of graphs are studied as density matrices in quantum mechanics. Separability and entanglement of density matrices are important properties as they determine the nonclassical behavior in quantum systems. In this note we look at the graphs whose normalized Laplacian matrices are separable or entangled. In particular, we show that the number of such graphs is related to the number of 0-1 matrices that are line sum symmetric and to the number of graphs with at least one vertex of degree 1., Comment: 7 pages, 1 figure

Normalized Laplacian matrices of graphs have recently been studied in the context of quantum mechanics as density matrices of quantum systems. Of particular interest is the relationship between quantum physical properties of the density matrix and the graph theoretical properties of the underlying graph. One important aspect of density matrices is their entanglement properties, which are responsible for many nonintuitive physical phenomena. The entanglement property of normalized Laplacian matrices is in general not invariant under graph isomorphism. In recent papers, graphs were identified whose entanglement and separability properties are invariant under isomorphism. The purpose of this note is to characterize the set of graphs whose separability is invariant under graph isomorphism. In particular, we show that this set consists of $K_{2,2}$, $\overline{K_{2,2}}$ and all complete graphs., Comment: 5 pages

Recently, Braunstein et al. [1] introduced normalized Laplacian matrices of graphs as density matrices in quantum mechanics and studied the relationships between quantum physical properties and graph theoretical properties of the underlying graphs. We provide further results on the multipartite separability of Laplacian matrices of graphs. In particular, we identify complete bipartite graphs whose normalized Laplacian matrix is multipartite entangled under any vertex labeling. Furthermore, we give conditions on the vertex degrees such that there is a vertex labeling under which the normalized Laplacian matrix is entangled. These results address an open question raised in [1]. Finally, we extend some of the results in [1,2] to the multipartite case and show that the Laplacian matrix of any product of graphs (strong, Cartesian, tensor, categorical, etc.) is multipartite separable., Comment: 13 pages, 1 figure

The concepts of paracontracting, pseudocontracting and nonexpanding operators have been shown to be useful in proving convergence of asynchronous or parallel iteration algorithms. The purpose of this paper is to give characterizations of these operators when they are linear and finite-dimensional. First we show that pseudocontractivity of stochastic matrices with respect to sup-norm is equivalent to the scrambling property, a concept first introduced in the study of inhomogeneous Markov chains. This unifies results obtained independently using different approaches. Secondly, we generalize the concept of pseudocontractivity to set-contractivity which is a useful generalization with respect to the Euclidean norm. In particular, we demonstrate non-Hermitian matrices that are set-contractive for ||.||_2, but not pseudocontractive for ||.||_2 or sup-norm. For constant row sum matrices we characterize set-contractivity using matrix norms and matrix graphs. Furthermore, we prove convergence results in compositions of set-contractive operators and illustrate the differences between set-contractivity in different norms. Finally, we give an application to the global synchronization in coupled map lattices., Comment: 17 pages

Recently, Laplacian matrices of graphs are studied as density matrices in quantum mechanics. We continue this study and give conditions for separability of generalized Laplacian matrices of weighted graphs with unit trace. In particular, we show that the Peres-Horodecki positive partial transpose separability condition is necessary and sufficient for separability in ${\mathbb C}^2\otimes {\mathbb C}^q$. In addition, we present a sufficient condition for separability of generalized Laplacian matrices and diagonally dominant nonnegative matrices., Comment: 10 pages, 1 figure

In a recent paper, wavelet analysis was used to perturb the coupling matrix in an array of identical chaotic systems in order to improve its synchronization. As the synchronization criterion is determined by the second smallest eigenvalue $\lambda_2$ of the coupling matrix, the problem is equivalent to studying how $\lambda_2$ of the coupling matrix changes with perturbation. In the aforementioned paper, a small percentage of the wavelet coefficients are modified. However, this result in a perturbed matrix where every element is modified and nonzero. The purpose of this paper is to present some results on the change of $\lambda_2$ due to perturbation. In particular, we show that as the number of systems $n \to \infty$, perturbations which only add local coupling will not change $\lambda_2$. On the other hand, we show that there exists perturbations which affect an arbitrarily small percentage of matrix elements, each of which is changed by an arbitrarily small amount and yet can make $\lambda_2$ arbitrarily large. These results give conditions on what the perturbation should be in order to improve the synchronizability in an array of coupled chaotic systems. This analysis allows us to prove and explain some of the synchronization phenomena observed in a recently studied network where random coupling are added to a locally connected array. Finally we classify various classes of coupling matrices such as small world networks and scale free networks according to their synchronizability in the limit., Comment: 7 pages, 2 figures, 1 table